Algorithmic Problem Solving with Python

1 Algorithmic Problem Solving with PythonJohn B. SchneiderShira Lynn BroschatJess DahmenFebruary 22, 2019iiContents1 Computers .. Languages .. Problem Solving .. Python .. Python .. Sessions and Comments .. Commands from a File .. ()Function .. on Learning New Languages .. Chapter Summary .. Review Questions .. 152 Core and Types.. , Arithmetic Operators, and Precedence .. and the Assignment Operator.. and Simultaneous Assignment.. Statements and Multi-Line Strings .. and Keywords .. and Namespaces .. Arithmetic Operators .. Division .. anddivmod().. Assignment .. Summary .. Review Questions .. Exercises.

2 493 Input and Type Input:input().. Type Conversion:int(),float(), andstr().. Strings:eval().. Summary .. Questions .. 654 Functions andNone.. Void Functions .. Functions.. of Variables .. of Functions .. () .. amain()Function .. Parameters .. Summary .. Review Questions .. Exercises .. 925 Introduction to of Objects and Classes .. a Class: Attributes .. a Class: Methods .. ()Function .. ()Method .. Overloading.. Message .. Summary .. 1076 Lists .. ().. , Immutability, and Tuples .. Loops in Functions.. Assignment with Lists .. Entries in alist.. Sequence.

3 Chapter Summary .. Review Questions .. 133 CONTENTSv7 More onfor-Loops, Lists, and withinfor-Loops .. oflists .. Embeddedlists .. Assignment andlists oflists .. andlistMutability.. as Iterables or Sequences .. Indices.. (optional) .. Summary .. Questions .. 1728 Modules Entire Modules .. to Complex Numbers .. Numbers and thecmathModule .. Selected Parts of a Module .. an Entire Module Using*.. Your Own Module.. Summary .. Questions .. 1949 Basics .. ASCII Characters .. Sequences.. ()andord().. String Methods .. (),upper(),capitalize(),title(), andswapcase(). ().. (),lstrip(), andrstrip().. ().. ()andindex().

4 ().. ()andjoin().. Strings and theformat()Method .. Fields as Placeholders .. Specifier: Width .. Specifier: Alignment .. Specifier: Fill and Zero Padding.. Specifier: Precision (Maximum Width) .. Specifier: Type .. Specifier: Summary .. Formatting Example .. Summary .. Questions .. 23110 Reading and Writing Reading a File .. (),close(), andtell().. ().. ().. File Object Used as an Iterable .. Using More than One Read Method .. Writing to a File.. ()andprint().. ().. Chapter Summary .. Review Questions .. 25211 Conditional , Boolean Variables, andbool().. Comparison Operators .. Compound Conditional Statements .. Logical Operators.

5 Multiple Comparisons .. Infinite Loops andbreak.. Short-Circuit Behavior .. TheinOperator .. Chapter Summary .. Questions .. 29012 Background .. Flawed Recursion .. Proper Recursion .. Merge Sort .. 30613 Turtle Introduction .. Turtle Basics .. Importing Turtle Graphics .. Your First Drawing .. Basic Shapes and Using Iteration to Generate Graphics .. Controlling the Turtle s Animation Speed .. Colors and Filled Shapes .. Strange Errors .. Filled Shapes .. Visualizing Recursion .. Simple GUI Walk-Through .. Function References .. Callback functions .. A simple GUI .. 33214 Dictionary Basics.

6 Cycling through a Dictionary .. ().. Chapter Summary .. Review Questions .. 344A ASCII Non-printable Characters347 Index349viiiCONTENTSC hapter Modern ComputersAt their core, computers are remarkably simple devices. Nearly all computers today are builtusing electronic devices called transistors. These transistors serve as switches that behave muchlike simple light switches they can be on or they can be off. In a digital computer eachbitofinformation (whether input, memory, or output) can be in only one of two states: either off or on,or we might call these states low or high, or perhaps zero or one. When we say bit, we have inmind the technical definition. A bit is abinary digitthat can be either 0 or 1 (zero or one).

7 In a veryreal sense computers only understand these two numbers. However, by combining thousandsor millions or even billions of these transistor switches we can achieve fantastically complicatedbehavior. Thus, rather than keeping track of a single binary digit, with computers we may be ableto work with a stream of bits of arbitrary each additional bit we use to represent a quantity, we double the number of possible uniquevalues the quantity can have. One bit can represent only two states or values: 0 and 1. This mayseem extremely limiting, but a single bit is enough to represent whether the answer to a questionis yes or no or a single bit can be used to tell us whether a logical statement evaluates to eithertrue or false.

8 We merely have to agree to interpret values consistently, for example, 0 representsno or false while 1 represents yes or true. Two bits can represent four states which we can writeas: 00, 01, 10, and 11 (read this as zero-zero, zero-one, one-zero, one-one). Three bits have eightunique combinations or values: 000, 001, 010, 011, 100, 101, 110, and 111. In general, fornbitsthe number of unique values 7bits, there are27= 128unique values. This is already more than the number ofall the keys on a standard keyboard, , more than all the letters in the English alphabet (bothuppercase and lowercase), plus the digits (0 through 9), plus all the standard punctuation , by using a mapping (orencoding) of keyboard characters to unique combinations of binarydigits, we can act as though we are working with characters when, really, we are doing nothingmore than manipulating binary can also take values from the (real) continuous world and digitize them.

9 Rather thanhaving values such as the amplitude of a sound wave or the color of an object vary continuously,we restrict the amplitude or color to vary between fixed values or levels. This process is also knownFrom the 1. INTRODUCTIONas digitizing or quantizing. If the levels of quantization are close enough, we can fool our sensesinto thinking the digitized quantity varies continuously as it does in the real world. Through theprocess of digitizing, we can store, manipulate, and render music or pictures on our computerswhen we are simply dealing with a collection of zeros and Computer LanguagesComputers, though remarkably simple at their core, have, nevertheless, truly revolutionized theway we live. They have enabled countless advances in science, engineering, and medicine.

10 Theyhave affected the way we exchange information, how we socialize, how we work, and how we a large degree, these incredible advances have been made possible through the development ofnew languages that allow humans to tell a computer what it should do. These so-calledcomputerlanguagesprovide a way for us to express what we want done in a way that is more natural to theway we think and yet precise enough to control a , as humans, are also phenomenal computing devices, but the way we think and communi-cate is generally a far cry from the way computers think and communicate. Computer languagesprovide a way of bridging this gap. But, the gap between computers and humans is vast and,for those new to computer programming, these languages can often be tremendously challengingto master.