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 .. 493 Input and Type Input:input().. Type Conversion:int(),float(), andstr().. Strings:eval().. Summary .. Questions .. 654 Functions andNone.. Void Functions .. Functions.

2 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 .. 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*.

3 Your Own Module.. Summary .. Questions .. 1949 Basics .. ASCII Characters .. Sequences.. ()andord().. String Methods .. (),upper(),capitalize(),title(), andswapcase(). ().. (),lstrip(), andrstrip().. ().. ()andindex().. ().. ()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.

4 Logical Operators.. 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 .. Cycling through a Dictionary .. ().. Chapter Summary .. Review Questions .. 344A ASCII Non-printable Characters347 Index349viiiCONTENTSC hapter Modern ComputersAt their core, computers are remarkably simple devices.

5 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). 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.

6 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. 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.

7 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. 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.

8 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. There are three important points that one must keep in mind when learning , these languages arenotdesigned to provide a means for having a two-way dialog witha computer. These languages are more like instruction sets where the human specifies what thecomputer should do. The computer blindly follows these instructions. In some sense, computerlanguages provide a way for humans to communicatetocomputers and with these languages wealso have to tell the computers how we want them to communicate back to us (and it is extremelyrare that we want a computer to communicate information back to us in the same language we usedto communicate to it).

9 Second, unlike with natural languages1, there is no ambiguity in a computer language. State-ments in natural languages are often ambiguous while also containing redundant or superfluouscontent. Often the larger context in which a statement is made serves to remove the ambiguitywhile the redundant content allows us to make sense of a statement even if we miss part of it. Asyou will see, there may be a host of different ways to write statements in a computer languagethat ultimately lead to the same , the path by which an outcome is reached isprecisely determined by the statements/instructions that are provided to the computer. Note thatwe will often refer to statements in a computer language as computer code or simply code. 2We will call a collection of statements that serves to complete a desired task third important point about computer languages is that a computer can never infer meaningor intent. You may have a very clear idea of what you want a computer to do, but if you do not ex-plicitly state your desires using precisesyntaxandsemantics, the chances of obtaining the desiredoutcome are exceedingly small.

10 When we say syntax, we essentially mean the rules of grammar1By natural languages we mean languages that humans use with each has nothing to do with a secret code nor does code in this sense imply anything to do with program that is written specifically to serve the needs of a user is often called anapplication. We will notbother to distinguish between programs and PYTHON3and punctuation in a language. When writing natural languages, the introduction of a small num-ber of typographical errors, although perhaps annoying to the reader, often does not completelyobscure the underlying information contained in the writing. On the other hand, in some computerlanguages even one small typographical error in a computer program, which may be tens of thou-sands of lines of code, can often prevent the program from ever running. The computer can t makesense of the entire program so it won t do anything at show-stopping typographical errorof syntax, , a syntactic bug, that prevents a program from running is actually often preferable toother kinds of typographical errors that allow the code to run but, as a consequence of the error, thecode produces something other than the desired result.