CS201 Final Study Guide I. Basic Linux Commands a. cd – change directory b. mkdir – make directory c. ls – show contents of directory II. Variables in Python d. Variables do not need to be declared e. Must start with a letter or “_” i. can contain numbers f. **variable names are case sensitive! ii. Use camel case: 1. newValue 2. studentAverage 3. setAverageGrade g. Initializing a variable: iii. 3 2 1 iv. variable = value h. Order of Operations: v. HIGHEST PRIORITY: not ** vi. * / % vii. + - viii. < <= > >= ix. == != x. and xi. LOWEST PRIORITY: or III. Python Data Types (int, float, strings, lists, boolean, NoneType) and the type function i. Int – integer numbers: 5, 6, 3, 25, etc. j. Float – decimals: 5.0, 3.50, 25.4, etc. k. String – string of words or a phrase: “Hello World” etc. l. List – a list of values contained within brackets: [1, 4, 3, 25] m. Boolean – True/False n. NoneType IV. Using input, raw_input, and print o. input – lets the user input a number xii. variable = input(“Enter a number: “) p. raw_input – lets the user input a string xiii. variable = raw_input(“Enter a word: “) q. print – prints a statement, etc. xiv. print “Hello World” V. The math and random module r. VI. Lists s. Unlike variables, lists can hold massive amounts of data t. Lists are mutable, meaning they can be changed or modified u. A list can hold only one value per element xv. Index starts at 0, not one 4. The first element in the list is at index 0 v. Lists are heterogeneous xvi. All of the elements can be different types(int, float, string, etc.) w. Creating a list xvii. Lists are identified with [] xviii. Options: 5. Start with an empty list a. >>> myList = [] b. >>> myList c. [] 6. List with initial values d. >>> myList = [“bread”, “milk”, “apples”, “cheese”] e. >>> myList f. [‘bread’, ‘milk’, ‘apples’, ‘cheese’] g. >>> myList.append(“water”) h. >>> myList i. [‘bread’, ‘milk’, ‘apples’, ‘cheese’, ‘water’] 7. In the above example, “bread” is at index 0 and “water” is at index 4 xix. You can place an empty string into a list!! x. Some list methods: xx. listName.append(value) – appends the value to the end of listName xxi. listName.reverse() – reverses the order of items in listName xxii. listName.count(value) – count the occurrences of the value in listName xxiii. listName.extend([list]) – append multiple items to the end of listName xxiv. listName.index(value) – locate the index of the value in listName xxv. listName.remove(value) – removes the first occurrence of the value from listName xxvi. listName.sort() – sorts listName y. Built-in functions that operate on lists: xxvii. len(listName) – count number of items in the list xxviii. del(listName[index]) – remove the item at index from listName VII. Strings z. A string is one or more characters of text strung together xxix. “c” xxx. “Hello” xxxi. “1234567” are all strings. {. Strings are immutable, meaning they cannot be changed or modified |. Creating strings xxxii. When making a string, “” are used xxxiii. Strings start at index 0! [0] | [1] | [2] | [3] | [4] | h | e | l | l | o | 8. var1 = “Hello” }. Accessing characters in a string xxxiv. Strings are sequences 9. Each element contains a character, and when put all together it makes a string xxxv. Assigning values 10. Mut use “” to set if literal j. variable = raw_input(“Please enter… “) reads the whole line typed xxxvi. Can use + to concatenate strings together, but not other types ~. String splicing . String methods/built-in functions xxxvii. string.capitalize() 11. returns a copy of the string with only the first letter capitalized xxxviii. string.upper() 12. returns a copy of the string in all capital letters xxxix. string.lower() 13. returns a copy of the string in all lowercase letters xl. len(string) xli. string.split(c) 14. returns a list of strings made by splitting string on all occurrences of c xlii. string[index] xliii. string.isalpha() 15. returns True if all characters in the string are alphabetic xliv. string.strip() 16. returns a copy of the string with all whitespace removed from the beginning and end of the string . String operators xlv. Concatenation - + 17. Adds to end of string. The new string object wil be the old string and the one you added onto the end of it xlvi. Repetition- * xlvii. Indexing- [ ] xlviii. Slicing- [ : ] 18. Slicing works from the first index specified and up to, but not including the last one. [1:4] will print out characters at indexes 1, 2, and 3, but not 4 [0] | [1] | [2] | [3] | [4] | H | e | l | l | o | 19. >>> string = “Hello” 20. >>> print string[1:4] 21. “ell” . Using a for loop with a string xlix. >>> for i in string: #this basically says to scan l. ... #condition #the string for instances of i VIII. ASCII Table . chr and ord functions li. chr() function converts a number to its corresponding ASCII value 22. >>> chr(104) 23. ‘h’ lii. ord() function converts an ASCII character to its corresponding number value 24. >>> ord(‘h’) 25. 104 IX. Decision-Making . if, elif, else constructs liii. if <condition>: 26. <perform an action> liv. elif <condition>: 27. <perform an action> lv. else: 28. <perform an action> . and, or, not operators lvi. used to join two conditions in if/while statements lvii. if <condition1> and <condition2>: 29. <perform an action> X. Validation . Using while loops for validation lviii. Condition is tested before the body of the loop lix. Loop only runs if the condition is true 30. So ,if you are done with the loop, you want the condition to fail (something will be False) 31. Basically, set a thing = True 32. then, while thing = True: k. what you want the loop to do for when thing = true l. in the end, set the thing to False so the loop ends . try/except blocks lx. Remember how the program will crash if the user puts in any wrong type of input? 33. A try/except structure will catch anything that may cause a crash 34. Will recover from a user error 35. The will contain/recover from errors so as not to end the entire program 36. Used for many things such as: m. File I/O n. Input from the keyboard 37. An error is called an exception 38. try and except are reserved words o. try try to do something that may cause an error p. except catch that error 39. structure is the exact same as an if/elif 40. Types of errors we can detect: q. ZeroDivisionError – divided by zero somewhere r. ValueError – receives an argument that has the right type but an inappropriate value s. NameError – name not found t. TypeError – wrong type 41. You can use several exceptions in the same try XI. Functions . A function is a procedure to complete a specialized task, no matter how small or large lxi. A package of code . Functions can be run any number of times you want . How to define functions lxii. Functions are sequential – start from the top and end at the bottom 42. Declare variables at the beginning of the function so you can use later lxiii. def functionName(): 43. To define a function . Arguments/parameters lxiv. What outside info does the function need in order to work? lxv. Formal parameters 44. Variables listed in a function definition 45. Variables that are local to a function 46. Contain a copy of the actual parameter’s value lxvi. Actual parameters (also called arguments) 47. Variables that are used in the function calls as parameters 48. Values are passed as a copy 49. Variables are part of some other scope . Passing a mutable object vs. an immutable object into a function lxvii. Mutable 50. Can change values when passed into another function lxviii. Immutable 51. Cannot change values when passed into another function lxix. Simple data types in python are immutable 52. Ints, floats, strings lxx. Complex data types are mutable 53. Lists, dictionaries, sets, etc. lxxi. If parameters are assigned an immutable value (e.g. a number), they can be assigned other values in the function. However, when the function completes, the original arguments retain their original values. That is, the change inside the function does not stay. lxxii. If parameters are assigned a mutable value (e.g. a list), they can be assigned other values in the function. Whatever changes you make to the list in the function will stick! 54. You do not have to return the same list back! . Return values XII. Local, Global Variables . Global variables lxxiii. “live” and can be accessed throughout the entire file lxxiv. Is not declared within any function, but rather, outside of them . Local Variables lxxv. Is declared within a function lxxvi. live and die in the function that it was created lxxvii. Can only be accessed by that function XIII. File I/O . Used to read/open files into the program . open() function lxxviii. open(“<filename>”, “<action>”) lxxix. open() takes two arguments: 55. The first is a string that represents the system path to the file you want to open and the filename. The path can be either an absolute full system path to the file, or it can be a relative path with respect to the directory where the program is running. 56. The second argument specifies what you want to do with the file. This is called the mode. You can either read(“r”), write(“write”), append(“a”), or read and write(“r+”): u. “r” – reads the file v. “w” – write to the file i. Used to create a new file and write into it w. “a” – append data to an already existing file. If a file already exists with the same name, then anything we write to the file will be appended to the file, after the previously existing data. ii. Unlike write mode, it appends data to the file after any previously existing data. x. “r+” – allows you to read and write to a file. iii. When using this mode, you can read through a file until you find the place where you want to start writing, and then write to the file. iv. However, in this mode, when you write to the file, what is written has to be exactly the same length as the original text that gets replaced, if it is to leave the remainder of the file unchanged. This behavior severely limits the usefulness of this mode. . readline/write methods lxxx. To read a line from the file, you use the command file.readline(). This command will return a string representing the next line of text in the file. Whenever a file.readline() command is issued, the file variable will set its position in the file to the next line. This means that subsequent calls to file.readline() will return the line after the last one that was returned. 57. If you try to read a line when there are no more lines in the file, the file.readline() statement will just return an empty string. 58. If you want to remove the new line character you can use the string method strip() y. file.readline().strip() 59. if you want to do processing on every single line in a file, python gives us a much easier way to do this using a ‘for’ loop z. >>> file = open(“file.txt”, “r”) {. >>> for line in file: |. ... line }. ... ~. ‘This is line 1\n’ . ‘This is line 2\n’ . ‘This is line 3\n’ . close method lxxxi. You should always close the file when you’re finished using it! lxxxii. file.close() XIV. Loops . for and while loops . Nested loops . Uses of loops lxxxiii. Validation lxxxiv. Menu Loop lxxxv. Sentinel Loop lxxxvi. Accumulator Loops lxxxvii. Loops for File I/O XV. Top-Down Design . What is it? lxxxviii. Top-Down Design is a way of programming that helps increase the efficiency and organization of the programmer when writing code. lxxxix. It starts with looking at the problem as the big picture, and then simplifies it by breaking it down into smaller problems to solve one at a time. . How do you use it? xc. It’s helpful to write out all of the function names and what they’re supposed to do, and then further breaking them down into smaller functions that will all come together to solve the problem. xci. When using top-down design, you want to write functions as stubs . What are the benefits? xcii. It increases efficiency and organization of the programmer xciii. It makes the code look better/more organized. Rather than just having one large function that does everything, you can break it down into smaller parts and solve the problem one part at a time. XVI. Random() and randrange() functions XVII. Sets . The Set Object xciv. A set is an unordered collection of items xcv. Duplicates are not allowed 60. If there are duplicates, they’re ignored xcvi. Items in the set are immutable (cannot be changed) . Common Operators/Methods for Sets xcvii. in – checks to see if an element is in a set xcviii. == - checks is a set is equal to another set . Built-In Functions xcix. len(set) – count the number of items in the set . Methods for Sets c. issubset(set) – determine if the set is a subset of another one 61. example: x.issubset(y) 62. Does x have duplicates of ALL of its elements in y? Is x a subset of y? ci. issuperset(set) – determine if the set is a superset of another 63. reverse of issubset cii. add(item) – adds an item to a set ciii. remove(item) – removes an item from a set civ. clear() – remove everything from the set cv. copy() – copies a set, and returns that copy cvi. Set operations (on multiple sets) 64. union(set) – create a union with another set . unifies both sets 65. intersection(set) – create an intersection with another set . Consists of everything that is common to both sets 66. difference(set) . Order is important!! . x.difference(y) – what does x have that y doesn’t? XVIII. Dictionaries . Also called Associative Arrays . Uses tuples of key-value pairs cvii. Tuples = grouping of data cviii. One key per value KEYS | VALUES | “John” | “Biology” | “Joe” | “CS” | “Susan” | “Math” | 67. However, a key can have a list of multiple values . dict = {“key:[value1, value2, value3]} a. Uses “keys” cix. Think of a key as an index cx. Immutable cxi. Keys are in random order cxii. students = {“John”: “Biology”, “Joe”: “CS”, “Susan”: “Math”} b. Common operators/methods cxiii. has_key(key) method 68. >>> students.has_key(“Joe”) 69. True cxiv. get(key) method – find the value associated with the key 70. >>> students.get(“John”) 71. ‘Biology’ cxv. get(key, default) – use a default value when a key isn’t found cxvi. keys() method 72. >>> names = students.keys() 73. >>> names 74. [‘John’, ‘Joe’, ‘Susan’] cxvii. values() method 75. >>> majors = students.values() 76. >>> majors 77. [‘Biology’, ‘CS’, ‘Math’] cxviii. copy() method 78. >>> temp = students.copy() 79. >>> temp 80. {‘John’: ‘Biology’, ‘Joe’: ‘CS’, ‘Susan’: ‘Math’} cxix. clear() method 81. >>> students.clear() 82. >>> students 83. {} 84. >>> temp 85. {‘John’: ‘Biology’, ‘Joe’: ‘CS’, ‘Susan’: ‘Math’} c. Built-in functions cxx. len cxxi. del XIX. Classes and Objects . Strings and lists are examples of some object we have been using throughout the semester . We now want to create our own custom objects cxxii. In order to do this, we first need to define a class . How to design a class cxxiii. A class defines a new type and contains: 86. Instance variables (called member variables in some languages) 87. Methods (functions that can be called by using instances of the class) cxxiv. A class can be thought of as a template or a blueprint cxxv. Once you define a class, you can create instances of the class 88. An object is an instance of a class cxxvi. What you need to define a class: 89. Constructor . A constructor is a shortcut method that fills values into an INSTANCE . Called __init__ . Called as soon as you create an instance . You should only have one __init__ method per class . Constructors are placed INSIDE the class they belong to 90. Accessors . “get” member values for instance variables v. Method names start with “get” . Does not change member variable values . Methods do not (usually) have parameters 91. Mutators . “set” or edit member values for an object vi. Method names start with “set” . Used to change member variable values . Can have error checking code 92. Other necessary methods . How to create an object . What are methods? cxxvii. In addition to accessors and mutators, your class can also have additional custom methods. cxxviii. These custom methods are like stand-alone functions (i.e. they need a name, can have parameters and return values), but they are called by objects using dot notation 93. s1.display() . What is self? cxxix. Used for identification cxxx. Self identifies the INSTANCE/OBJECT 94. Sets the value to “my” member variable 95. Remember “=” . Read right to left . Using = with objects cxxxi. Looks like copying data from one instance to another, but it’s actually just an alias. Any changes affect the original XX. cmp function . used to create your own sorting mechanism cxxxii. you may be given a task where sorting is more complicated >>> cmp(5, 3)1>>> cmp(5, 5)0>>> cmp(5, 7)-1 | cxxxiii. by Python default the cmp function is used cxxxiv. cmp function 96. returns 1, 0, -1 . How does it work? XXI. Sorting user-defined objects XXII. Stacks . Just a list!! cxxxv. You can still use the normal list methods (len, remove, etc.) . Stacks are an abstract data type for storing and retrieving data elements . Stack provides temporary storage in such a way that the data element stored last will be retrieved first (LIFO) cxxxvi. FILO – first in, last out 97. Like a stack of plates . The last plate you put on top is the first one to be taken off the stack 98. Operations are performed only at the top of the stack . Elements can be “pushed” or “popped” from the top cxxxvii. Push – stackName.push(element) cxxxviii. Pop – stackName.pop() . Top – prints the first element on top of the stack cxxxix. top() . Common problems with stacks cxl. Stack underflow 99. No elements in the stack, and you tried to pop an element cxli. Stack overflow 100. Maximum elements in a stack, and tried to add another 101. Not an issue using Python unless you run out of memory! XXIII. Queue . Just a list!! cxlii. You can still use the normal list methods (len, remove, etc.) . Queue is a data structure for storing and retrieving data elements . Queue provides temporary storage in such a way that the data stored first will be retrieved first (FIFO) . FIFO – first in, first out cxliii. Like a drive-thru window – the first to go in is the first to leave . Data processed from the beginning of the queue(“dequeued”) and new data added at the end of the queue(“enqueued”) . Enqueue cxliv. queueName.enqueue(element) . Dequeue cxlv. queueName.dequeue() . Peek XXIV. List of lists and queue of queues XXV. Linear/Binary Searching . Linear Search cxlvi. Linear search is considered an O(n) algorithm cxlvii. How does it work? 102. Starts from the beginning of the list, and one by one, searches for the target . Once it finds the target, returns the index where the target is presented 103. This can take a while if you have a large list cxlviii. Best case? 104. The value you are searching for is the first element – O(1) Best Case | O(1) | Average Case | O(n) | Worst Case | O(n) | 105. In this case, it only makes one comparison cxlix. Average case? cl. Worst case? 106. The value you’re searching for is the last element . Binary Search cli. Binary search is considered an O(log2n) algorithm clii. How does it work? 107. Given a list of numbers ALREADY SORTED and in ASCENDING ORDER 108. Searches for a value and returns the index Best Case | O(1) | Average Case | O(log2n) | Worst Case | O(log2n) | 109. Define Middle: . ALWAYS INT value of vii. (min_index + max_index)/2 viii. Size = 13, then middle = 6 ix. Size = 4, then middle = 2 110. Compare target with MIDDLE index highlighted 111. Redefine (reset) Left or Right sections of the list (if not target), repeat cliii. Best case? 112. Target that you’re searching for is the first element cliv. Average case? clv. Worst case? 113. Target that you’re searching for is the last element XXVI. Sorting: Bubble, Selection, Insertion, Mergesort, Quicksort . Decorate, sort, undecorated for lists clvi. Needed for unconventional sorting (unnatural ordering) 114. Longest words 115. number of occurrences of a value 116. etc… clvii. we can create a “decorated” list that contains: 117. count of unconventional order 118. original value . Bubble Sort clviii. Bubble sort is an O(n2) Sort 119. Not efficient 120. Remember n is the number of elements to be sorted 121. Note: if you double the size of the input, you would expect the time to increase by a factor of 4 clix. How does it work? 122. Compare 1st and 2nd items; if they’re out of order, swap. Now, compare 2nd and 3rd items…continue until end, (called a “pass”), then redo again until there are no more swaps to be done Best Case | O(n) | Average Case | O(n2) | Worst Case | O(n2) | clx. Best case? 123. The data is already sorted . Only passes through the list once clxi. Average case? clxii. Worst case? . Selection Sort clxiii. Selection sort is an O(n2) Sort clxiv. How does it work? 124. Finds the smallest element in the list and swaps it with the first element (pass) Best Case | O(n2) | Average Case | O(n2) | Worst Case | O(n2) | 125. Then start again until n-1 passes 126. Even if the data is sorted, is does the same amount of work as if the list is not sorted. . Insertion sort clxv. Insertion sort is an O(n2) Sort clxvi. How does it work? 127. Starts form the smallest, to the largest 128. Looks at the next element, and places it in the correct ordered spot, in all of the previous elements checked already. 129. Think of it as a deck of cards – each one you draw you immediately put in order Best Case | O(n) | Average Case | O(n2) | Worst Case | O(n2) | clxvii. Best case? clxviii. Average case? clxix. Worst case? . Mergesort, Quicksort clxx. Mergesort 130. Considered O(n logn) which is faster than O(n2) 131. Recursive 132. Needs extra memory 133. How it works: . Split the list into two equal halves, and places them in separate lists. Each list is recursively sorted, then merged back together to form the final sorted list.

