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