15-112 Spring 2013 Homework 5
Due Monday, 18-Feb, at 9pm

Read these instructions first!

Some Review Practice Problems (variables, expressions, loops, conditionals, strings)

  1. nearestHarshadNumber
    Background:  A Harshad Number is a positive integer with at least two digits that is divisible by the sum of its digits.  The first several Harshad numbers are:  10, 12, 18, 20, 21, 24, 27, 30, 36, 40, 42, ...  With this in mind, write the function nearestHarshadNumber(n) that takes an integer value n and returns the nearest Harshad number to n, with ties going to the lower number. Thus, nearestHarshadNumber(14) returns 12, since the two nearest Harshad numbers to 14 are 12 and 18, and 12 is nearer.  Also, nearestHarshadNumber(15) returns 12, since ties go to the lower number.  But nearestHarshadNumber(16) returns 18.

1d-List and Tuple Problems
Do not use recursion
Make all your functions non-destructive unless explicitly indicated otherwise.

  1. alternatingSum
    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. mostCommonName
    Write the function mostCommonName, that takes a list of names (such as ["Jane", "Aaron", "Cindy", "Aaron"], and returns the most common name in this list (in this case, "Aaron"). If there is more than one such name, return a list of the most common names, in alphabetical order (actually, in whatever order sorted() uses). So mostCommonName(["Jane", "Aaron", "Jane", "Cindy", "Aaron"]) returns the list ["Aaron", "Jane"]. If the list is empty, return None.  Also, treat names case sensitively, so "Jane" and "JANE" are different names.
     
  3. reverse
    Write the function reverse(a) that destructively reverses the list a.  So if a equals [2,3,4], then after reverse(a), a should equal [4,3,2].  As is generally true of destructive functions, this function does not return a value (well, technically it returns None, but Python does that for you).
     
  4. vectorSum
    Write the function vectorSum(a,b) that takes two same-length lists of numbers a and b, and returns a new list c where c[i] is the sum of a[i] and b[i].  For example, vectorSum([2,4],[20,30]) returns [22, 34].
     
  5. isSorted
    Write the function isSorted(a) that takes a list of numbers and returns True if the list is sorted (either smallest-first or largest-first) and False otherwise.  Your function must run in O(n) time, where n=len(a), and so you may  not sort the list.
     
  6. duplicates
    Write the function duplicates(a) that takes a list (which your function must not modify) of unsorted values and returns a sorted list of all the duplicates in that first list. For example, duplicates([1, 3, 5, 7, 9, 5, 3, 5, 3]) would return [3, 5] If there are no duplicates, return an empty list.  If n=len(a), your function may run in O(nlogn) time, but not in O(n2) time.
     
  7. dotProduct
    Background:  the “dot product” of the lists [1,2,3] and [4,5,6] is (1*4)+(2*5)+(3*6), or 4+10+18, or 32.  In general, the dot product of two lists is the sum of the products of the corresponding terms.  With this in mind, write the function dotProduct(a,b).  This function takes two lists and non-destructively returns the dotProduct of those lists.  If the lists are not equal length, ignore the extra elements in the longer list.
     
  8. isRotation
    Write the function isRotation(a1, a2) that takes two lists, a1 and a2, and returns True if a2 is a rotation of a1 and False otherwise.  For example, [2,3,4,5,6] is a rotation of [4,5,6,2,3].  A list is a rotation of itself.

10.  Reasoning About Code  [30 pts; 2.5 pts each]

For each of the following functions, find values of the parameters so that the functions will return True.  You should assume that x, y, and z are ints, and that s is a string.  Hint:  reason your way through this.  How you find your answer is just as important, if not more so, than what the answer is!  While you may confirm your answer by running it in a Python interpreter, do not use the Python interpreter at all when solving the problem.  You will be given similar problems such as these on written quizzes without access to Python interpreters!  Also, consider only the possible inputs.  For example, if you are given that x+y==16, since x>y>0, we only need consider (15,1), (14,2), ..., (9,7).  That's only 7 (x,y) points in total, one of which must be correct!

import string
def f1(s):
    assert((type(s) == str) and (len(s) == 5))
    i = 0
    for j in xrange(len(string.ascii_lowercase)):
        if (j % len(s) == 0):
            assert(s[i] == string.ascii_lowercase[j])
            i += 1
            if (i == len(s)):
                return True
    return False

import copy
def f2(a):
    assert(sorted(a) == range(5,9))
    b = copy.copy(a)
    for i in xrange(len(b)):
       b[len(b)-1-i] *= i
    return ((b[0] == 18) and (min(a) == b[2]) and (a[1] > a[3]))

# Hint:  (a << b) is the same as (a * (2**b))
#  and:  (a >> b) is the same as (a / (2**b))
def f3(x, y):
    return ((100>x>y>0) and
            (y == 1 << (x/10)) and
            ((y<<(x/10)) + x == 100))

def f4(s):
    assert(type(s) == str)
    t = "CBBD"
    for i in xrange(4):
        assert(s.count(s[i]) ==
               (ord(t[i]) - ord("A")))
    return (s[::3] == s[5:2:-1])
 

def f5(y):
    x = 28
    while (x > 0):
        c = 0
        for z in xrange(1,x+1):
            if (x % z == 0):
                c += 1
        if (c == 2):
            return (x == y)
        x -= 1
    return (2*y == -y)
 

def f6(n):
    assert(type(n) == int)
    m = 1
    for x in xrange(10*1000):
        r = 1
        for c in str(x):
            r *= (ord(c) - ord("5"))
        if (r == 6):
            m = x
    return (n == m)


def f7(n,k,x):
    s = "ab\tc\\d"
    assert(len(s) == n)
    assert(s[k] in string.whitespace)
    assert(s.find("b") == s.find("e") + x)
    return True

def f8(fmt):
    # string formatting, you supply the format string!
    s1 = fmt % (2, 3.56)
    assert (s1 == "+2abc3.6")
    s2 = fmt % (-2, 3.4)
    assert (s2 == "-2abc3.4")
    return True

def f9(s):
    assert (s[0] == "d" and len(s) == 5)
    for i in xrange(1, len(s)):
        if (ord(s[i]) != (i + ord(s[i-1]))):
            return False
    return True

def f10(s,t):
    return (t[2] == str(len(t))) and (s[1:len(s)] == t[4:0:-1])

def f11(a):
    assert(len(a) == 8)
    s = 0
    for i in xrange(0, 8, 2):
        assert(a[i] > s)
        s += a[i]
        assert(str(s) == a[i+1])
    return True

def f12(a):
    b = sorted(a)
    assert(b == range(len(a)))
    i = a.index(b[1])
    return (b[1:6:2] == a[i:i+3])


11.  True or False: [10 pts; 1 pt each; 11a is bonus]
Be sure to include a very brief explanation as to WHY it is True or False.

a.    (bonus) TRUE or FALSE:  For any non-negative integers x and y, (x|y) >= max(x,y).

b.   TRUE or FALSE:  For any integers x and y and z, if (x > y) is True, then ((x % z) > (y % z)) is True.

c.    TRUE or FALSE:  In general, for loops run faster than while loops.

d.   TRUE or FALSE:  We would expect fasterIsPrime(N**2) to run in about the same time as isPrime(N).

e.   TRUE or FALSE:  If we changed mergesort so that instead of merging halves of the list, it merged thirds of the list, this would not change the big-oh runtime, which would still be O(NlogN).

f.     TRUE or FALSE:  Polya’s “How to Solve It” explains how to use math, mainly algebra, to solve a variety of problems, and serves as our basis for our big-oh theory of run-time analysis.

g.    TRUE or FALSE:  Selectionsort can be faster than mergesort in some cases.

h.   TRUE or FALSE:  In Eck’s xSortLab simulator, a bar turns black when it is about to be swapped.

i.      TRUE or FALSE:  When we create a string and then no longer use it, the string becomes garbage, and Python automatically detects this situation and reuses the memory that the string used.

j.     TRUE or FALSE:  The Google Python Style Guide is similar to but distinct from the Official PEP-8 Python Style Guide written by Guido van Rossum.


12.  Very Short Answers [10 pts; 2 pts each]
Answer each of the following with only a few words or numbers.  Longer answers will be incorrect.

a.    Using different-height bars for values (as in xSortLab), sketch what a list with 8 elements would probably look like if we are halfway done sorting using mergesort (as it works in xSortLab).
 

b. Assuming f(s,t) takes two non-empty strings, rewrite the following function so that it works the same way only it does not use a loop or recursion.
def f(s,t):
   for i in xrange(len(t)):
       if (t[i] != s[i%len(s)]): return False
   return (len(t) % len(s) == 0)

 

c.    On a certain computer, running binary search on a random sorted list with 1 thousand elements takes 2 milliseconds.  About how long would you expect the same computer to run binary search on a random sorted list with 1 billion elements?
 

d.   Assuming n is a positive integer, what is the big-oh runtime of each of these functions:
def fa(n):
    count = 0
    for x in xrange(len(str(n))):
       for y in xrange(n, n/2, -3):
           count += 1
    return count

def fb(n):
    count = 0
    for x in xrange(1, n*100000, n*0.00001):
        count += 1
    return count

def fc(n):
    rows = n
    cols = n*n
    count = 0
    for row in xrange(rows):
        for col in xrange(cols):
            count += 1
        count += 1
    return count

def fd(n):
    x,y,count1,count2 = n,1,0,0
    while (x > 1): (x,count1) = (x/5,1+count1)
    while (y < n): (y,count2) = (count1+y,1+count2)
    return count2

e.   In just a few words, explain what short-circuit evaluation is in Python.


Bonus/Optional:  subsetSum
Write the function subsetSum(a) that takes a list of int values and returns a list of indexes i0, i1, ..., ik, in increasing order, such that a[i0] + a[i1] + ... + a[ik] equals 0.  If no such list exists, return None.  For example, subsetSum([2,5,-13,-6,4,3]) could return [0,3,4] since a[0]+a[3]+a[4] == 2+-6+4 == 0.  There may be more than one valid answer for any given list, in which case your function may return any one of them.  To solve this, you will want to use the technique we discussed in class:  if n=len(a), iterate a counter from 0 to 2n, then each of these values of the counter corresponds to a unique subset in the powerset of a, where element a[i] is in the subset if the ith bit of the counter is set to 1.

Bonus/Optional Graphics:
  Read this carefully!  The following problems are bonus/optional.  They are graphical, and you should be certain to place them (and any helper functions they require) below the #ignore_rest line in your hw6.py submission.  Unlike the autograded problems, the bonus graphics problems will be graded only in person on Monday or Tuesday night at office hours.  To get your bonus graphics grade, go to office hours where you should download your submitted code (and it must be just as submitted, with no modifications), run it and show the CA the result.  The CA will grade your bonus at that time, mainly visually but also by looking at the code as needed.

Bonus/Optional:  Radial and Spiral Tilings [2 pts]
Write a function that draws either this picture or this picture from this page on Radial and Spiral Tilings.

Bonus/Optional:  Logarithmic Spiral Tilings [3 pts]
Write a function that draws any one of this picture or this picture or this picture from this page on Logarithmic Spiral Tilings.


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