From rrost@andrew.cmu.edu Mon Feb 14 20:14:00 2000 Date: Tue, 8 Feb 2000 22:35:40 -0500 From: bobrost el magnifico Subject: Re: Updated Quiz Newsgroups: cmu.cs.class.cs451 since i was so badly injured today by the quiz (see www.spacemoose.com for demonstration) i thought i would try to answer the follow-up quiz for some extra credit or a replacement grade. > 1. Solve the following recurrences: > > T(n) = T(n) O(T(n)) > T(n) = - T(n) O(spacetime non-continuity) > T(n) = Pi * e^(T(n/2)) (make note of integrality problems) does not divide well for large values of Pi. > 2. Given the universe U of all possible character strings of size 15 > characters, write a hash function h(x) so that on any subset S of U, S will > be evenly distributed by the hash function into 10 buckets. int h(x) { //this function uses advanced hashing techniques return 7; } > 3. Outline a solution of the halting problem. You may not use the solution > from today's lecture. as we learned today in 15-312 (programming language and design), any well-typed program will halt. so, therefore, as long as you use ML, the halting problem can be determined by the following code: fun halting 0 = false | halting _ = true; > 4. Give an O(n lgn) solution to the Travelling Salesman Problem. You only > need to outline the solution, and may use subroutines from class in doing > so. Give a rough proof of the running time. Solution: cloning. the salesman can travel in parallel paths. everyone knows that parallel computing is awesome. Proof by Assumption: Assume true. QED I need to know my score on this quiz immediately, because if it is not acceptable then I am considering dropping the course. thanks, captain spiffo