CS 4104 Final: CS 4104 Final Exam Answers
Document Summary
The exam consists of 25 multiple-choice questions, worth 10 points each, for a total of 250 points. Mark the correct answer on the opscan form. This sample exam only has 9 questions: de ne these functions of the natural numbers: g1(n) = n2 g2(n) = 2n g3(n) = (lg n)lg n. Which of these statements is true: g1 o(g2) and g2 o(g3, g2 o(g3) and g3 o(g1, g3 o(g1) and g2 o(g1, none of the above. Answer: none of the above, de ne the function t (n) by the following recurrence: What is the easiest method to solve this recurrence asymptotically: master theorem, evaluate the summation, recursion tree, none of the above. 2: consider a hash table t [0m 1] with open addressing, where m = 10. Assume uniform hashing and an initially empty table. The expected number of probes to insert 2 keys into t is: 2, 19.
