[ 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	9	10
   11	12	13	14	15	16	17	18	19	20
   21	22	23	24	25	26	27	28	29	30
   31	32	33	34	35	36	37	38	39	40
   41	42	43	44	45	46	47	48	49	50
   51	52	53	54	55	56	57	58	59	60
   61	62	63	64	65	66	67	68	69	70
   71	72	73	74	75	76	77	78	79	80
   81	82	83	84	85	86	87	88	89	90
   91	92	93	94	95	96	97	98	99	100

   
   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]