Computer Science 15-112, Fall 2012
Class Notes:  Practice (through week 5)

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

1. See hw6a.
    
10. selectionsort, bubblesort, insertionsort
    You should be able to easily write any of these sorts.  For more of a challenge, try mergesort (as it works in David Eck's xSortLab, and not the recursive way) or heapsort (read about it online) or radixsort (ditto).  Save quicksort for when we cover recursion.
     
11. shuffle
    Without using the builtin shuffle, write the function shuffle(a) that takes a list of values and shuffles (randomizes) it.  This can be done efficiently by working left-to-right, and swapping each value in turn with a randomly-selected value lying to the right of it in the list.
     
12. isPalindromicList
    Write the function isPalindromicList(a) that takes a list and returns True if it is the same forwards as backwards and False otherwise.
     
13. missingNumber
    Write the function missingNumber(a) that takes an unsorted list of size n that contains all but one of the integers from 1 to (n+1).  Return the missing number.  Your function must run in O(n) time, so it cannot sort the list.
     
14. histogram
    Write the function histogram(a) that takes a list of integers between 0 and 100, inclusive, representing exam scores, and returns a string representing a histogram of that data.  The details can be gleaned from this example:
    histogram([73, 62, 91, 74, 100, 77]) returns this multi-line string:
    60-69: *
    70-79: ***
    80-89:
    90++ : **
     
15. nearestWords
    Write the function nearestWords(wordlist, word) that takes a sorted wordlist and a single word (all words in this problem will only contain lowercase letters).  If the word is in the wordlist, then that word is returned.  Otherwise, the function returns a list of all the words (in order) in the wordlist that can be obtained by making a single small edit on the given word, either by adding a letter, deleting a letter, or changing a letter.  If no such words exist, the function returns None.
     
16. merge
    Write the function merge(a1,a2) that takes two sorted lists and returns a new sorted list with all the elements from both lists.  If each list contains n elements, you must run in O(n) time, so you cannot just append the lists and sort the result.
     
17. smallestDifference
    Write the function smallestDifference(a) that takes a list of integers and returns the smallest absolute difference between any two integers in the list.  If the list is empty, return -1.
     
18. split
    Write the function split, without using the builtin split function (of course), that takes a string and a delimiter and returns a list of substrings that are determined by that delimiter.  For example, split("ab,cd,efg", ",") returns ["ab", "cd", "efg"].
     
19. join
    Write the function join, without using the builtin join function (of course), that takes a list and a delimiter and returns the string composed of each element in the list separated by the delimiter.  So, join(["ab", "cd", "efg"], ",") returns "ab,cd,efg".
     
20. repeatingPattern
    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).
     
21. concatBits
    Write the function concatBits(a) that takes a list of numbers (which we consider to be in base 2) and returns the base 2 concatenation of those numbers.  For example, concatBits([0b101, 0b111000, 0b101]) returns 0b101111000101.
     
22. concatDigits
    This is the base10 version of the previous problem, so concatDigits[123, 45, 6789] returns 123456789.
     
23. evalPolynomial
    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 evalPolynomial(coeffs, x) that takes a list of coefficients and a value x and returns the value of that polynomial evaluated at that x value.  For example, evalPolynomial([2,3,0,4], 4) returns 180 (2*4³ + 3*4² + 4 = 2*64 + 3*16 + 4 = 128 + 48 + 4 = 180).
     
24. mulitiplyPolynomials
    Write the function multiplyPolynomials(p1, p2) which takes two polynomials as defined in the previous problem 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].
     
25. polynomialToString
    Write the function polynomialToString(p) that takes a polynomial as defined in the previous problems and returns a string representation of that polynomial, with these rules:
      * Use "n" as the variable
      * Use "^" for exponentation (though that means "bitwise-xor" in Python)
      * Include a space before/after each "+" or "-" sign
      * Do not include 0 coefficients (unless the entire polynomial equals 0)
    So polynomialToString([2,-3,0,4]) returns "2n^3 - 3n^2 + 4"
     
26. map
    Write the function map(f, a), which does not use the builtin map function, and which takes a function f and a list a, and returns a new list containing f(x) for each value x in a.  For example, say you defined a function plus3(x) that returns (x+3).  Then, map(plus3, [2,4,7]) returns [5,7,10].
     
