CS 202, section 2 Midterm 2 5 November 2004 1 Name: _____________________________________ E-mail ID: [email protected] Pledge: _______________________________________________________________________ _____________________________________________________________________________ _____________________________________________________________________________ Signature: _____________________________________________________________________ There are 50 minutes for this exam and 100 points on the test; don’t spend too long on any one question! All work must be on these three exam pages. A note on terminology: to differentiate between the two types of induction (mathematical induction and strong induction), they are referred to as weak induction and strong induction, respectively (or weak mathematical induction and strong mathematical induction, respectively).CS 202, section 2 Midterm 2 5 November 2004 2Short answer questions (5 points each): these questions only require a sentence or two for full credit. 1. Given a RSA cipher text of 4501, a decryption key of 4669, and n = 10379, how would this message be decrypted? You can leave the answer in formulaic form. Clearly label what your variables represent! Answer: 2. Find the lowest possible number (greater than 1) that is relatively prime to 210. Note that any number that is relatively prime to 210 will get credit, but the lower the number, the greater the credit. Answer: 3. Find four numbers congruent to 5 modulo 17. Answer: 4. What is )105,63gcd( ? Answer:CS 202, section 2 Midterm 2 5 November 2004 3 5. What is )105,63lcm( ? Answer: 6. What is the closed form formula (meaning a non-recursive formula that does not use summations) for the summation ∑=nkk1? Answer: 7. What is the halting problem, and why is it important? Answer: 8. What is the difference between weak induction and strong induction? Answer:CS 202, section 2 Midterm 2 5 November 2004 49. (20 points) For each of the following parts, draw arrows from the dots on the left to the dots on the right to indicate a function that fulfills the following properties. If necessary, you may cross off elements on either side. a) A function that is not one-to-one and not onto 1 • 2 • 3 • 4 • 5 • • a • b • c • d • e b) A function that is one-to-one but not onto 1 • 2 • 3 • 4 • 5 • • a • b • c • d • e c) A function that is not one-to-one but is onto 1 • 2 • 3 • 4 • 5 • • a • b • c • d • e d) A function that is both one-to-one and onto 1 • 2 • 3 • 4 • 5 • • a • b • c • d • e e) An example of a mapping that is not a function 1 • 2 • 3 • 4 • 5 • • a • b • c • d • eCS 202, section 2 Midterm 2 5 November 2004 510. (25 points) Consider the recursive definition for )(nf where 1)1(=f and 12)1()( −+−= nnfnf for 2≥n. a) Write the first 5 terms of )(nf . Answer: b) Find an explicit (i.e. non-recursive) formula for )(nf . Answer: c) Use weak mathematical induction to prove the result from (b) equals the recursive definition for )(nf . Answer:CS 202, section 2 Midterm 2 5 November 2004 611. (15 points) Give the recursive definitions of the following sequences. Clearly label the parts of your recursive definition. a) The sequence generated by 5=na for ,...3,2,1=n Answer: b) 1, 0, 2, 0, 4, 0, 8, 0, 16, 0, 32, 0, … Answer: c) 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6, 1, … (only one basis step allowed!)
View Full Document
Unlocking...