Lecture 1 - DePaul University



CSC 401 NotesYosef MendelsohnPseudocodePseudocode is a method by which we try to explain our algorithm (our strategy for solving a problem). An algorithm is sometimes simply displayed a flowchart or written description but is often does not specify any particular programming strategy in mind. Pseudocode is where we take our algorithm and our desired programming language and put them together. Pseudocode is meant to be written in plain “spoken” language, but at the same time, should look somewhat like programming code. In other words, you are still writing a description in words, but your words should LOOK a lot like a program – even though that program would never run in Python. For example, you can indicate the name of variables that you might choose, you might indicate the header of the function you are writing, you might use the words ‘for’, ‘return’, ‘if’ etc. Unless the problem you are working on is very trivial, you should always, always, always, invest some time to think about your strategy and then write out the pseudocode for it. I can not emphasize this point enough! It is a natural temptation to just start coding and then hope you can sort of ‘hone in’ on the solving the problem. While this does (usually) work eventually, I promise you that this approach will nearly always end up costing you more time at the end. One of the best ways to save yourself time and frustration, is to get in the habit of going through the following process:Strategize out the problem so that you can come up with an algorithmWrite out the pseudocode that incorporates your Python knowledgeStart coding based on your pseudocodeI am going to ask you to provide pseudocode for some of your assignments. Let’s try out this process using the following problem: Write a function arithmetic() that takes a list of integers and returns True if they form an “arithmetic progression”. An arithmetic progression is one in which the difference between adjacent items of the list is always the same. For example the progression: 2, 9, 16, 23, 30 is an arithmetic progression since the difference between each value in the collection is 7. It would be used as follows:>>> arithmetic([3, 6, 9, 12, 15])True>>> arithmetic([3, 6, 9, 11, 14])FalseRemember the process:AlgorithmPseudocodeCodeAlgorithm:Check the difference between the first two numbers in the list. Note: We should proably take the absolute valueContinue through all of the remaining numbers in the list. If any of them are different from the first two numbers, return false.If we make it through all of them and the difference is always the same, return true, otherwise return false.Pseudocode:def arithmetic(someList):diff = absolute value of (second item – first item)for second item in someList through remainder of someList:calculate difference between current item with following item, and get absolute valueif this difference != diff, then immediately return FalseIf we make it through the above loop and never find a ‘False’, return TrueCode: def arithmetic(lst): if len(lst) < 2: #Probably a wise thing to check for! return False diff = abs(lst[0] - lst[1]) for i in range(len(lst)-1): #a counter loop if abs(lst[i] - lst[i+1]) != diff: return False return TrueAside: You will notice that we use indices (i.e. the values inside square brackets) to refer to items in the collection. We will return to this topic shortly. Do it – Really!Again, you really, really, really, want to get in the habit of going through this process. I promise you that you will find it is going to make your coding lives much easier if you start pushing yourelves to take this approach to solving your coding problems. NOTE: It is absolutely acceptable to return to any earlier step if and when you get stuck. For example, you may be in your pseudocode phase and realize that there is a flaw in your strategy (algorithm). Or you may be coding and realize there is an issue in your pseudocode – or even that there is an issue all the way back in your algorithm. This is very common and entirely acceptable! But recognizing these issues, and making adjustments earlier on is far easier trying to solve bugs in the code that turn out not to be bugs at all – but rather a flaw in strategy or choice of coding approach. Here is a page with a pretty good discussion of pseudocode: Review: write() function:The write() function is is used to output information to a file. Important: The write() function will only accept strings!fout = open('output.txt','w')name = 'Bob'age = 44fout.write(name) #no problem: name is a stringfout.write(age) #ERROR! age is not a stringfout.write( str(age) ) #Solved!A much better option is to use format strings!fout.write('{} is {} years old.'.format(name, age))In fact, format strings are useful pretty much everywhere! Keep practicing with them…Review: str.split() function:The split() function is powerful and important. Review the help notes for it.As an example, suppose someone hands you a "csv" file. CSV stands for "comma separated values". CSV is a file in which all of the values are separated by commas. Many, many datasets available from the government and other sources are supplied in CSV format. One nice thing about CSV files is that you can open them in any text editor. That is, you don't need Excel or other specialized software. See: split_example.pyNOTE: This file requires: exam_grades_small.csvWe are going to use this split() function quite a lot – so be sure to practice using it!IterationSometimes we need to repeat a block of code multiple times, which we achieve by using a loop.There are various forms of loops. Each type of loop has situations where it is best suited relative to other types of loops. We will begin with a review of the only loop we’ve seen so far, the 'for' loop. We will then discuss some looping patterns and their usage. Finally, we will add an additional looping structure to our toolbox: the 'while' loop.Loop patterns: Iteration loopsThe simpes pattern of for loop is one in which we iterate through an explicit, ordered sequence of items and performing some action for each item.In the following example, the for loop iterates over a list, (i.e. a collection of items that has an order) and printing each of the elements:>>> for i in [‘hi’,’bye’,’lisa’]:print(i) hibyelisaIn the following example, the for loop iterates over a range (i.e. using the range() function), printing the elements::>>> for i in range(4):print(i) 0123A for loop can also iterate over the characters in a string:>>> word = "Puccini">>> for character in word:if character in "aeiou":print(character)uiiIn general, a for loop has the following structure:for <var> in <sequence>:<body>In other words, a for loop requires a variable, a sequence, and a body: <var> is a variable that we will typically refer to in the body of the loop. <sequence> is an object whose type is one of the sequence types (e.g. string, list, etc.). It contains an ordered collection of items.<body>, of course, refers to the body of the loop that will get executed each time.When Python runs a for loop, it will assign each value in <sequence> to <var> one at a time. For each value, the loop will execute the statements in <body>.FILES: Another example of using loops is when working with files. The following code example opens the file ‘example.txt’ for reading, and then reads and prints the contents of the file. At this point, we have read in files and iterated through them by using one of two techniques:Reading in the file and assigning the entire contents of the text into a string.Reading in the file as a list of lines.Let’s review the first approach – it should be very familiar to you at this point:We will read in the file as one long string. We will then iterate through the string character by character, and print each one.Recall that when iterating through a string using a for loop, the loop uses each character in the string one at a time.def f1(): infile = open(example.txt', 'r') strContents = infile.read() for character in strContents: print(character, end="") #why the ‘end’ parameter?infile.close()Now let’s review the second version where we read in the contents as a list of lines. We will then we iterate through the list:def f2(): infile = open(example.txt', 'r') lstContents = infile.readlines() for line in lstLines: print(line) infile.close()Loop patterns: Counter loopsOne special but important (i.e. commonly used) case of the iteration loop pattern is the iteration over a list of consecutive integers.A simple reason for doing this might be to do some action on a sequence of integers.For example, we might want to output all even numbers from 0 up to, but not including, some integer 'n':>>> n = 10>>> for i in range(n):if i%2 == 0:print(i, end=" ")0 2 4 6 8Note: Just a friendly reminder: When you use the range() function, the number that you provide as the argument is not included in the list of numbers. For example, range(3) will give 0, 1, and 2. This is also the case when you use forward indexing/slicing via the ':' character. E.g. [2:5] gives 2, 3, and 4. Pop-Quiz: What if, in the previous example, you wanted to include the value of n? How would you change the code?Answer: Simply change range(n) to range(n+1)IMPORTANT: A very common reason to iterate over a sequence of consecutive integers is to generate index values (k/a "indices") of values in a list or characters in a string.Consider a simple loop example:>>> lstAnimals = ['cat', 'dog', 'chicken']>>> for animal in lstAnimals:print(animal)catdogchickenInstead of iterating through the values of this list 'lstAnimals', we could iterate through the indices of 'lstAnimals' and achieve the same thing:>>> for i in range(len(lstAnimals)):print(lstAnimals[i])catdogchickenNote how the range and len functions are used to generate the list [0, 1, 2], i.e., the list of valid indices of lstAnimals.Initially this might seem more complicated and less intuitive than using a simple for loop to move through elements of a list. So why would we use it?In programming, it frequently will make more sense to iterate through a sequence by index location.For example, consider the problem of checking whether a list of numbers 'lst' is sorted in non-decreasing order.To do this, it suffices to check whether each item in the list is greater than or equal to the previous item. Doing this without using indices seems tricky:>> for i in lst:# Each time through the list, # 'i' is holding the current value in the list# How do we compare 'i' with the previous item in the list??The problem here is that while ‘i’ is always holding the current item in the list, we don’t have a way to easily determine the previous value in the list.If we iterate through the list by index, doing this comparison becomes much clearer:>>> for i in range(len(lst)):if lst[i-1] > lst[i]:print(‘The list is not in sorted order’)So in this case, while lst[i] accesses the current item in the collection as we are iterating through, the lst[i-1] allows us to access the previous item in the collection.Bug Alert! This is certanly an improvement, and it does pretty mch solve the problem. However…. there is a bug in the code. Did you spot it?When we are looking at the the first element, that is i = 0, we will compare lst[-1] with lst[0]. But, of course, lst[-1] is not what we wish to compare with!Let's fix this. One way would be to start counting at 1:>>> for i in range(1, len(lst)):if lst[i-1] > lst[i]:print(‘lst is not in sorted order’)Here is one version of this solution:def isSorted(lstOfNums): for index in range(1, len(lstOfNums) ): if lstOfNums[index-1] > lstOfNums[index]: print('The list is not in sorted order.')l1 = [0,2,7,-3,14]isSorted(l1)l2 = [-3,0,2,7,14]isSorted(l2)Practice problem Let’s rewrite our arithmetic() function using a loop with indices. Recall that this function should take a list of integers and returns the value True if the values form an arithmetic progression (i.e. the difference between adjacent items of the list is always the same). If they do not, it should return the boolean value False.Reminder: It should return the boolean value True not the string 'True' !It would be used as follows:>>> arithmetic([3, 6, 9, 12, 15])True>>> arithmetic([3, 6, 9, 11, 14])FalseCode:def arithmetic(lstNums): #get the difference of first two items diff = lstNums[1]-lstNums[0] #for every item in the remainder of the list, #confirm that they all have the same 'diff' #The moment one is different, return False for i in range(2, len(lstNums)): if lstNums[i]-lstNums[i-1]!=diff: return False #If we reach this point, then we have gone through the #entire list without finding a different 'diff' #Therefore, return True return True l3 = [3,6,9,12,15]print(arithmetic(l3))l4 = [3,6,9,11,14]print(arithmetic(l4))Character encoding and stringsFor many years the standard encoding for characters in the English language was the ASCII encoding. ASCII defines a numeric code for 128 characters, punctuation, and a few other symbols common in the American English language. For example, the letter 'A' is represented by 65, 'B' by 66, 'a' by 97, a dollar sign by 36, and so on. Here is a link to an ASCII table: includes two built-in functions to manipulate ASCII encoding:The function ord() takes as a parameter a character and returns the ASCII encoding of the character:>>> ord('a')97>>> ord('+')43The function chr() is the inverse function of ord(). It takes as a parameter a numeric code and returns the character corresponding to it:>>> chr(97)'a'>>> chr(45)'-'Problem 1: Write a function encoding() that takes a string as a parameter and prints the ASCII code of every character in it.It would be used as follows:>>> encoding('dad')100 97 100 >>> encoding('mom')109 111 109def encoding(string): for ch in string: print( ord(ch) )#Test:someString = "hello"encoding(someString)Problem 2: Write a function charCodes(low, high) that prints the characters corresponding to ASCII decimal code i for all values of i from low up to and including high. Try it as follows:>>> charCodes(62,67)>?@ABdef charCodes(low,high): for i in range(low,high): print( chr(i))charCodes(62,67) #TestObjectsThis is a very brief introduction to what we mean when we discuss “objects”. We will be returning to it later in the course as well in considerably more detail. In Python, every value, whether a simple integer value (like 3) or a more complex value (such as the list [‘hello’, 4, 5]) is stored in memory as something called an object.Objects are extremely important in nearly every programming language in common use. We will introduce a few key concepts today and will build on them in subsequent lectures. Every Python has:A type that indicates what kind of values the object can hold – this is important because the type determines what kind of operations are valid for the object.A value, This refers to the contents or the data stored inside the object.To illustrate the difference, consider the following examples:>>> type(3)<class 'int'>>>> type(3.0)<class 'float'>>>> type('hello')<class 'str'>>>> type([])<class 'list'>>>> 33>>> 3.03.0>>> 'hello''hello'>>> [][]There are two types of comparisons you can do between objects:Object value comparisons: Compare the values stored inside two objects. Note: To do this, the two objects must be of the same data type. Object identity comparisons: Compare the objects themselves. Note: This is a very important point and will require further discussion.To see how this works, consider some examples.NOTE: Understanding the discussion of objects below will be made much easier – and you will understand the concepts far better -- if you get in the habit of drawing out diagrams of the objects. I will demonstrate in class. Object value comparisonsComparison operators are used to determine the equality between two objects . (NOTE: The two objects must be of the same type) :>>> 3 == 3True>>> 3 == 4False>>> [2, 3, 4] == [2, 3, 4]True>>> [2, 3, 4] == [3]False>>> 3 <= 4 == 4 < 8 != 9True # But I think the REAL take-home point here is that # we should have used parentheses! This code is NOT clear!Object identity comparisonsSuppose we have the following two objects:lst1 = [2,3,4]lst2 = [2,3,4]As you can see, these are two entirely separate variables (objects). However, they do happen to be holding the same values. Therefore, typing:lst1 == lst2will return TrueHowever, suppose we now change one of them slightly:lst2 = [2,3,5]I hope you recognize that at this time, lst1 == lst2would return False.So the comparison operator == compares the "insides" (ie the contents) of two objects and returns True if both objects hold the exact same data.The is operator:Now let's talk about another important operator called isThis operator compares two objects to see if they are pointing to the same data in memory. For example, suppose we create a list as we did earlier: lst1 = [2,3,4]Now let's create 'lst2' but instead of assigning it [2,3,4] explicitly, we will assign it 'lst1': lst2 = lst1In other words, both objects (lst1 and lst2) are pointing to the exact same object. This means that if we were to make a change to lst1, then lst2 would also be changed and vice-versa:lst1 = [2,3,4]lst2 = lst1lst2[0] = -7 #change a value in lst2print(lst1)#would output: [-7, 3, 4]We have already seen that we can compare the contents of two objects using ==.lst1 == lst2However, what if we want to see if two identifiers are referring (pointing) to the same object? To do this, we use the keyword 'is'.lstA = [2,3,4]lstB = [2,3,4]lstC = lstAlstA == lstB #returns TruelstA is lstB #returns FalseNow let's try using the 'is' operator on two variables that point to the same object in memory: lstA is lstC #returns TruelstC is lstA #also returns True Diagram this out!Another example – again, draw these out:>>> a = [3, 4]>>> b = a>>> a == bTrue>>> a is bTrue>>> b is aTrue>>> c = [3, 4]>>> a == cTrue>>> a is cFalseStrange Integer BehaviorI am going to bring a slightly strange bit of behavior up again. (We have touched on this previously). But as with the last time we discussed this, I will tell you that you don’t have to “sweat” this strange integer behavior for now. I am showing it to you, but to be clear, it’s the above discussion that does not involve integers that you should spend your time worrying about and diagramming. We should note one situation where the Python interpreter does something unexpected:>>> a = 2.0>>> b = 2.0>>> a is bFalse #Makes sense -> a and b are not aliases of each other>>> a = 2>>> b = 2>>> a is bTrue #This is unexpected!!In the last example, the Python virtual machine decided, on its own to reuse all integer objects that happen to store the same value. In this case, rather than create a new location in memory to store a separate “copy” of the integer value 2, Python stores one copy of the integer ‘2’ and keeps track of the fact that two different identifiers point to that same object in the computer’s memory. This is a bit unusual – not many languages besides Python do this. Don’t sweat this strange integer behavior right now, but you should be aware of it. We will review it later. Again, for now, focus on the previous examples of comparing object values vs aliases, and don’t worry about the strange behavior that occurs with integers and other immutable data types. I only bring it up since while practicing you will probably encounter this situation, and I don’t want you to be thrown off by this seemingly inconsistent behavior. ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download