CMU 15-112 Summer 2018: Fundamentals of Programming and Computer Science
Homework 11 (Due Wed 25-Jun, at 5pm)

• This assignment is SOLO. This means you may not look at other student's code or let other students look at your code for these problems. See the syllabus for details.


• To start:
  1. Create a folder named 'week4'
  2. Edit hw11.py using Pyzo. Note that you are not given a starter file. This means you must make your own test cases!
  3. When you are ready, submit hw11.py to Autolab. For this hw you will have 10 submissions.
• This homework is fully autograded.
• Do not hardcode the test cases in your solutions.
• This homework may be graded for style.
• You must use recursion to solve these problems. Using a for or while loop will result in you losing full credit for the question. You may also not use inherently iterative functions. These include range, sum, max, min, count, replace, sort, reverse, sorted, and reversed.

1. recursive alternatingSum(lst) [30 pts] [autograded]
   Write the function alternatingSum(lst) that takes a possibly-empty list of numbers, lst, and returns the alternating sum of the list, where every other value is subtracted rather than added. For example: alternatingSum([1,2,3,4,5]) returns 1-2+3-4+5 (that is, 3). If lst is empty, return 0.
   
   


2. recursive binarySearchValues(L, v) [30 pts] [autograded]
   Write the function binarySearchValues(L, v) that takes a sorted list L and a value v and returns a list of tuples, (index, value), of the values that binary search must check to verify whether or not v is in L. As an example, say:

      L = ['a', 'c', 'f', 'g', 'm', 'q']
      v = 'c'
   

   Binary search always searches between some start and end index (exclusive), which initially are 0 and (len(L)). So here, start=0 and end=6. The first index we try, then, is mid=3 (the integer average of start and end). The value there is 'g', so we will add (3, 'g') to our result.
   
   Since 'g' is not the value we are seeking, we continue, only now we are searching from start=0 to end=3, just like we did with Binary Search in class.
   
   Now we try mid=1 (the integer average of start and end), and so we add (1, 'c') to our result. We found 'c', so we're done. And so we see:

       L = ['a', 'c', 'f', 'g', 'm', 'q']
       v = 'c'
       assert(binarySearchValues(L, v) == [(3,'g'), (1,'c')])
   

   
   In the case where v is not in L, still return the list of tuples of indices and values searched. For example:

       L = ['a', 'c', 'f', 'g', 'm', 'q']
       v = 'b'
       assert(binarySearchValues(L, v) == [(3, 'g'), (1, 'c'), (0, 'a')])
   

   
   Hint: Do not slice the list L, but rather adjust the indexes into L.
   Hint Hint: It might help to write a helper function that can take in a start and end index in addition to L and v. This helper function will do all of the work. What should you return when start == end?


3. recursive generateLetterString [40 pts] [autograded]
   Write the function generateLetterString(s) that takes a two-character string and returns a new string that contains the all of the letters between the first letter and the second letter. For example, generateLetterString("ko") would return "klmno". This should also work backwards, so generateLetterString("me") would return "mlkjihgfe". If the initial provided string is not two characters long you should return the empty string. If the string contains two identical characters (like "aa"), then return the letter ("a"). You may assume that you are given only lowercase letters.