CMU 15-112: Fundamentals of Programming and Computer Science
Writing-Session4 Practice

• These exercises will help you prepare for writing-session4, which is on Fri 20-Sep, and which will contain a randomly-chosen subset of exercises from among these.
• Unlike the hw, you may work collaboratively on these practice exercises.
• That said, during the actual writing session on Friday you must work alone, and without any notes or access to the web or other resources.
• To start:
  1. Create a folder named 'writing_session4_practice'
  2. Download both writing_session4_practice.py and cs112_f19_week4_linter.py to that folder
  3. Edit writing_session4_practice.py
• Do not use recursion this week.
• Do not hardcode the test cases in your solutions.

1. alternatingSum(a)
   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). If the list is empty, return 0.


2. median(a)
   Write the non-destructive function median(a) that takes a list of ints or floats and returns the median value, which is the value of the middle element, or the average of the two middle elements if there is no single middle element. If the list is empty, return None.


3. isSorted(a)
   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 only consider each value in the list once (so, in terms of big-oh, which we will learn soon, it runs in O(n) time, where n=len(a)), and so in particular you may not sort the list.


4. smallestDifference(a)
   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. For example:

     assert(smallestDifference([19,2,83,6,27]) == 4)
   

   The two closest numbers in that list are 2 and 6, and their difference is 4.


5. lookAndSay(a)
   First, you can 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, using tuples for each (count, value) pair. 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)]
     lookAndSay([3,3,8,3,3,3,3]) == [(2,3),(1,8),(4,3)]
   



6. inverseLookAndSay(a)
   Write the function inverseLookAndSay(a) that does the inverse of the previous problem, so that, in general:

     inverseLookAndSay(lookAndSay(a)) == a
   

   Or, in particular:

     inverseLookAndSay([(2,3),(1,8),(3,-10)]) == [3,3,8,-10,-10,-10]
   



7. multiplyPolynomials(p1, p2)
   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 lists representing polynomials as just described, and returns a third list representing the polynomial which is the product of the two. For example, multiplyPolynomials([2,0,3], [4,5]) represents the problem (2x**2 + 3)(4x + 5), and:
       (2x**2 + 3)(4x + 5) = 8x**3 + 10x**2 + 12x + 15
   And so this returns the list [8, 10, 12, 15].


8. nondestructiveRemoveRepeats(L)
   Write the function nondestructiveRemoveRepeats(L), which takes a list L and nondestructively returns a new list in which any repeating elements in L are removed. For example:

   assert(nondestructiveRemoveRepeats([1, 3, 5, 3, 3, 2, 1, 7, 5]) ==
                                      [1, 3, 5, 2, 7])
   

   Also:

   L = [1, 3, 5, 3, 3, 2, 1, 7, 5]
   assert(nondestructiveRemoveRepeats(L) == [1, 3, 5, 2, 7])
   assert(L == [1, 3, 5, 3, 3, 2, 1, 7, 5]) # nondestructive!
   

   Note that the values in the resulting list occur in the order they appear in the original list, but each occurs only once in the result. Also, since this is a nondestructive function, it returns the resulting list.


9. destructiveRemoveRepeats(L)
   Write the function destructiveRemoveRepeats(L), which implements the same function destructively. Thus, this function should directly modify the provided list to not have any repeating elements. Since this is a destructive function, it should not return any value at all (so, implicitly, it should return None). For example:

   L = [1, 3, 5, 3, 3, 2, 1, 7, 5]
   destructiveRemoveRepeats(L)
   assert(L == [1, 3, 5, 2, 7]) # destructive!
   

   
   
10. Short Answer Practice Problems
    Note that this week's writing session will start with a physical sheet of paper containing some subset of these questions, or questions nearly identical to these questions.

    1. Which of these does not set M to a copy of L?
        a) M = copy.copy(L)
        b) M = L[:]
        c) M = L + [ ]
        d) M = L
        e) M = list(L)
    
    2. If a function f(L) does not return a value (so technically it returns None),
       which is more likely:
       a) f(L) is destructive
       b) f(L) is non-destructive
    
    3. Assuming L is a list and s is a string, which of the following methods
       does not exist:
       a) L.index(v)
       b) L.find(v)
       c) s.index(c)
       d) s.find(c)
    
    4. What is the difference between L.append(v) and L.extend(v)?
       a) There is no difference
       b) L.append adds one value and L.extend adds a list of values
       c) L.append adds to the end of L and L.extends adds to the start of L
       d) There is no such thing as L.extend
    
    5. Fill in the blank so that M is equal to L, only with the value 5
       nondestructively inserted at index 3 (so L is unchanged). 
       You may assume len(L)>3:
    
       M = _________________________________________________
    
    6. Which kind of loop should we use if we are adding and/or removing values
       from a list L while looping over it?
       a) for v in L
       b) while i < len(L)
    
    7. What is the difference between L.sort() and sorted(L)?
       a) L.sort() is faster than sorted(L)
       b) L.sort() is destructive and sorted(L) is non-destructive
       c) L.sort() is non-desructive and sorted(L) is destructive
       d) Nothing -- they do the same thing.
    
    8. What is the key difference between a tuple and a list?
       a) Tuples can only contain exactly 2 values, lists can contain any number of values
       b) Tuples are mutable, lists are not
       c) Tuples are immutable, lists are not
       d) Tuples can only contain numbers, lists can contain any type of value
    
    9. Fill in the blank so that T refers to a singleton (length 1) tuple
       containing just the value 42:
    
       T = _____________________________________
    
    10. Fill in the blank with a list comprehension so that M contains the
        list of the squares of the values in L, which you may assume is a list
        of integers:
    
        M = ____________________________________
    



11. Code Tracing Practice Problems
    Same note as above: this week's writing session will start with a physical sheet of paper containing some subset of these questions, or questions nearly identical to these questions.

def ct():
    # fill in each space to the right of each print statement
    # with the value it prints

    print([3,2,1] > [3,2])  # __________________________________

    a = [1]
    b = a
    c = copy.copy(a)
    a += [2]
    a = a + [3]
    print(a, b, c)          # __________________________________

    a = [2,3,5,3,2]
    a.remove(2)
    v = a.pop(2)
    print(a, v)             # __________________________________

    L = list(range(1,7,2))
    M = [v**2 for v in L]
    N = [v*10 for v in M if v < 10]
    print(L, M, N)          # __________________________________

    L = ['A', 'BC', 'D']
    print('xy'.join(L))     # __________________________________

ct()