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 <rrost@andrew.cmu.edu>
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