15-112 Fall 2012 Quiz 6a (Autograded)
45 minutes

Read these instructions first!

• This quiz is SOLO.
• This portion is worth 75 pts.  The written portion tomorrow will be worth 25 pts.
• No notes, books, web sites (except reading this quiz and accessing Autolab).
• IDLE hint:  python -m idlelib.idle &
• Autolab hint (to submit):  http://autolab.cs.cmu.edu/
• You must submit your quiz6.py file to Autolab before leaving the lab!  You will not have access to this file after you leave the lab!
• To start, download this one file: quiz6.py
• The private autograder you have is "very nearly" the final version.  We will keep the same tests worth the same points, but the constants will be changed when we autograde after the quiz so you cannot just hardcode the answers.
• You may use up to 5 submissions during the quiz, though (as always) your last submission is the only one that counts.  Obviously, you may not submit nor resubmit after you leave the lab (do not attempt to do so, even if Autolab for some reason allows it).
• Good luck! :-)

1. alternatingSum [25 pts]
2. repeatingPattern [25 pts]
3. transpose [25 pts]
4. bonus/optional: mulitiplyPolynomials [2.5 pts bonus]

1. alternatingSum [25 pts]
   Write the function alternatingSum(a) that takes a list of numbers and returns the alternating sum (where the sign alternates from positive to negative or vice versa).  For example, alternatingSum([5,3,8,4]) returns 6 (that is, 5-3+8-4).
    
2. repeatingPattern [25 pts]
   Write the function repeatingPattern(a) that takes a list a and returns True if a == b*k for some list b and some value k>1, and False otherwise.  For example, repeatingPattern([1,2,3,1,2,3]) returns True (b==[1,2,3] and k=2).
    
3. transpose [25 pts]
   While we probably would not do this, we could represent a 2d list of numbers as a triple:  (rows, cols, values), where we first include the dimensions and then we include a 1d list of the values as read from top-to-bottom and then left-to-right.  For example, consider this 2d list:
     5  8  1
     0  7  4
   This has 2 rows and 3 columns, so we would represent this as:  (2, 3, [5, 8, 1, 0, 7, 4]).  Now, the transpose of a 2d list is constructed by swapping rows and columns.  For example, the transpose of the list above is this list:
     5  0
     8  7
     1  4
   This would be represented as (3, 2, [5, 0, 8, 7, 1, 4]).  With this in mind, write the function transpose(L) that takes a triple L representing a 2d-list as just described, and returns another triple representing the transpose of that list.
   
   Note that a "triple" is a tuple, not a list, with 3 elements.  So transpose takes one parameter, but that parameter is a triple containing 3 values.
    
4. bonus/optional:  mulitiplyPolynomials [2.5 pts bonus]
   Background:  we can represent a polynomial as a list of its coefficients.  For example, [2, 3, 0, 4] could represent the polynomial 2x³ + 3x² + 4.  With this in mind, write the function multiplyPolynomials(p1, p2) which takes two polynomials as just defined and returns a third polynomial which is the product of the two.  For example, multiplyPolynomials([2,0,3], [4,5]) represents the problem (2x² + 3)(4x + 5), and:
       (2x² + 3)(4x + 5) = 8x³ + 10x² + 12x + 15
   And so this returns [8, 10, 12, 15].

15-112 Fall 2012 Quiz 6b (non-autograded)

* 15 Minutes.  No calculators, no notes, no books, no computers.
* 25 pts (5 problems, 5 pts each; 5 pts bonus).  (The other 75 points are on the autograded quiz5a)

What will the following print?

def f1(a):
    b = [ ]
    for i in xrange(len(a)):
        if (i%2 == a[i]%2):
            b.append((i, a[i]))
    return b
print f1([3,5,4,6,7])


def f2(a,b):
    a = a[0:len(a)-1]
    for c in a:
        for i in xrange(len(b)):
            if (b[i] % c == 2):
                b[i] += c
L1 = [3,2]*2
L2 = range(3,9,2)
f2(L1, L2)
print L1, L2
 

What will the following print?

def f3(s):
    d = ord(s[0]) - ord(s[1])
    a = [d]*d
    x = "x"
    for c in s.lower():
        if (c.isalpha()):
            if (abs(ord(c) - ord(x)) <= d):
                a.append(c)
            x = c
    return a
print f3("carpe DIEM!")

For each of the following functions, find values of the parameters so that the functions will return True. 

def f4(a):
    s = a[0]
    return s[a[1]:a[2]/a[1]] == "abc"

def f5(n):
    assert(1000 > n > 0)
    d = 5
    for c in range(50):
        if (str(d) in str(c)):
            if (d == 0):
                return (c == n)
            d -= 1
    return False

Bonus:  What will the following print?

import string
s = string.lowercase[:len(string.lowercase)%16]
def fbonus(x):
    global s
    (s,p,c)=(x.replace(s[-1],str(len(s))),None,0)
    while (p != s): (s,p,c) = (eval(s),s,1+c)
    return "%s is %d!" % (s[s.rfind('sh'):],c)
print fbonus("""s[j:] or s.replace('ab','sh') #about time""")

carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem