[ answers in web view ]
Name: _______________________________ K E Y
Student ID: _______________________________

Total points: 20
  1. Find all prime numbers less than 100. (1 is not prime.) Show your work as necessary. [4]
    1 2 3 4 5 6 7 8 910
    1112131415 1617181920
    2122232425 2627282930
    3132333435 3637383940
    4142434445 4647484950
    5152535455 5657585960
    6162636465 6667686970
    7172737475 7677787980
    8182838485 8687888990
    9192939495 96979899100

    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
  2. Encrypt the cleartext "God is love" using a Caesar substitution cipher with the following key. [4]
    KEOPWRTMQZYXLINAVBFCSJGHDU

    TNP QF XNJW
  3. In your own words, what is recursion? What two conditions are required in order to prevent infinite recursion? [3]
    A function is recursive when it invokes itself. In order to prevent infinite recursion (like an infinite loop), a recursive function must make progress each time (e.g., the parameter must change), and there must be a non-recursive base case that specifies when to stop.



  4. Write a recursive function to calculate the n-th Lucas number. The Lucas sequence is similar to the Fibonacci sequence but uses 2, 1 as the starting point. So the first few Lucas numbers are 2, 1, 3, 4, 7, 11, 18, 29, ..., where each number is the sum of the two previous numbers.
    Note: write a function, not a complete program -- this means it takes input via parameters, and outputs via return statement; it should not print anything to the screen. Docstring with pre/post is required.[4]
    See fibonacci.py for both these problems, modifying the base case to be 2, 1.
  5. It turns out that the recursive solution to Fibonacci/Lucas numbers is really, really, really slow! Write another version of your function to calculate the n-th Lucas number, using iteration (i.e., loops) instead of recursion. Hint: instead of working back down from n, work your way up from the starting point of 2, 1, .... Docstring with pre/post is required.[5]