Programming with Python for beginners

introduction to computation and programming using python and lecture notes on python programming pdf free download
FrankRoberts Profile Pic
Published Date:11-07-2017
Your Website URL(Optional)
1 GETTING STARTED A computer does two things, and two things only: it performs calculations and it remembers the results of those calculations. But it does those two things extremely well. The typical computer that sits on a desk or in a briefcase performs a billion or so calculations a second. It’s hard to image how truly fast that is. Think about holding a ball a meter above the floor, and letting it go. By the time it reaches the floor, your computer could have executed over a billion instructions. As for memory, a typical computer might have hundreds of gigabytes of storage. How big is that? If a byte (the number of bits, typically eight, required to represent one character) weighed one ounce (which it doesn’t), 100 gigabytes would weigh more than 3,000,000 tons. For comparison, that’s roughly the weight of all the coal produced in a year in the U.S. For most of human history, computation was limited by the speed of calculation of the human brain and the ability to record computational results with the human hand. This meant that only the smallest problems could be attacked computationally. Even with the speed of modern computers, there are still problems that are beyond modern computational models (e.g., understanding climate change), but more and more problems are proving amenable to computational solution. It is our hope that by the time you finish this book, you will feel comfortable bringing computational thinking to bear on solving many of the problems you encounter during your studies, work, and even everyday life. What do we mean by computational thinking? All knowledge can be thought of as either declarative or imperative. Declarative knowledge is composed of statements of fact. For example, “the square root of x is a number y such that y y = x.” This is a statement of fact. Unfortunately it doesn’t tell us how to find a square root. Imperative knowledge is “how to” knowledge, or recipes for deducing information. Heron of Alexandria was the first to document a way to compute 2 the square root of a number. His method can be summarized as: • Start with a guess, g. • If g g is close enough to x, stop and say that g is the answer. • Otherwise create a new guess by averaging g and x/g, i.e., (g + x/g)/2. • Using this new guess, which we again call g, repeat the process until g g is close enough to x. 2 Many believe that Heron was not the inventor of this method, and indeed there is some evidence that it was well known to the ancient Babylonians. 2 Chapter 1. Getting Started Consider, for example, finding the square root of 25. 1. Set g to some arbitrary value, e.g., 3. 2. We decide that 3 3 = 9 is not close enough to 25. 3 3. Set g to (3 + 25/3)/2 = 5.67. 4. We decide that 5.67 5.67 = 32.15 is still not close enough to 25. 5. Set g to (5.67 + 25/5.67)/2 = 5.04 6. We decide that 5.04 5.04 = 25.4 is close enough, so we stop and declare 5.04 to be an adequate approximation to the square root of 25. Note that the description of the method is a sequence of simple steps, together with a flow of control that specifies when each step is to be executed. Such a 4 description is called an algorithm. This algorithm is an example of a guess- and-check algorithm. It is based on the fact that it is easy to check whether or not a guess is a good one. A bit more formally, an algorithm is a finite list of instructions that describe a computation that when executed on a provided set of inputs will proceed through a set of well-defined states and eventually produce an output. An algorithm is a bit like a recipe from a cookbook: 1. Put custard mixture over heat. 2. Stir. 3. Dip spoon in custard. 4. Remove spoon and run finger across back of spoon. 5. If clear path is left, remove custard from heat and let cool. 6. Otherwise repeat. It includes some tests for deciding when the process is complete, as well as instructions about the order in which to execute instructions, sometimes jumping to some instruction based on a test. So how does one capture this idea of a recipe in a mechanical process? One way would be to design a machine specifically intended to compute square roots. Odd as this may sound, the earliest computing machines were, in fact, fixed- program computers, meaning they were designed to do very specific things, and were mostly tools to solve a specific mathematical problem, e.g., to compute the trajectory of an artillery shell. One of the first computers (built in 1941 by Atanasoff and Berry) solved systems of linear equations, but could do nothing else. Alan Turing’s bombe machine, developed during World War II, was designed strictly for the purpose of breaking German Enigma codes. Some very simple computers still use this approach. For example, a four-function calculator is a fixed-program computer. It can do basic arithmetic, but it cannot 3 For simplicity, we are rounding results. 4 The word “algorithm” is derived from the name of the Persian mathematician Muhammad ibn Musa al-Khwarizmi. Chapter 1. Getting Started 3 be used as a word processor or to run video games. To change the program of such a machine, one has to replace the circuitry. 5 The first truly modern computer was the Manchester Mark 1. It was distinguished from its predecessors by the fact that it was a stored-program computer. Such a computer stores (and manipulates) a sequence of instructions, and has a set of elements that will execute any instruction in that sequence. By creating an instruction-set architecture and detailing the computation as a sequence of instructions (i.e., a program), we make a highly flexible machine. By treating those instructions in the same way as data, a stored-program machine can easily change the program, and can do so under program control. Indeed, the heart of the computer then becomes a program (called an interpreter) that can execute any legal set of instructions, and thus can be used to compute anything that one can describe using some basic set of instructions. Both the program and the data it manipulates reside in memory. Typically there is a program counter that points to a particular location in memory, and computation starts by executing the instruction at that point. Most often, the interpreter simply goes to the next instruction in the sequence, but not always. In some cases, it performs a test, and on the basis of that test, execution may jump to some other point in the sequence of instructions. This is called flow of control, and is essential to allowing us to write programs that perform complex tasks. Returning to the recipe metaphor, given a fixed set of ingredients a good chef can make an unbounded number of tasty dishes by combining them in different ways. Similarly, given a small fixed set of primitive elements a good programmer can produce an unbounded number of useful programs. This is what makes programming such an amazing endeavor. To create recipes, or sequences of instructions, we need a programming language in which to describe these things, a way to give the computer its marching orders. In 1936, the British mathematician Alan Turing described a hypothetical computing device that has come to be called a Universal Turing Machine. The machine had an unbounded memory in the form of tape on which one could write zeros and ones, and some very simple primitive instructions for moving, reading, and writing to the tape. The Church-Turing thesis states that if a function is computable, a Turing Machine can be programmed to compute it. The “if” in the Church-Turing thesis is important. Not all problems have computational solutions. For example, Turing showed that it is impossible to write a program that given an arbitrary program, call it P, prints true if and only if P will run forever. This is known as the halting problem. 5 This computer was built at the University of Manchester, and ran its first program in 1949. It implemented ideas previously described by John von Neumann and was anticipated by the theoretical concept of the Universal Turing Machine described by Alan Turing in 1936. 4 Chapter 1. Getting Started The Church-Turing thesis leads directly to the notion of Turing completeness. A programming language is said to be Turing complete if it can be used to simulate a universal Turing Machine. All modern programming languages are Turing complete. As a consequence, anything that can be programmed in one programming language (e.g., Python) can be programmed in any other programming language (e.g., Java). Of course, some things may be easier to program in a particular language, but all languages are fundamentally equal with respect to computational power. Fortunately, no programmer has to build programs out of Turing’s primitive instructions. Instead, modern programming languages offer a larger, more convenient set of primitives. However, the fundamental idea of programming as the process of assembling a sequence of operations remains central. Whatever set of primitives one has, and whatever methods one has for using them, the best thing and the worst thing about programming are the same: the computer will do exactly what you tell it to do. This is a good thing because it means that you can make it do all sorts of fun and useful things. It is a bad thing because when it doesn’t do what you want it to do, you usually have nobody to blame but yourself. There are hundreds of programming languages in the world. There is no best language (though one could nominate some candidates for worst). Different languages are better or worse for different kinds of applications. MATLAB, for example, is an excellent language for manipulating vectors and matrices. C is a good language for writing the programs that control data networks. PHP is a good language for building Web sites. And Python is a good general-purpose language. Each programming language has a set of primitive constructs, a syntax, a static semantics, and a semantics. By analogy with a natural language, e.g., English, the primitive constructs are words, the syntax describes which strings of words constitute well-formed sentences, the static semantics defines which sentences are meaningful, and the semantics defines the meaning of those sentences. The primitive constructs in Python include literals (e.g., the number 3.2 and the string 'abc') and infix operators (e.g., + and /). The syntax of a language defines which strings of characters and symbols are well formed. For example, in English the string “Cat dog boy.” is not a syntactically valid sentence, because the syntax of English does not accept sentences of the form noun noun noun. In Python, the sequence of primitives 3.2 + 3.2 is syntactically well formed, but the sequence 3.2 3.2 is not. The static semantics defines which syntactically valid strings have a meaning. In English, for example, the string “I are big,” is of the form pronoun linking verb adjective, which is a syntactically acceptable sequence. Nevertheless, it is not valid English, because the noun “I” is singular and the verb “are” is plural. This is an example of a static semantic error. In Python, the sequence 3.2/'abc' is syntactically well formed (literal operator literal), but Chapter 1. Getting Started 5 produces a static semantic error since it is not meaningful to divide a number by a string of characters. The semantics of a language associates a meaning with each syntactically correct string of symbols that has no static semantic errors. In natural languages, the semantics of a sentence can be ambiguous. For example, the sentence “I cannot praise this student too highly,” can be either flattering or damning. Programming languages are designed so that each legal program has exactly one meaning. Though syntax errors are the most common kind of error (especially for those learning a new programming language), they are the least dangerous kind of error. Every serious programming language does a complete job of detecting syntactic errors, and will not allow users to execute a program with even one syntactic error. Furthermore, in most cases the language system gives a sufficiently clear indication of the location of the error that it is obvious what needs to be done to fix it. The situation with respect to static semantic errors is a bit more complex. Some programming languages, e.g., Java, do a lot of static semantic checking before allowing a program to be executed. Others, e.g., C and Python (alas), do relatively less static semantic checking. Python does do a considerable amount of static semantic checking while running a program. However, it does not catch all static semantic errors. When these errors are not detected, the behavior of a program is often unpredictable. We will see examples of this later in the book. One doesn’t usually speak of a program as having a semantic error. If a program has no syntactic errors and no static semantic errors, it has a meaning, i.e., it has semantics. Of course, that isn’t to say that it has the semantics that its creator intended it to have. When a program means something other than what its creator thinks it means, bad things can happen. What might happen if the program has an error, and behaves in an unintended way? • It might crash, i.e., stop running and produce some sort of obvious indication that it has done so. In a properly designed computing system, when a program crashes it does not do damage to the overall system. Of course, some very popular computer systems don’t have this nice property. Almost everyone who uses a personal computer has run a program that has managed to make it necessary to restart the whole computer. • Or it might keep running, and running, and running, and never stop. If one has no idea of approximately how long the program is supposed to take to do its job, this situation can be hard to recognize. • Or it might run to completion and produce an answer that might, or might not, be correct. 6 Chapter 1. Getting Started Each of these is bad, but the last of them is certainly the worst, When a program appears to be doing the right thing but isn’t, bad things can follow. Fortunes can be lost, patients can receive fatal doses of radiation therapy, airplanes can crash, etc. Whenever possible, programs should be written in such a way that when they don’t work properly, it is self-evident. We will discuss how to do this throughout the book. Finger Exercise: Computers can be annoyingly literal. If you don’t tell them exactly what you want them to do, they are likely to do the wrong thing. Try writing an algorithm for driving between two destinations. Write it the way you would for a person, and then imagine what would happen if that person executed the algorithm exactly as written. For example, how many traffic tickets might they get? 2 INTRODUCTION TO PYTHON Though each programming language is different (though not as different as their designers would have us believe), there are some dimensions along which they can be related. • Low-level versus high-level refers to whether we program using instructions and data objects at the level of the machine (e.g., move 64 bits of data from this location to that location) or whether we program using more abstract operations (e.g., pop up a menu on the screen) that have been provided by the language designer. • General versus targeted to an application domain refers to whether the primitive operations of the programming language are widely applicable or are fine-tuned to a domain. For example Adobe Flash is designed to facilitate adding animation and interactivity to Web pages, but you wouldn’t want to use it build a stock portfolio analysis program. • Interpreted versus compiled refers to whether the sequence of instructions written by the programmer, called source code, is executed directly (by an interpreter) or whether it is first converted (by a compiler) into a sequence of machine-level primitive operations. (In the early days of computers, people had to write source code in a language that was very close to the machine code that could be directly interpreted by the computer hardware.) There are advantages to both approaches. It is often easier to debug programs written in languages that are designed to be interpreted, because the interpreter can produce error messages that are easy to correlate with the source code. Compiled languages usually produce programs that run more quickly and use less space. In this book, we use Python. However, this book is not about Python. It will certainly help readers learn Python, and that’s a good thing. What is much more important, however, is that careful readers will learn something about how to write programs that solve problems. This skill can be transferred to any programming language. Python is a general-purpose programming language that can be used effectively to build almost any kind of program that does not need direct access to the computer’s hardware. Python is not optimal for programs that have high reliability constraints (because of its weak static semantic checking) or that are built and maintained by many people or over a long period of time (again because of the weak static semantic checking). However, Python does have several advantages over many other languages. It is a relatively simple language that is easy to learn. Because Python is designed to be interpreted, it can provide the kind of runtime feedback that is especially helpful to novice programmers. There are also a large number of freely available libraries that interface to Python and provide useful extended functionality. Several of those are used in this book. 8 Chapter 2. Introduction to Python Now we are ready to start learning some of the basic elements of Python. These are common to almost all programming languages in concept, though not necessarily in detail. The reader should be forewarned that this book is by no means a comprehensive introduction to Python. We use Python as a vehicle to present concepts related to computational problem solving and thinking. The language is presented in dribs and drabs, as needed for this ulterior purpose. Python features that we don’t need for that purpose are not presented at all. We feel comfortable about not covering the entire language because there are excellent online resources describing almost every aspect of the language. When we teach the course on which this book is based, we suggest to the students that they rely on these free online resources for Python reference material. Python is a living language. Since its introduction by Guido von Rossum in 1990, it has undergone many changes. For the first decade of its life, Python was a little known and little used language. That changed with the arrival of Python 2.0 in 2000. In addition to incorporating a number of important improvements to the language itself, it marked a shift in the evolutionary path of the language. A large number of people began developing libraries that interfaced seamlessly with Python, and continuing support and development of the Python ecosystem became a community-based activity. Python 3.0 was released at the end of 2008. This version of Python cleaned up many of the inconsistencies in the design of the various releases of Python 2 (often referred to as Python 2.x). However, it was not backward compatible. That meant that most programs written for earlier versions of Python could not be run using implementations of Python 3.0. The backward incompatibility presents a problem for this book. In our view, Python 3.0 is clearly superior to Python 2.x. However, at the time of this writing, some important Python libraries still do not work with Python 3. We will, therefore, use Python 2.7 (into which many of the most important features of Python 3 have been “back ported”) throughout this book. 2.1 The Basic Elements of Python A Python program, sometimes called a script, is a sequence of definitions and commands. These definitions are evaluated and the commands are executed by the Python interpreter in something called the shell. Typically, a new shell is created whenever execution of a program begins. In most cases, a window is associated with the shell. We recommend that you start a Python shell now, and use it to try the examples contained in the remainder of the chapter. And, for that matter, later in the book as well. A command, often called a statement, instructs the interpreter to do something. For example, the statement print 'Yankees rule' instructs the interpreter to output the string Yankees rule to the window associated with the shell. Chapter 2. Introduction to Python 9 The sequence of commands print 'Yankees rule' print 'But not in Boston' print 'Yankees rule,', 'but not in Boston' causes the interpreter to produce the output Yankees rule But not in Boston Yankees rule, but not in Boston Notice that two values were passed to print in the third statement. The print command takes a variable number of values and prints them, separated by a 6 space character, in the order in which they appear. 2.1.1 Objects, Expressions, and Numerical Types Objects are the core things that Python programs manipulate. Every object has a type that defines the kinds of things that programs can do with objects of that type. Types are either scalar or non-scalar. Scalar objects are indivisible. Think of 7 them as the atoms of the language. Non-scalar objects, for example strings, have internal structure. Python has four types of scalar objects: • int is used to represent integers. Literals of type int are written in the way we typically denote integers (e.g., -3 or 5 or 10002). • float is used to represent real numbers. Literals of type float always include a decimal point (e.g., 3.0 or 3.17 or -28.72). (It is also possible to write literals of type float using scientific notation. For example, the 3 literal 1.6E3 stands for 1.6 10 , i.e., it is the same as 1600.0.) You might wonder why this type is not called real. Within the computer, values of type float are stored in the computer as floating point numbers. This representation, which is used by all modern programming languages, has many advantages. However, under some situations it causes floating point arithmetic to behave in ways that are slightly different from arithmetic on real numbers. We discuss this in Section 3.4. • bool is used to represent the Boolean values True and False. • None is a type with a single value. We will say more about this when we get to variables. Objects and operators can be combined to form expressions, each of which evaluates to an object of some type. We will refer to this as the value of the expression. For example, the expression 3 + 2 denotes the object 5 of type int, and the expression 3.0 + 2.0 denotes the object 5.0 of type float. 6 In Python 3, print is a function rather than a command. One would therefore write print('Yankees rule', 'but not in Boston'). 7 Yes, atoms are not truly indivisible. However, splitting them is not easy, and doing so can have consequences that are not always desirable. 10 Chapter 2. Introduction to Python The == operator is used to test whether two expressions evaluate to the same value, and the = operator is used to test whether two expressions evaluate to different values. The symbol is a shell prompt indicating that the interpreter is expecting the user to type some Python code into the shell. The line below the line with the prompt is produced when the interpreter evaluates the Python code entered at the prompt, as illustrated by the following interaction with the interpreter: 3 + 2 5 3.0 + 2.0 5.0 3 = 2 True The built-in Python function type can be used to find out the type of an object: type(3) type 'int' type(3.0) type 'float' The operators on types int and float are listed in Figure 2.1. • i+j is the sum of i and j. If i and j are both of type int, the result is an int. If either of them is a float, the result is a float. • i–j is i minus j. If i and j are both of type int, the result is an int. If either of them is a float, the result is a float. • ij is the product of i and j. If i and j are both of type int, the result is an int. If either of them is a float, the result is a float. • i//j is integer division. For example, the value of 6//2 is the int 3 and the value of 6//4 is the int 1. The value is 1 because integer division returns the quotient and ignores the remainder. • i/j is i divided by j. In Python 2.7, when i and j are both of type int, the result is also an int, otherwise the result is a float. In this book, we will never use / to divide one int by another. We will use // to do that. (In Python 3, the / operator, thank goodness, always returns a float. For example, in Python 3 the value of 6/4 is 1.5.) • i%j is the remainder when the int i is divided by the int j. It is typically pronounced “i mod j,” which is short for “i modulo j.” • ij is i raised to the power j. If i and j are both of type int, the result is an int. If either of them is a float, the result is a float. • The comparison operators are == (equal), = (not equal), (greater), = (at least), , (less) and = (at most). Figure 2.1 Operators on types int and float The arithmetic operators have the usual precedence. For example, binds more tightly than +, so the expression x+y2 is evaluated by first multiplying y by 2, and then adding the result to x. The order of evaluation can be changed by Chapter 2. Introduction to Python 11 using parentheses to group subexpressions, e.g., (x+y)2 first adds x and y, and then multiplies the result by 2. The operators on type bool are: • a and b is True if both a and b are True, and False otherwise. • a or b is True if at least one of a or b is True, and False otherwise. • not a is True if a is False, and False if a is True. 2.1.2 Variables and Assignment Variables provide a way to associate names with objects. Consider the code pi = 3 radius = 11 area = pi (radius2) radius = 14 8 It first binds the names pi and radius to different objects of type int. It then binds the name area to a third object of type int. This is depicted in the left panel of Figure 2.2. Figure 2.2 Binding of variables to objects If the program then executes radius = 11, the name radius is rebound to a different object of type int, as shown in the right panel of Figure 2.2. Note that this assignment has no effect on the value to which area is bound. It is still bound to the object denoted by the expression 3(112). In Python, a variable is just a name, nothing more. Remember this—it is important. An assignment statement associates the name to the left of the = symbol with the object denoted by the expression to the right of the =. Remember this too. An object can have one, more than one, or no name associated with it. 8 If you believe that the actual value of π is not 3, you’re right. We even demonstrate that fact in Chapter 15. 12 Chapter 2. Introduction to Python Perhaps we shouldn’t have said, “a variable is just a name.” Despite what Juliet 9 said, names matter. Programming languages let us describe computations in a way that allows machines to execute them. This does not mean that only computers read programs. As you will soon discover, it’s not always easy to write programs that work correctly. Experienced programmers will confirm that they spend a great deal of time reading programs in an attempt to understand why they behave as they do. It is therefore of critical importance to write programs in such way that they are easy to read. Apt choice of variable names plays an important role in enhancing readability. Consider the two code fragments a = 3.14159 pi = 3.14159 b = 11.2 diameter = 11.2 c = a(b2) area = pi(diameter2) As far as Python is concerned, they are not different. When executed, they will do the same thing. To a human reader, however, they are quite different. When we read the fragment on the left, there is no a priori reason to suspect that anything is amiss. However, a quick glance at the code on the right should prompt us to be suspicious that something is wrong. Either the variable should have been named radius rather than diameter, or diameter should have been divided by 2.0 in the calculation of the area. In Python, variable names can contain uppercase and lowercase letters, digits (but they cannot start with a digit), and the special character _. Python variable names are case-sensitive e.g., Julie and julie are different names. Finally, there are a small number of reserved words (sometimes called keywords) in Python that have built-in meanings and cannot be used as variable names. Different versions of Python have slightly different lists of reserved words. The reserved words in Python 2.7 are and, as, assert, break, class, continue, def, del, elif, else, except, exec, finally, for, from, global, if, import, in, is, lambda, not, or, pass, print, raise, return, try, with, while, and yield. Another good way to enhance the readability of code is to add comments. Text following the symbol is not interpreted by Python. For example, one might write subtract area of square s from area of circle c areaC = piradius2 areaS = sideside difference = areaC-areaS Python allows multiple assignment. The statement x, y = 2, 3 binds x to 2 and y to 3. All of the expressions on the right-hand side of the assignment are evaluated before any bindings are changed. This is convenient 9 “What's in a name? That which we call a rose by any other name would smell as sweet.” Chapter 2. Introduction to Python 13 since it allows you to use multiple assignment to swap the bindings of two variables. For example, the code x, y = 2, 3 x, y = y, x print 'x =', x print 'y =', y will print x = 3 y = 2 2.1.3 IDLE Typing programs directly into the shell is highly inconvenient. Most programmers prefer to use some sort of text editor that is part of an integrated development environment (IDE). 10 In this book, we will use IDLE, the IDE that comes as part of the standard Python installation package. IDLE is an application, just like any other application on your computer. Start it the same way you would start any other application, e.g., by double-clicking on an icon. IDLE provides • a text editor with syntax highlighting, autocompletion, and smart indentation, • a shell with syntax highlighting, and • an integrated debugger, which you should ignore for now. When IDLE starts it will open a shell window into which you can type Python commands. It will also provide you with a file menu and an edit menu (as well as some other menus, which you can safely ignore for now). The file menu includes commands to • create a new editing window into which you can type a Python program, • open a file containing an existing Python program, and • save the contents of the current editing window into a file (with file extension .py). The edit menu includes standard text-editing commands (e.g., copy, paste, and find) plus some commands specifically designed to make it easy to edit Python code (e.g., indent region and comment out region). 10 Allegedly, the name Python was chosen as a tribute to the British comedy troupe Monty Python. This leads one to think that the name IDLE is a pun on Eric Idle, a member of the troupe. 14 Chapter 2. Introduction to Python For a complete description of IDLE, see 2.2 Branching Programs The kinds of computations we have been looking at thus far are called straight- line programs. They execute one statement after another in the order in which they appear, and stop when they run out of statements. The kinds of computations we can describe with straight-line programs are not very interesting. In fact, they are downright boring. Branching programs are more interesting. The simplest branching statement is a conditional. As depicted in Figure 2.3, a conditional statement has three parts: • a test, i.e., an expression that evaluates to either True or False; • a block of code that is executed if the test evaluates to True; and • an optional block of code that is executed if the test evaluates to False. After a conditional statement is executed, execution resumes at the code following the statement. Figure 2.3 Flow chart for conditional statement In Python, a conditional statement has the form if Boolean expression: block of code else: block of code In describing the form of Python statements we use italics to describe the kinds of code that could occur at that point in a program. For example, Boolean expression indicates that any expression that evaluates to True or False can follow the reserved word if, and block of code indicates that any sequence of Python statements can follow else:. Chapter 2. Introduction to Python 15 Consider the following program that prints “Even” if the value of the variable x is even and “Odd” otherwise: if x%2 == 0: print 'Even' else: print 'Odd' print 'Done with conditional' The expression x%2 == 0 evaluates to True when the remainder of x divided by 2 is 0, and False otherwise. Remember that == is used for comparison, since = is reserved for assignment. Indentation is semantically meaningful in Python. For example, if the last statement in the above code were indented it would be part of the block of code associated with the else, rather than with the block of code following the conditional statement. Python is unusual in using indentation this way. Most other programming languages use some sort of bracketing symbols to delineate blocks of code, e.g., C encloses blocks in braces, . An advantage of the Python approach is that it ensures that the visual structure of a program is an accurate representation of the semantic structure of that program. When either the true block or the false block of a conditional contains another conditional, the conditional statements are said to be nested. In the code below, there are nested conditionals in both branches of the top-level if statement. if x%2 == 0: if x%3 == 0: print 'Divisible by 2 and 3' else: print 'Divisible by 2 and not by 3' elif x%3 == 0: print 'Divisible by 3 and not by 2' The elif in the above code stands for “else if.” It is often convenient to use compound Boolean expressions in the test of a conditional, for example, if x y and x z: print 'x is least' elif y z: print 'y is least' else: print 'z is least' Conditionals allow us to write programs that are more interesting than straight- line programs, but the class of branching programs is still quite limited. One way to think about the power of a class of programs is in terms of how long they can take to run. Assume that each line of code takes one unit of time to execute. If a straight-line program has n lines of code, it will take n units of time to run. What about a branching program with n lines of code? It might take less than n units of time to run, but it cannot take more, since each line of code is executed at most once. 16 Chapter 2. Introduction to Python A program for which the maximum running time is bounded by the length of the program is said to run in constant time. This does not mean that each time it is run it executes the same number of steps. It means that there exists a constant, k, such that the program is guaranteed to take no more than k steps to run. This implies that the running time does not grow with the size of the input to the program. Constant-time programs are quite limited in what they can do. Consider, for example, writing a program to tally the votes in an election. It would be truly surprising if one could write a program that could do this in a time that was independent of the number of votes cast. In fact, one can prove that it is impossible to do so. The study of the intrinsic difficulty of problems is the topic of computational complexity. We will return to this topic several times in this book. Fortunately, we need only one more programming language construct, iteration, to be able to write programs of arbitrary complexity. We get to that in Section 2.4. Finger exercise: Write a program that examines three variables—x, y, and z— and prints the largest odd number among them. If none of them are odd, it should print a message to that effect. 2.3 Strings and Input 11 Objects of type str are used to represent strings of characters. Literals of type str can be written using either single or double quotes, e.g., 'abc' or "abc". The literal '123' denotes a string of characters, not the number one hundred twenty-three. Try typing the following expressions in to the Python interpreter (remember that the is a prompt, not something that you type): 'a' 34 3'a' 3+4 'a'+'a' The operator + is said to be overloaded: It has different meanings depending upon the types of the objects to which it is applied. For example, it means addition when applied to two numbers and concatenation when applied to two strings. The operator is also overloaded. It means what you expect it to mean when its operands are both numbers. When applied to an int and a str, it duplicates the str. For example, the expression 2'John' has the value 11 Unlike many programming languages, Python has no type corresponding to a character. Instead, it uses strings of length 1. Chapter 2. Introduction to Python 17 'JohnJohn'. There is a logic to this. Just as the expression 32 is equivalent to 2+2+2, the expression 3'a' is equivalent to 'a'+'a'+'a'. Now try typing a 'a''a' Each of these lines generates an error message. The first line produces the message NameError: name 'a' is not defined Because a is not a literal of any type, the interpreter treats it as a name. However, since that name is not bound to any object, attempting to use it causes a runtime error. The code 'a''a' produces the error message TypeError: can't multiply sequence by non-int of type 'str' That type checking exists is a good thing. It turns careless (and sometimes subtle) mistakes into errors that stop execution, rather than errors that lead programs to behave in mysterious ways. The type checking in Python is not as strong as in some other programming languages (e.g., Java). For example, it is pretty clear what should mean when it is used to compare two strings or two numbers. But what should the value of '4' 3 be? Rather arbitrarily, the designers of Python decided that it should be False, because all numeric values should be less than all values of type str. The designers of some other languages decided that since such expressions don’t have an obvious meaning, they should generate an error message. Strings are one of several sequence types in Python. They share the following operations with all sequence types. The length of a string can be found using the len function. For example, the value of len('abc') is 3. Indexing can be used to extract individual characters from a string. In Python, all indexing is zero-based. For example, typing 'abc'0 into the interpreter will cause it to display the string 'a'. Typing 'abc'3 will produce the error message IndexError: string index out of range. Since Python uses 0 to indicate the first element of a string, the last element of a string of length 3 is accessed using the index 2. Negative numbers are used to index from the end of a string. For example, the value of 'abc'-1 is 'c'. Slicing is used to extract substrings of arbitrary length. If s is a string, the expression sstart:end denotes the substring of s that starts at index start and ends at index end-1. For example, 'abc'1:3 = 'bc'. Why does it end at index end-1 rather than end? So that expressions such as 'abc'0:len('abc') have the value one might expect. If the value before the colon is omitted, it defaults to 0. If the value after the colon is omitted, it defaults to the length of the string. Consequently, the expression 'abc': is semantically equivalent to the more verbose 'abc'0:len('abc'). 18 Chapter 2. Introduction to Python 2.3.1 Input Python 2.7 has two functions (see Chapter 4 for a discussion of functions in Python) that can be used to get input directly from a user, input and 12 raw_input. Each takes a string as an argument and displays it as a prompt in the shell. It then waits for the user to type something, followed by hitting the enter key. For raw_input, the input line is treated as a string and becomes the value returned by the function; input treats the typed line as a Python expression and infers a type. In this book, we use only raw_input, which is less likely to lead to programs that behave in unexpected ways. Consider the code name = raw_input('Enter your name: ') Enter your name: George Washington print 'Are you really', name, '?' Are you really George Washington ? print 'Are you really ' + name + '?' Are you really George Washington? Notice that the first print statement introduces a blank before the “?” It does this because when print is given multiple arguments it places a blank space between the values associated with the arguments. The second print statement uses concatenation to produce a string that does not contain the superfluous blank and passes this as the only argument to print. Now consider, n = raw_input('Enter an int: ') Enter an int: 3 print type(n) type 'str' Notice that the variable n is bound to the str '3' not the int 3. So, for example, the value of the expression n4 is '3333' rather than 12. The good news is that whenever a string is a valid literal of some type, a type conversion can be applied to it. Type conversions (also called type casts) are used often in Python code. We use the name of a type to convert values to that type. So, for example, the value of int('3')4 is 12. When a float is converted to an int, the number is truncated (not rounded), e.g., the value of int(3.9) is the int 3. 2.4 Iteration A generic iteration (also called looping) mechanism is depicted in Figure 2.4. Like a conditional statement it begins with a test. If the test evaluates to True, the program executes the loop body once, and then goes back to reevaluate the test. This process is repeated until the test evaluates to False, after which control passes to the code following the iteration statement. 12 Python 3 has only one command, input. Somewhat confusingly, Python 3’s input has the same semantics as raw_input in Python 2.7. Go figure. Chapter 2. Introduction to Python 19 Figure 2.4 Flow chart for iteration Consider the following example: Square an integer, the hard way x = 3 ans = 0 itersLeft = x while (itersLeft = 0): ans = ans + x itersLeft = itersLeft - 1 print str(x) + '' + str(x) + ' = ' + str(ans) The code starts by binding the variable x to the integer 3. It then proceeds to square x by using repetitive addition. The following table shows the value associated with each variable each time the test at the start of the loop is reached. We constructed it by hand-simulating the code, i.e., we pretended to be a Python interpreter and executed the program using pencil and paper. Using pencil and paper might seem kind of quaint, but it is an excellent way to 13 understand how a program behaves. test x ans itersLeft 1 3 0 3 2 3 3 2 3 3 6 1 4 3 9 0 The fourth time the test is reached, it evaluates to False and flow of control proceeds to the print statement following the loop. For what values of x will this program terminate? If x == 0, the initial value of itersLeft will also be 0, and the loop body will never be executed. If x 0, the initial value of itersLeft will be greater than 0, and the loop body will be executed. 13 It is also possible to hand-simulate a program using pen and paper, or even a text editor.

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.