CSC 15 Midterm Exam Study Guide Topics to be covered: Different kinds of statements and expressions; type of expressions (integer, float, string), but especially boolean expressions. if-else statements and while loops. Nested if-else and while loops Use of Array/Lists. Know how to use the built-in array operations including 'append', 'pop', +, 'len' and 'in'. Understand the difference between destructive and non-destructive operations. Understand the difference between pre-initializing arrays using expressions such as [0]*n and using .append. Use of strings and tuples, how they differ from arrays Basic functions such as ord, chr, str and int (which converts a string to an integer). How to define and call functions Local variables of functions***. How to define for-all and there-exists types of loops Basic operations on arrays and strings involving loops and nested loops. Binary numbers, bitwise operations, the log functions, the % operator Algorithms: binary search, finding the largest value, swap sort, etc... (if covered in time): converting between bases, association lists, hexadecimal numbers. Topics that will NOT be covered on the exam: File IO (the only IO you need to know is "print") Use of graphical (gtk) routines such as brush.drawline, etc ... for loops What to study: Class notes Sample programs I've wrote in class, many of which are on the webpage Past quizzes and labs Additional Hints: Concentrate on topics/examples that we have covered more than once. Topics I've only mentioned in passing have a lesser chance of being tested. On the test, don't leave a question blank; usually I give partial credit. ------------- Most of the problems on the exam are similar to the ones that you've already seen on the quizzes and labs. You will be asked to write some code, including some functions. One or two questions on the exam will be specially designed to be challenging. ------------- Sample Questions. Sample solutions will be posted later. These are in addition to the extra practice problems already posted. 1. For each line below, determine its value or describe what it does if it has no value (statement as opposed to expression). Assume the following function definition def f(n): return n*n a. S+"C" # assume S is a string variable b. A.append("C") # assume A is an array (what's the difference between this and the expression in part a?) c. f(f(2)) # (hint: read inside-out) 2. Determine the output of the following program fragment: x = 1 y = 2 def f(x) x = x+y return x # end f def g(x) y = x+1 x = y # end g print(f(x)) x = f(x) print(x) g(x) # note this call is a statement since g doesn't return anything print(x, y) 3. Determine the output of the following program fragment: x = 10 while x>0: y = 1 while y<=x: print(y,end="") # prints y without newline y = y+1 # inner while print("") # prints new line x = x - 2 # read this line carefully #outer while print(x,y) # don't forget this line! 4. Write a function 'interleave' that constructs the interleave of two arrays. For example, interleave([1,3,7,9],[4,8,16,32]) should return the array [1,4,3,8,7,16,9,32]. The the two array parameters are not of the same length, you should just return the empty array []. 5. Two arrays are disjoint if they share no common element. Write a function to test for this property. For example, disjoint([1,4,2],[5,0,3,8]) should return True because they share no common element. The empty array is considered disjoint from all other arrays. 6. A list is sorted if all elements are in order. For example, [4,7,2,8] is not sorted because 2 should come before the 4. Write a function sorted(A) that returns True/False depending on whether A is sorted. Hint: you need to write a loop that checks that A[i]<=A[i+1] for each index i. Unlike the "usual" case however, your loop will have to stop one index sooner: both i and i+1 must be <= len(A). Additional hint: think about whether this is a "for all" or "there exists" type of property. 7. (a little harder) Write a function 'duplicate' to determine if an array contains a duplicate entry (an element that appears more than once). For example, duplicate([4,5,2,4,1]) should return True and duplicate(["abc","def","ghi"]) should return False. hint: you may want to first define a function that counts the number of times an element occurs in an array. 8 (similar to problem 6). Write a function 'pivot' that returns the index of the first element in an array that's not in order (not sorted). If all elements are in order, then return -1. For example, pivot([3,6,7,2,9,4]) should return 3, which is the index of the element 2. This is the element out of order because it's larger than the element (7) preceeding it. pivot([2,4,6,8,9]) should return -1, since all elements are in order. 9. Write a function that takes a string as an argument and return the same string but with all upper case letters changed to lower case. Upper case letters have ascii values in the range ord('A') to ord('Z') and lower case letters have ascii values from ord('a') to ord('z'). Hint: rebuild the string one character at a time, add 32 to the ascii value of upper chase chars to get the ascii value of lower case chars 9b. Write a function that calls the function above, and which determines if two strings are equal regardless of upper/lower case. For example, calling yourfunction("aBc","ABc") should return True. 10. Explain why binary search requires an array to be sorted. What would happen if binary search is used on an array that's not sorted. 11. Write a function that checks if a number is a prime number (returns true or false) 12. Write a function that finds all the prime factors of a number, that is, all prime numbers that evenly divide the number. For example, the prime factors of 20 are 2 and 5. 13. Write a version of the binary search function that, instead of returning just True or False, will return the index of where the value was found, or -1 if the value was not found. For example, binsearchi(4,[1,3,4,7]) should return 2, and binsearchi(3,[1,4,8]) should return -1. 14. The following function converts a (non-negative) integer n into base-8 form, where each digit has value 8**n power. For example, base_8(19) will return "0o23", which is the base-8 representation of 19 because 19 = 2*8**1 + 3*8**0 (2*8 + 3) def base_8(n): # returns string representation of integer n in base 8: answer = "" while n>0: digit = n%8 answer = str(digit)+answer n = n//8 # shifts bits in n three positions to the right return "0o"+answer Write the inverse function that takes a string in base 8 and return the integer that it represents.