15-112 Spring 2013 Midterm 1

* 80 Minutes.
* No calculators, no notes, no books, no computers.
* Show your work, circle your answers.

1. [5 pts; 1 pt each] True or False (circle one):

a. TRUE or FALSE: For any positive integers x and y, (x%y)/y cannot be positive.

b. TRUE of FALSE: For large integers N, we would expect binary search over a list of N sorted elements to run faster than testing whether N is prime using fasterIsPrime.

c. TRUE or FALSE: Polya’s main contribution was his famously efficient sorting algorithm.

d. TRUE or FALSE: For any 2d List L, if a=copy.copy(L) and b=copy.deepcopy(L), then a[0] cannot be an alias to b[0].

e. TRUE or FALSE: Style guidelines are mainly for novice programmers; experts rarely adhere to them.

2. [24 pts; 3 pts each] Very Short Answers:
Answer each of the following with only a few words or numbers. Really, do not write long answers!

a.    Assuming n>0, what is the big-oh runtime of f(n):
def f(n):
   a = range(0,3*n,3)
   for x in range(n):
       if (x in a):
           print x

b. Say we invent a new hybrid sort that works like this: given a list with N elements, it uses selectionsort to sort the first half, and then selectionsort to sort the second half, and finally it uses merge (from mergesort) to merge the two sorted halves. What is the big-oh runtime of this sort?

c. Say that selectionsort on a random list with 2 million elements takes 2 seconds. About how long would you expect the same computer to selectionsort a random list with 10 million elements?

d. Given a list L with N elements, fill in the blank with a single expression, not a statement and not a function, so b is True if L contains all the integers from 1 to N (in any order) and False otherwise.

b = ______________________________________________________________

e. For any positive integers x and y with x>y, if (x > (x/y*y)), what must be true about x and y?

f. What is the key observation we used to make fasterIsPrime so much faster than isPrime?

g. Why do we use a while loop instead of a for loop in nthPrime?

h. Our wordSearch function called a helper function repeatedly, and that helper function called yet another helper function repeatedly. Very briefly describe both of those helper functions’ purposes.

3. [15 pts; 3 pts each] Code Tracing. Indicate what each will print:

Statement(s):	Prints:
s = "a\nbc\td" * 2 print len(s), s[2:4], s
(w, x, y) = (1, 22, 5) while (x%y > w): for z in xrange(y,15,4): print z, print (x,y) (w, x, y) = (w+1, x-5, y+2)
a = [4.56, 5.67, 6.78] for i in xrange(len(a)): fmt = "%" + ("%d.%df" % (i, i+1)) print fmt % a[i],
s = "2ec3d" for c in s: if (c.isdigit()): c = chr(ord('c') + int(c)) else: c = s[ord(c) - ord('c')] print c,
def f(a): (i,x) = (1,len(a[0])) for b in a: if (i < x): b[i] += 1 print b[i%x], i += 1 a = [[2,4],[6,8]] f(a) print a

4. [10 pts] Short Free Response: drawCircleInRect
Write the function drawCircleInRect that takes a canvas and four ints – cx, cy, width, height. Your function should draw an unfilled blue outline of a rectangle centered at (cx, cy) with the given width and height. Then, draw a filled red circle that is centered in the left half of the blue rectangle. Make the circle as large as possible without extending beyond the left half of the blue rectangle.

5. [16 pts; 4 pts each] Reasoning about code
For each of the functions f, find values of the parameters so that f will return True. Circle your answers.

def fa(x, y):
    return ((100>x>y>0) and
            (x/y**2 == 10) and
            (x+y == 99))

import string
def fb(s):
    assert(type(s) == type("s"))
    t = string.ascii_uppercase[1:6]
    return (s[0:len(s):2] +
            s[-2:0:-2] == t)

def fc(a):
    assert(type(a) == list)
    assert(len(a) == 5)
    assert(a.count(0) == 1)
    i = 0
    while (a[i] != 0):
        (oldi, newi) = (i, a[i])
        assert(abs(newi - oldi) > 1)
        (a[oldi], i) = (0, newi)
    return (a == [0]*len(a))

def fd(L):
    assert(len(L) == 1+len(L[0]) == 3)
    k = 0
    # note the funny order of
    # the next two lines
    for j in xrange(len(L[0])):
      for i in xrange(len(L)):
            assert(L[i][j] == k)
            k += 1
    return True

6. [15 pts] Free Response: nearestHumdrum
We will say that an int value is humdrum if it is positive and contains no odd digits. Write the function nearestHumdrum(n) (and any helper functions it requires), that takes an int value n and returns the nearest humdrum number to n, with ties going to the lower value, so nearestHumdrum(34) returns 28 and not 40.

7.       [15 pts] Free Response: quizAverage
We can store a table of quiz scores in a 2d list, where each row is a different student and each column is a different quiz. For example:
   [ [ 52, 74, 90 ],
     [ 71, 88, "NS" ]
   ]
This table includes two students who took 3 quizzes. Student 0 scored 52 on quiz 0, 74 on quiz1, and 90 on quiz2. If a student did not take a quiz, the score is entered as “NS” for “No Score”. With this in mind, write the function quizAverage(scores, student) which takes a 2d list of scores, as just described, and the index of a student, and returns the quiz average for that student subject to these constraints:
(1) “NS” scores do not affect any averages.
(2) The quiz with the lowest course-wide average is dropped for every student.
(3) After that, each student’s lowest remaining quiz is also dropped.
(4) Averages are rounded to the nearest tenth.
If the student id is out of range, or if the student has no average (because there are no scores remaining after doing steps 1-4), then return None.

Bonus/Optional: [2.5 pts] Very short Answer: In mergesort, each time we merged, we combined two sorted lists into one larger sorted list. What if we modified merge to combine three sorted lists instead? This is doable, but would it change the big-oh runtime? To earn points, you must (very briefly but clearly) say why or why not.

Bonus/Optional: [2.5 pts] In just a few words of plain English, in general, for what values of n does f(n) return True?
def f(n):
    j = k = 0
    for d in xrange(1,n+1): k += (n%d==0)
    for d in xrange(2,k): j += (k%d==0)
    return k/(k+1) == j*k