CSC 15 Midterm Exam Study Guide Topics to be covered: Difference between statements and expressions; type of expressions, 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. In particular, know the difference between a string and an array of characters. 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. Algorithms: binary search, finding the largest value, etc... Two's Complement binary 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 hash tables/association lists (not on this tests) What to study: Class notes Sample programs I've wrote in class, many of which are on the webpage Past quizzes and labs The extra practice problems and their solutions posted on the webpage 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 (these are in addition to the ones that were on the "extra practice problems"; they may a bit more difficult). Sample solutions will be posted later. 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, # note , at the end y = y+1 # inner while print "" 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 characters into lower case characters. 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. 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 the following base-10 integers in 8-bit two's complement form: a. 34 b. -34 12. Write a function that takes a base-10 positive integer and output it in binary form. 13. (harder) Write a function that takes a binary string such as "00110100" as an argument and return the integer that it represents. For example, value("00110100") should return 52 and value("1111") should return -1. The bits can vary.