15-112 Fall 2012 Homework 6a
Autolab submission due Sunday, 7-Oct, at 10pm

Read these instructions first!

This part of the hw is SOLO. As explained in the course syllabus, you must not discuss these problems or share your code with anyone else except for the course staff and the tutors at Academic Development. This includes students from former semesters (who may indeed have the answers to these problems!).
This portion is worth 50 pts (10 problems at 5pts each).
Be sure to name your functions exactly as specified, and take exactly the same parameters as specified!
There is no starter file nor any public autograder this week. Be sure to write your own test functions!!!

Most of these problems are relatively easier than most homework problems. They are here to give you extra practice at "quiz-style" problems.
Suggested-but-not-required way to do this: To get the most out of this, do this hw under "near-quiz conditions". Try to finish each of these in 10 minutes or less, working alone, without accessing any notes, etc. Even better, do this in the cluster, using IDLE, and then doing only a few at a time.

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

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.

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).
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.
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).
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].
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.
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(n²) time.
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.
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.
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 2ⁿ, 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