clxxi. Quicksort 134. Considered O(n logn) which is faster than O(n2) 135. Averages a faster time than other sorts 136. Does not require extra memory 137. Good cache performance 138. Good parallel performance 139. It is possible for it to be O(n2) in the worst case (e.g. if you pick the pivot as the first value and the list is already sorted) 140. Recursive 141. How it works: . Pick a pivot. Get all values smaller than the pivot on left of the pivot and all the values greater than the pivot on the right of it. Use recursion to sort the left and the right. XXVII. Command line arguments . What is sys.argv? XXVIII. Recursion . What is it? clxxii. A recursive definition is one which refers to itself as in the factorial and Fibonacci functions. clxxiii. Function calls itself 142. Each time the function calls itself, it gets a new set or parameters and local variables 143. The parameters and local variables from a previous call to the recursive function will still be preserved, on the call stack, until the function returns from the previous call. 144. Recursion can also occur indirectly by the invocation or a function that invokes the function that invoked it (e.g. A calls B which calls A…) 145. Recursion is an alternative to iteration. . Recursion can often provide a more elegant and a simpler solution compared to iteration . Recursive solutions are often less efficient than an iterative one . Some problems are difficult to solve without recursion (e.g. when the problem involves processing a recursively defined data structure) . How does it work? clxxiv. Recursion requires the following: 146. BASE CASE – there exists one or more simple solutions to the problem 147. GENERAL RULE – other cases of the problem can be expressed in terms of one or more reduced cases of the problem (i.e. closer to the known simple solutions) 148. Eventually the problem can be reduced to one of the simple solutions . Be able to analyze a recursive function XXIX. Binary search tree . Know how to make one . Inorder, preorder, postorder transversals XXX. Coupling, cohesion . Routine – a programming unit that performs a task, such as a function, procedure, method, or main class. (ex. getValidInt, append) . Module – a collection of objects that are logically related, such as constants, data types, variables, routines. . Component – a routine or module. In python, can also be an object or class. . Program structure clxxv. Every component should be clear about what it’s inputs and outputs are. clxxvi. This makes it so higher-level functions can use the lower-level functions, knowing that they will accomplish their intended goal. clxxvii. Examples of lower-level functions you have written are things such as getValidInt, enqueue, dequeue, pop, push, etc. clxxviii. This leads to component independence. . Component Coupling (the bad) clxxix. Coupling terminology: 149. Tightly coupled - many components rely on each other 150. Loosely coupled - some weak dependencies 151. Uncoupled - no connections clxxx. Our goal is always to MINIMIZE coupling. clxxxi. Ways things can be coupled: 152. One component calling another 153. One component passing data to another component clxxxii. Types of coupling 154. Content coupling – component directly modifying the control flow of another component. Very poor programming practice. 155. Common coupling – modifying a common data structure from different components. Accomplished by global variables. 156. Control coupling – Booleans or other controls passed between components. Passing of control flags as component parameters. Unnecessary way to program, and should be avoided. New components should be created to avoid this. 157. Stamp coupling – data structures (such as lists or stacks) are passed between components. Not as bad as previous kinds of coupling, but still not ideal and can often be eliminated. 158. Data coupling – primitive data is passed between components. Not a bad thing; as a matter of fact, it’s how functions are called that pass parameters. Minimizing this can be difficult and is unnecessary. . Component Cohesion clxxxiii. Coincidental cohesion – component parts are unrelated clxxxiv. Logical cohesion – logically related task in same component clxxxv. Temporal cohesion – performs tasks in sequence related by timing clxxxvi. Procedural cohesion – tasks grouped together to ensure mandatory ordering clxxxvii. Communicational cohesion – functions produce the same data set clxxxviii. Sequential cohesion – output from one function is input to next clxxxix. Functional cohesion – every processing element is essential to the function