CMU 15-110 Fall 2018: Principles of Computing
Homework 9 (Due Tuesday 13-Nov at 8pm)

---

• Team vs Solo:
  This hw has a collaborate team portion, and a solo portion. Please see the syllabus for details.


• Starter code:
  To start the solo hw, download this file: hw9.py Then, edit that file you downloaded!

---

Team Hw9

• This part of the hw is team-based and collaborative.


• Here are the topics and activities we covered:
  1. Collaborative Code Tracing
  
  
  2. Discuss / Implement Recursive Mergesort
     Note: The merge function will be provided for you.
  
  
  3. Make a 5-minute video on recursion
     Notes:
     1. The video should teach and illustrate recursion at a level that is understandable for novice programmers. For example, mergesort would be a bit too advanced for this purpose.
     
     
     2. It should be fun and engaging and clever.
     
     
     3. It does not have to have world-class video production value, but it should show some effort, including a title page, a list of authors, some basic video effect such a fade, and some well-chosen background music to keep it engaging.
     
     
     4. This is meant to help you reflect on what recursion is, and how you might teach it to someone. It is also meant to give you some practice making a video, which you will have to do again in your term project.
     
     
     5. Ideally, the team would finish the video completely during the team-hw session, but at the TA's discretion, some truly small amount of wrap-up work can be done by teammates afterwards.
     
     
     6. How to submit: get your video to your team-hw TA (in any agreed-upon manner) and they will submit it for your team.
     
     
     7. Bonus: we will assemble a small panel of world-renowned recursion education video experts (or maybe just Mark and me and a few TA's) and we will review each video and select the top few. Everyone on the first-place team will receive +10 points on the next quiz. Second-place gets +5 points, and third-place gets +2.5 points.
     
     
     8. Have fun with this!

---

Solo Hw9

• This part of the hw is solo and not collaborative. See the syllabus for details.
• Note: unless otherwise stated, functions must be non-destructive. This is true on this hw and in fact in general (all future hw's, quizzes, and exams).

---

Important: All answers on this hw must use recursion. To receive any credit, no answers can use 'for' or 'while' loops at all!

---

1. oddCount(L) [10 pts]
   Write the recursive function oddCount(L) that takes a list of integers L, and returns the number of odd numbers in L.


2. areNearlyEqual(L, M) [15 pts]
   We will say that two lists of integers are "nearly equal" if they are the same length, and the corresponding values in the lists are all within 1 (inclusive) of each other. With this in mind, write the recursive function areNearlyEqual(L, M) that takes two lists of integers, and returns True if they are "nearly equal" as just defined, or False otherwise. So:

       assert(areNearlyEqual([1, 2, 3], [1, 2, 3]) == True)
       assert(areNearlyEqual([1, 2, 3], [2, 3, 4]) == True)
       assert(areNearlyEqual([2, 3, 4], [1, 2, 3]) == True)
       assert(areNearlyEqual([1, 2, 3], [2, 3, 5]) == False)
       assert(areNearlyEqual([2, 3, 4], [1, 2]) == False)



3. complementaryDNA(dna) [15 pts]
   We can represent a strand of DNA using a Python string that contains a sequence of 'A', 'T', 'C', or 'G'. Plus, for any such strand of DNA, we define its complementary strand as having the same length, but where 'A' is converted to 'T', 'T' to 'A', 'C' to 'G', and 'G' to 'C'. With this in mind, write the recursive function complementaryDNA(dna) that takes a string (that you may assume contains only legal letters -- ATCG), and returns the complementary DNA string. So, for example:

        assert(complementaryDNA('ATGCCGTA') == 'TACGGCAT')

   Hint: this dictionary may be helpful here:

   DNA_MAP = { 'A':'T', 'T':'A', 'G':'C', 'C':'G' }



4. nthLucasNumber(n) [10 pts]
   Lucas Numbers are very similar to Fibonnaci Numbers. You can read (briefly) about Lucas Numbers here. Then write the recursive function nthLucasNumber(n) that takes a non-negative int n and recursively computes the nth Lucas Number. For example, since the Lucas Numbers are [2,1,3,4,7,...], we see:

       assert(nthLucasNumber(0) == 2)
       assert(nthLucasNumber(1) == 1)
       assert(nthLucasNumber(2) == 3)
       assert(nthLucasNumber(3) == 4)
       assert(nthLucasNumber(4) == 7)



5. bonus/optional: flatten(L) [2.5 pts]
   Write the recursive and non-destructive function flatten(L), which takes a list which may contain lists (which themselves may contain lists, and so on), and returns a single list (which does not contain any other lists) which contains each of the non-lists, in order, from the original list. This is called flattening the list. For example:

       assert(flatten([1,[2]]) == [1,2])
       assert(flatten([1,2,[3,[4,5],6],7]) == [1,2,3,4,5,6,7])
       assert(flatten(['wow', [2,[[]]], [True]]) == ['wow', 2, True])
       assert(flatten([]) == [])
       assert(flatten([[]]) == [])

   Hint: you may wish to use type(L) here to check the value is in fact a list. Note that if the top-level value is not a list, just return that value. So flatten(3) returns 3.