CMU 15-110 Fall 2018: Principles of Computing
Homework 7 (Due Wednesday 24-Apr at 8pm)


Except for the questions specifically noted as collaborative (the TA-led session on recursion and LMC, and the group study sessions on the movie), this hw is entirely solo. See the syllabus for details.
Important: Except for LMC questions, all answers on this hw must use recursion. To receive any credit, no answers can use 'for' or 'while' loops at all!
To start, download this file: hw7.py
  1. TA-Led Sessions on Recursion and LMC [20 pts, not autograded, collaborative]
    Your recitation TA's will organize 45-minute TA-led sessions in which you will do more recursion and LMC problem-solving and code tracing. To get the hw7 points for this, you need to show up on time (even a few minutes early), stay the whole time, and be very actively involved the whole time. Have fun!

  2. 30-to-45-Minute Non-TA-Led / Self-Organized Group Study Sessions on "The Imitation Game" [20 pts, not autograded, collaborative]
    Note: unlike the TA-led sessions above, for this exercise these are not TA-led, and are self-organized. You need to organize your own small study groups of 3-to-5 students each.
    After we complete watching the movie in class, you should meet in small groups of 3-to-5 students each to study the key points of the movie from the perspective of the History of Computation. Prior to meeting, each of you should write 4 thoughtful 15-110-level quiz-style short-answer questions (multiple choice, fill-in-the-blank, very short free response, etc). Try to focus on the big ideas, and less on minutiae. Still, make the questions interesting, thoughtful, on well-chosen topics from the movie, and level-appropriate (they will be graded on these criteria). At the meeting, review each others' questions, and discuss the answers.
    What to submit: at the top of your hw7.py file, in a triple-quoted string, include:
    • The date, time, and location of your group meeting
    • The names and andrew id's of everyone in your group
    • The 4 thoughtful 15-110-level quiz-style short-answer questions, along with their answers, that you personally wrote.

The remaining questions are all solo, and all require recursion. Do not use 'while' or 'for' when solving these.
  1. getEvens(L) [15 pts]
    Without using any loops, write the recursive function getEvens(L) that takes a possibly-empty list L of integers and returns a list of just the even integers in L (in the same order as they appear). For example:
        assert(getEvens([1,2,3,4,6,2,1]) == [2,4,6,2])

  2. areVowels(s) [15 pts]
    Without using any loops, write the recursive function areVowels(s) that takes a possibly-empty string s and returns True if s contains only vowels ('aeiouAEIOU'), in any order, and False otherwise. Note that areVowels('') should return False.

  3. duplicateDigits(n) [15 pts]
    Without using any loops, and without writing any helper functions, write the recursive function duplicateDigits(n) that takes a non-negative integer n, and returns the same integer only with each digit duplicated. For example:
        assert(duplicateDigits(1) == 11)
        assert(duplicateDigits(1213) == 11221133)
        assert(duplicateDigits(1020) == 11002200)
        assert(duplicateDigits(0) == 0)  # well, 00, but that's just 0
    Hint: recall that you can use % to find the ones digit of a number, and // (integer division) to remove the ones digit.

  4. numbersWithTwosUpToN(n) [15 pts]
    Without using any loops, write the recursive function numbersWithTwosUpToN(n) that takes a non-negative integer n and returns a set of all the integers that are no larger than n and that contain at least one 2. So, for example:
        assert(numbersWithTwosUpToN(10) == { 2 })
        assert(numbersWithTwosUpToN(20) == { 2, 12, 20 })
    Hint: you may use str(n) to convert n to a string to easily check if it contains a 2.

  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.