INTRO PROGRAMMING EECS 12
Popular in Course
Popular in Electrical Engineering & Computer Science
verified elite notetaker
verified elite notetaker
Marcos Pedro Ferreira Leal Silva
verified elite notetaker
verified elite notetaker
verified elite notetaker
verified elite notetaker
This 25 page Class Notes was uploaded by Anne Ward on Saturday September 12, 2015. The Class Notes belongs to EECS 12 at University of California - Irvine taught by Staff in Fall. Since its upload, it has received 39 views. For similar materials see /class/201878/eecs-12-university-of-california-irvine in Electrical Engineering & Computer Science at University of California - Irvine.
Reviews for INTRO PROGRAMMING
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/12/15
Chapter 8 Lists A list is an ordered set of values where each value is identi ed by an index The values that make up a list are called its elements Lists are similar to strings which are ordered sets of characters except that the elements of a list can have any type Lists and stringsiand other things that behave like ordered setsiare called sequences 81 List values There are several ways to create a new list the simplest is to enclose the elements in square brackets and 2 10 20 so 40 quotspamquot quotbungeequot quotswallowquot The rst example is a list of four integers The second is a list of three strings The elements of a list don t have to be the same type The following list contains a string a oat an integer and mirabile dictu another list quothelloquot 20 5 10 20 A list within another list is said to be nested Lists that contain consecutive integers are common so Python provides a simple way to create them gtgtgt range15 1 2 3 4 82 Lists The range function takes two arguments and returns a list that contains all the integers from the rst to the second including the rst but not including the second There are two other forms of range With a single argument it creates a list that starts at 0 gtgtgt range 10 0 1 2 3 4 5 6 7 8 9 If there is a third argument it speci es the space between successive values which is called the step size This example counts from 1 to 10 by steps of 2 gtgtgt range1 10 2 1 3 5 7 9 Finally there is a special list that contains no elements It is called the empty list and it is denoted I With all these ways to create lists it would be disappointing if we couldn t assign list values to variables or pass lists as parameters to functions We can vocabulary quotamelioratequot quotcastigatequot quotdefenestratequot numbers 17 123 empty 1 print vocabulary numbers empty ameliorate castigate defenestrate 17 123 J 82 Accessing elements The syntax for accessing the elements of a list is the same as the syntax for accessing the characters of a stringithe bracket operator 1 The expression inside the brackets speci es the index Remember that the indices start at 0 print numbers 0 numbers 1 5 The bracket operator can appear anywhere in an expression When it appears on the left side of an assignment it changes one of the elements in the list so the oneeth element of numbers which used to be 123 is now 5 Any integer expression can be used as an index gtgtgt numbers 3 2 gtgtgt numbers 10 TypeError sequence index must be integer 83 List length 83 If you try to read or write an element that does not exist you get a runtime error gtgtgt numbers 2 5 IndexError list assignment index out of range If an index has a negative value it counts backward from the end of the list gtgtgt numbers 1 5 gtgtgt numbers 2 17 gtgtgt numbers 3 IndexError list index out of range numbers 1 is the last element of the list numbers2 is the second to last and numbers 3 doesn t exist It is common to use a loop variable as a list index horsemen quotwarquot quotfaminequot quotpestilencequot quotdeathquot 1 0 while i lt 4 print horsemenEi i i 1 This while loop counts from 0 to 4 When the loop variable i is 4 the condition fails and the loop terminates So the body of the loop is only executed when i is 0 l 2 and 3 Each time through the loop the variable i is used as an index into the list printing the ieth element This pattern of computation is called a list traver sal 83 List length The function len returns the length of a list It is a good idea to use this value as the upper bound of a loop instead of a constant That way if the size of the list changes you won t have to go through the program changing all the loops they will work correctly for any size list 84 Lists horsemen quotwarquot quotfaminequot quotpestilencequot quotdeathquot 1 0 while i lt lenhorsemen print horsemeni i i 1 The last time the body of the loop is executed i is len horsemen 1 which is the index of the last element hen i is equal to lenhorsemen the condition fails and the body is not executed which is a good thing because lenhorsemen is not a legal index Although a list can contain another list the nested list still counts as a single element The length of this list is four spam 1 Brie Roquefort Pol 1e Veq 1 2 3 As an exercise write a loop that traverses the previous list and prints the length of each element What happens if you send an integer to len 84 List membership in is a boolean operator that tests membership in a sequence We used it in Section 710 with strings but it also works with lists and other sequences gtgtgt horsemen war famine pestilence death gtgtgt pestilence in horsemen 1 gtgtgt debauchery in horsemen 0 Since pestilence is a member of the horsemen list the in operator returns true Since debauchery is not in the list in returns false We can use the not in combination with in to test whether an element is not a member of a list gtgtgt debauchery not in horsemen 1 85 Lists and for loops The for loop we saw in Section 73 also works with lists The generalized syntax of a for loop is 86 List operations 85 for VARIABLE in LIST BDDY This statement is equivalent to i 0 while i lt lenLIST VARIABLE LISTEi BODY i i 1 The for loop is more concise because we can eliminate the loop variable i Here is the previous loop Written With a for loop for horseman in horsemen print horseman It almost reads like English For every horseman in the list of horsemen print the name of the horseman Any list expression can be used in a for loop for number in rangelt20 if number Z 2 print number for fruit in quotbananaquot quotapplequot quotquincequot print quotI like to eat quot fruit quotsquot The rst example prints all the even numbers between zero and nineteen The second example expresses enthusiasm for various fruits 86 List operations The operator concatenates lists a 1 2 3 gtgtgt b 4 5 6 gtgtgt c a b gtgtgt print 2 1 2 3 4 5 6 Similarly the operator repeats a list a given number of times 86 Lists gtgtgt 0 4 1 2 3 1 2 3 1 2 3 The rst example repeats 0 four times The second example repeats the list 1 2 3 three times 87 List slices The slice operations we saw in Section 74 also work on lists gtgtgt list a b c d e f gtgtgt list13 b 6 gtgtgt list4 Ia1 1b ICI Idi gtgtgt list3 Idl lei Ifl gtgtgt list Ia1 1b ICI Id lei Ifi 88 Lists are mutable Unlike strings lists are mutable which means we can change their elements Using the bracket operator on the left side of an assignment we can update one of the elements gtgtgt fruit quotbananaquot quotapplequot quotquincequot gtgtgt fruit 0 quotpearquot gtgtgt fruit 1 quotorangequot gtgtgt print fruit pear apple orange With the slice operator we can update several elements at once gtgtgt list a b c d e f gtgtgt list13 x y gtgtgt print list a zxz zyz zdz zez Ifi We can also remove elements from a list by assigning the empty list to them 89 List deletion 87 gtgtgt list a b c d e f gtgtgt list13 1 gtgtgt print list Ia1 Id lei Ifl And we can add elements to a list by squeezing them into an empty slice at the desired location gtgtgt list a d f gtgtgt list11 b 6 gtgtgt print list zaz zbz zcz zdz zfz gtgtgt list44 e gtgtgt print list a zbz zcz zdz zez Ifi 89 List deletion Using slices to delete list elements can be awkward and therefore errorprone Python provides an alternative that is more readable del removes an element from a list gtgtgt a one two three gtgtgt del a1 one three As you might expect del handles negative indices and causes a runtime error if the index is out of range You can use a slice as an index for del gtgtgt list a b c d e f gtgtgt del list15 gtgtgt print list a f As usual slices select all the elements up to but not including the second index 88 Lists 810 Objects and values If we execute these assignment statements a quotbananaquot 0quot quotbananaquot we know that a and b will refer to a string with the letters quotbananaquot But we can t tell whether they point to the same string There are two possible states a gt banana a gt banana b gt quotbananaquot b In one case a and b refer to two different things that have the same value In the second case they refer to the same thing These things have namesithey are called objects An object is something a variable can refer to Every object has a unique identi er which we can obtain with the id function By printing the identi er of a and b we can tell whether they refer to the same object gtgtgt ida 135044008 gtgtgt idb 135044008 In fact we get the same identi er twice which means that Python only created one string and both a and b refer to it Interestingly lists behave differently When we create two lists we get two objects gtgtgt a 1 2 3 gtgtgt b 1 2 3 gtgtgt ida 135045528 gtgtgt idb 135041704 So the state diagram looks like this a and b have the same value but do not refer to the same object 811 Aliasing 89 811 Aliasing Since variables refer to objects if we assign one variable to another both vari ables refer to the same object gtgtgt a 1 2 3 gtgtgtb a In this case the state diagram looks like this a b j 1 2 3 Because the same list has two different names a and b we say that it is aliased Changes made with one alias affect the other gtgtgt b0 5 gtgtgt print a 5 2 3 Although this behavior can be useful it is sometimes unexpected or undesirable In general it is safer to avoid aliasing when you are working with mutable objects Of course for immutable objects there s no problem That s why Python is free to alias strings when it sees an opportunity to economize 812 Cloning lists If we want to modify a list and also keep a copy of the original we need to be able to make a copy of the list itself not just the reference This process is sometimes called Cloning to avoid the ambiguity of the word copy The easiest way to clone a list is to use the slice operator gtgtgt a 1 2 3 gtgtgt b a gtgtgt print b 1 2 3 Taking any slice of a creates a new list In this case the slice happens to consist of the whole list Now we are free to make changes to b without worrying about a 90 Lists gtgtgt b0 5 gtgtgt print a 1 2 3 As an exercise draw a state diagram for a and b before and after this change 813 List parameters Passing a list as an argument actually passes a reference to the list not a copy of the list For example the function head takes a list as a parameter and returns the rst element def headlist return list 0 Here s how it is used gtgtgt numbers 1 2 3 gtgtgt headnumbers 1 The parameter list and the variable numbers are aliases for the same object The state diagram looks like this main numbers 123 Since the list object is shared by two frames we drew it between them If a function modi es a list parameter the caller sees the change For example deleteHead removes the rst element from a list def deleteHeadlist del list 0 Here s how deleteHead is used gtgtgt numbers 1 2 3 gtgtgt deleteHeadnumbers gtgtgt print numbers 2 3 814 Nested lists 91 If a function returns a list it returns a reference to the list For example tail returns a list that contains all but the rst element of the given list def taillist return list1 Here s how tail is used gtgtgt numbers 1 2 3 gtgtgt rest tailnumbers gtgtgt print rest 2 3 Because the return value was created with the slice operator it is a new list Creating re st and any subsequent changes to rest have no effect on numbers 814 Nested lists A nested list is a list that appears as an element in another list In this list the threeeth element is a nested list gtgtgt list quothelloquot 20 5 10 20 If we print list 3 we get 10 20 To extract an element from the nested list we can proceed in two steps gtgtgt elt listESJ gtgtgt e1t0 10 Or we can combine them gtgtgt list3 1 Bracket operators evaluate from left to right so this expression gets the three eth element of list and extracts the oneeth element from it 815 Matrixes Nested lists are often used to represent matrices For example the matrix 1 2 3 4 5 6 7 8 9 92 Lists might be represented as gtgtgt matrix 1 2 3 4 5 6 7 8 9 matrix is a list with three elements where each element is a row of the matrix We can select an entire row from the matrix in the usual way gtgtgt matrix1 4 5 6 Or we can extract a single element from the matrix using the doubleindex form gtgtgt matrix1 1 5 The rst index selects the row and the second index selects the column Al though this way of representing matrices is common it is not the only possibility A small variation is to use a list of columns instead of a list of rows Later we will see a more radical alternative using a dictionary 816 Strings and lists Two of the most useful functions in the string module involve lists of strings The split function breaks a string into a list of words By default any number of whitespace characters is considered a word boundary gtgtgt import string gtgtgt song quotThe rain in Spain quot gtgtgt stringsplitsong The rain in Spain An optional argument called a delimiter can be used to specify which charac ters to use as word boundaries The following example uses the string ai as the delimiter gtgtgt string splitsong ai The r n in Sp n Notice that the delimiter doesn t appear in the list The join function is the inverse of split It takes a list of strings and concate nates the elements with a space between each pair gtgtgt list The rain in Spain gtgtgt stringjoinlist The rain in Spain Chapter 20 Trees Like linked lists trees are made up of nodes A common kind of tree is a binary tree in whic each node contains a reference to two other nodes possibly null These references are referred to as the left and right subtrees Like list nodes tree nodes also contain cargo A state diagram for a tree looks like this tree None None None None To avoid cluttering up the picture we often omit the Nones The top of the tree the node tree refers to is called the root In keeping with the tree metaphor the other nodes are called branches and the nodes at the tips with null references are called leaves It may seem odd that we draw the picture with the root at the top and the leaves at the bottom but that is not the strangest thing To make things worse computer scientists mix in another metaphorithe family tree The top node is sometimes called a parent and the nodes it refers to are its Children Nodes with the same parent are called siblings 206 Trees Finally there is a geometric vocabulary for talking about trees We already mentioned left and right but there is also up toward the parentroot and down toward the childrenleaves Also all of the nodes that are the same distance from the root comprise a level of the tree We probably don t need three metaphors for talking about trees but there they are Like linked lists trees are recursive data structures because they are de ned recursively A tree is either 0 the empty tree represented by None or o a node that contains an object reference and two tree references 201 Building trees The process of assembling a tree is similar to the process of assembling a linked list Each constructor invocation builds a single node class Tree def initself cargo leftNone rightNone selfcargo cargo selfleft left selfright right def strself return str self cargo The cargo can be any type but the left and right parameters should be tree nodes left and right are optional the default value is None To print a node we just print the cargo One way to build a tree is from the bottom up Allocate the child nodes rst left Tree 2 right Tree3 Then create the parent node and link it to the children tree Tree 1 left right We can write this code more concisely by nesting constructor invocations gtgtgt tree Tree1 Tree2 Tree3 Either way the result is the tree at the beginning of the chapter 202 Traversing trees 207 202 I raversing trees Any time you see a new data structure your rst question should be How do I traverse it77 The most natural way to traverse a tree is recursively For example if the tree contains integers as cargo this function returns their sum def totallttree if tree None return 0 return totallttreeleft totallttreeright treecargo The base case is the empty tree which contains no cargo so the sum is 0 The recursive step makes two recursive calls to nd the sum of the child trees When the recursive calls complete we add the cargo of the parent and return the total 203 Expression trees A tree is a natural way to represent the structure of an expression Unlike other notations it can represent the computation unambiguously For example the in x expression 1 2 3 is ambiguous unless we know that the multiplication happens before the addition This expression tree represents the same computation tree The nodes of an expression tree can be operands like 1 and 2 or operators like and Operands are leaf nodes operator nodes contain references to their operands All of these operators are binary meaning they have exactly two operands We can build this tree like this gtgtgt tree Tree Tree1 Tree Tree2 Tree3 208 Trees Looking at the gure there is no question What the order of operations is the multiplication happens rst in order to compute the second operand of the addition Expression trees have many uses The example in this chapter uses trees to translate expressions to post x pre x and in xi Similar trees are used inside compilers to parse optimize and translate programs 204 Tree traversal We can traverse an expression tree and print the contents like this def printTree tree if tree None return print tree cargo printTree tree left printTree tree right In other words to print a tree rst print the contents of the root then print the entire left subtree and then print the entire right subtree This way of traversing a tree is called a preorder because the contents of the root appear before the contents of the children For the previous example the output is gtgtgt tree Tree Tree1 Tree Tree2 Tree3 gtgtgt printTree tree 1 2 3 This format is different from both post x and in x it is another notation called pre x in which the operators appear before their operands You might suspect that if you traverse the tree in a different order you Will get the expression in a different notation For example if you print the subtrees rst and then the root node you get def printTreePostorderlttree if tree None return printTreePostorder tree left printTreePostorder tree right print tree cargo The result 1 2 3 is in post xl This order of traversal is called postorder Finally to traverse a tree inorder you print the left tree then the root and then the right tree 204 Tree traversal 209 def printTreeInorderlttree if tree None return printTreeInorder tree left print tree cargo printTreeInorder tree right The result is 1 2 3 which is the expression in in x To be fair we should point out that we have omitted an important complication Sometimes when we write an expression in in x we have to use parentheses to preserve the order of operations So an inorder traversal is not quite suf cient to generate an in x expression Nevertheless with a few improvements the expression tree and the three recur sive traversals provide a general way to translate expressions from one format to another As an exercise modify printTreeInorder so that it puts parenthe ses around every operator and pair of operands Is the output correct and unambiguous Are the parentheses always necessary If we do an inorder traversal and keep track of what level in the tree we are on we can generate a graphical representation of a tree def printTreeIndentedlttree level0 if tree None return printTreeIndentedlttreeright level1 print level strtreecargo printTreeIndentedlttreeleft level1 The parameter level keeps track of where we are in the tree By default it is initially 0 Each time we make a recursive call we pass leve11 because the child s level is always one greater than the parent s Each item is indented by two spaces per level The result for the example tree is gtgtgt printTreeIndented tree If you look at the output sideways you see a simpli ed version of the original gure 210 Trees 205 Building an expression tree In this section we parse in x expressions and build the corresponding expression trees For example the expression 379 yields the following tree Notice that we have simpli ed the diagram by leaving out the names of the attributes The parser we will write handles expressions that include numbers parentheses and the operators and We assume that the input string has already been tokenized into a Python list The token list for 379 is 11 3 11 7 1 Ha 9 lendi The end token is useful for preventing the parser from reading past the end of the list As an exercise write a function that takes an expression string and returns a token list The rst function we ll write is getToken which takes a token list and an expected token as parameters It compares the expected token to the rst token on the list if they match it removes the token from the list and returns true otherwise it returns false def getTokenlttokenList expected if tokenList 0 expected del tokenList 0 return 1 else return 0 Since tokenLi st refers to a mutable object the changes made here are visible to any other variable that refers to the same object 205 Building an expression tree 211 The next function getNumber handles operands If the next token in tokenList is a number getNumber removes it and returns a leaf node con taining the number otherwise it returns None def getNumber tokenLi st x tokenList0 if typex type 0 return None del tokenList0 return Tree x None None Before continuing we should test getNumber in isolation We assign a list of numbers to tokenLi st extract the rst print the result and print what remains of the token list gtgtgt tokenList 9 11 end gtgtgt x getNumbertokenList gtgtgt printTreePostorderx 9 gtgtgt print tokenList 11 end The next method we need is getProduct which builds an expression tree for products A simple product has two numbers as operands like 3 7 Here is a version of getProduct that handles simple products def getProductlttokenList a getNumberlttokenList if getTokenlttokenList b getNumberlttokenList return Tree a b else return 3 Assuming that getNumber succeeds and returns a singleton tree we assign the rst operand to a If the next character is we get the second number and build an expression tree with a b and the operator If the next character is anything else then we just return the leaf node with a Here are two examp es gtgtgt tokenList 9 11 end gtgtgt tree getProductlttokenList gtgtgt printTreePostorderlttree 9 11 gtllt 21 2 Trees gtgtgt tokenList 9 11 end gtgtgt tree getProductlttokenList gtgtgt printTreePostorderlttree 9 The second example implies that we consider a single operand to be a kind of product This de nition of product is counterintuitive but it turns out to be useful Now we have to deal with compound products like like 3 5 13 We treat this expression as a product of products namely 3 5 13 The resulting tree is With a small change in getProduct we can handle an arbitrarily long product def getProductlttokenList a getNumberlttokenList if getTokenlttokenList b getProduct tokenList this line changed return Tree a b else return a In other words a product can be either a singleton or a tree with at the root a number on the left and a product on the right This kind of recursive de nition should be starting to feel familiar Let s test the new version with a compound product gtgtgt tokenList 2 3 H 5 7 end gtgtgt tree getProductlttokenList gtgtgt printTreePostorderlttree 2 3 5 7 Next we will add the ability to parse sums Again we use a slightly counterin tuitive de nition of sum r us a sum can be a tree with at t e root a product on the left and a sum on the right Or a sum can be just a product 205 Building an expression tree 213 If you are willing to play along with this de nition it has a nice property we can represent any expression without parentheses as a sum of products This property is the basis of our parsing algorithms getSum tries to build a tree with a product on the left and a sum on the rights But if it doesn t nd a it just builds a product def getSumlttokenList a getProduct tokenList if getTokenlttokenList b getSumlttokenList return Tree a b Let s test it with9 11 5 7 gtgtgt tokenList 9 11 5 7 end gtgtgt tree getSumtokenList gtgtgt printTreePostorderlttree 9 11 5 7 We are almost done but we still have to handle parentheses Anywhere in an expression where there can be a number there can also be an entire sum enclosed in parentheses We just need to modify getNumber to handle subexpressions def getNumber tokenLi st if getTokenlttokenList x getSumlttokenList get the subexpression getTokenlttokenList remove the closing parenthesis return x else x tokenList 0 if typex type 0 return None tokenListEOzl 1 return Tree x None None Let s test this code with 9 11 5 7 gtgtgt tokenList 9 11 5 4 7 end gtgtgt tree getSumtokenList gtgtgt printTreePostorderlttree 9 11 5 7 214 Trees The parser handled the parentheses correctly the addition happens before the multiplication In the nal version of the program it would be a good idea to give getNumber a name more descriptive of its new ro e 206 Handling errors Throughout the parser we ve been assuming that expressions are wellformed For example when we reach the end of a subexpression we assume that the next character is a close parenthesis If there is an error and the next character is something else we should deal with it def getNumber tokenLi st if getTokenlttokenList x getSumlttokenList if not getTokenlttokenList raise BadExpressionError missing parenthesis return x else the rest of the function omitted The raise statement creates an exception in this case we create a new kind of exception called a BadExpressionError If the function that called getNumber or one of the other functions in the traceback handles the exception then the program can continue Otherwise Python will print an error message and quit As an exercise nd other places in these functions where errors can occur and add appropriate raise statements Test your code with improperly formed expressions 207 The animal tree In this section we develop a small program that uses a tree to represent a knowledge base The program interacts with the user to create a tree of questions and animal names Here is a sample run 207 The animal tree Are you thinking of an animal y Is it a bird 11 What is the animals name dog What question would distinguish a dog from a bird Can it fly If the animal were dog the answer would be 11 Are you thinking of an animal y Can it fly 11 Is it a dog 11 What is the animals name cat What question would distinguish a cat from a dog Does it bark If the animal were cat the answer would be 11 Are you thinking of an animal y Can it fly 11 Does it bark y Is it a dog y I rule Are you thinking of an animal 11 Here is the tree this dialog builds Can it fly At the beginning of each round the program starts at the top of the tree and asks the rst question Depending on the answer it moves to the left or right child and continues until it gets to a leaf node At that point it makes a guess If the guess is not correct it asks the user for the name of the new animal and a question that distinguishes the bad guess from the new animal Then it adds a node to the tree with the new question and the new animal Here is the code 216 Trees def animal start with a singleton root Treequotbirdquot loop until the user quits while 1 print if not yesquotAre you thinking of an animal quot break walk the tree tree root while treegetLeft None prompt treegetCargo quot quot if yesprompt tree treegetRight else tree treegetLeft make a guess guess treegetCargo prompt quotIs it a quot guess quot quot if yesprompt print quotI rulell continue get new information prompt llWhat is the animal s name quot animal rawinputprompt prompt llWhat question would distinguish a Ks from a Ks quot question rawinputprompt X animalguess add new information to the tree tree setCargo question prompt quotIf the animal were Ks the answer would be quot if yesprompt 39Z animal treesetLeft Treeguess tree setRight Tree animal else tree setLeft Tree animal tree setRight Tree guess The function yes is a helper it prints a prompt and then takes input from the user If the response begins With y or Y the function returns true 208 Glossary 217 def yesques from string import lower ans lowerltrawinputques return ans0 y The condition of the outer loop is 1 which means it will continue until the break statement executes if the user is not thinking of an animal The inner while loop walks the tree from top to bottom guided by the user s responses When a new node is added to the tree the new question replaces the cargo and the two children are the new animal and the original cargo One shortcoming of the program is that when it exits it forgets everything you carefully taught it As an exercise think of various ways you might save the knowledge tree in a le Implement the one you think is easiest 208 Glossary binary tree A tree in which each node refers to zero one or two dependent nodes root The topmost node in a tree with no parent leaf A bottommost node in a tree with no children parent The node that refers to a given node Child One of the nodes referred to by a node siblings Nodes that share a common parent level The set of nodes equidistant from the root binary operator An operator that takes two operands subexpression An expression in parentheses that acts as a single operand in a larger expression preorder A way to traverse a tree visiting each node before its children pre x notation A way of writing a mathematical expression with each oper ator appearing before its operands
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'