27. firstNEvenFibonacciNumbers
    Write the function firstNEvenFibonacciNumbers(n) that takes a non-negative number n and returns a list of the first n even Fibonacci numbers in increasing order.  For example, firstNEvenFibonacciNumbers(4) returns [2, 8, 34, 144].  Note that your answer must run in O(n) time, so it cannot repeatedly call nthEvenFibonacciNumber.
     
28. crossProduct
    Write the function crossProduct(a,b) which takes two lists each containing 3 numbers and returns their cross product (as defined here, for example).  For example, crossProduct([1,2,3], [4,5,6]) returns [-3,6,-3].
     
29. lookAndSay
    First, read about look-and-say numbers here.  Then, write the function lookAndSay(a) that takes a list of numbers and returns a list of numbers that results from "reading off" the initial list using the look-and-say method.  For example:
         lookAndSay([]) == []
         lookAndSay([1,1,1]) == [3,1]
         lookAndSay([-1,2,7]) == [1,-1,1,2,1,7]
         lookAndSay([3,3,8,-10,-10,-10]) == [2,3,1,8,3,-10]
     
30. averageColor
    Write the function averageColor(a) that takes a list of 32-bit RGBA values and returns the "average" color, which is a single RGBA value where the red is the average of all the reds, the green is the average of all the greens, and so forth.
     
31. areClockwise
    Write the function areClockwise(a) that takes a list of (x,y) values and returns True if the points are in clockwise order and False otherwise.
     
32. transpose
    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.
     
33. largestProduct
    Write the function largestProduct(a) that takes a list of floating-point values and returns the largest product made by using some of those values.  For example, largestProduct([2,-3,4.5]) returns 9.0, largestProduct([0.5,1.5]) return 1.5, and largestProduct([-4, -3, -2]) returns 12.0.
     
34. mostAnagrams
    Write the function mostAnagrams(wordList) that takes a possibly-unsorted list of words (all lowercase) and returns the first word alphabetically in the list that contains the most anagrams of itself in the list.  If there are ties, still return just the first word alphabetically.
     
35. bowlingScore
    Background:  in bowling, a bowler gets 2 throws per frame for 10 frames, where each frame begins with 10 pins freshly positioned, and the score is the sum of all the pins knocked down.  However, if the bowler knocks down all 10 pins on the first throw of a frame, it is called a "strike", and they do not get a second throw in that frame; also, the number of pins knocked down in the next two throws are added to the score of that frame.  Also, if the bowler knocks down the rest of the 10 pins on the second throw in a frame, that is called a "spare", and the number of pins knocked down in the next throw are added to the score of that frame.  Finally, if there is a spare or strike in the final frame, then the bowler gets one extra throw in that frame (but if there is a subsequent strike, they still get only that one extra throw).  With all this in mind, write the function bowlingScore that takes a list of the number of pins knocked down on each throw and returns the score.  Note that throws skipped due to strikes are not listed, so the best possible result is a list of 12 10's (all strikes), which would score 300 points.
     
36. rotateList
    Write the function rotateList(a, n) which takes a list and and an integer n, and destructively modifies the list so that each element is shifted to the right by n indices (including wraparound). The function should then return the modified list.  For example:
        rotateList([1,2,3,4], 1) -> [4,1,2,3]
        rotateList([4,3,2,6,5], 2) -> [6, 5, 4, 3, 2]
        rotateList([1,2,3], 0) -> [1,2,3]
        rotateList([1, 2, 3], -1) -> [2, 3, 1]
    Do this without creating another list of length len(a).
     
37. moveToBack
    Write the function moveToBack(a,b) which takes two lists a and b, and destructively modifies a so that each element of a that appears in b moves to the end of a in the order that they appear in b. The rest of the elements in a should still be present in a, in the same order they were originally. The function should return a.  Examples:
        moveToBack([2, 3, 3, 4, 1, 5], [3]) -> [2, 4, 1, 5, 3, 3]
        moveToBack([2, 3, 3, 4, 1, 5], [2, 3]) -> [4, 1, 5, 2, 3, 3]
        moveToBack([2, 3, 3, 4, 1, 5], [3, 2]) -> [4, 1, 5, 3, 3, 2]
    Do this without creating another list of length len(a).
     
38. binaryListToDecimal
    Write the function binaryListToDecimal(a) which takes a list of 1s and 0s, and returns the integer represented by reading the list from left to right as a single binary number.  Examples:
        binaryListToDecmial([1, 0]) -> 2
        binaryListToDecmial([1, 0, 1, 1]) ->11
        binaryListToDecmial([1, 1, 0, 1]) ->13
     

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