CSC 789 Assignment 2

Due date, September 21, 2004, 5:30 PM.

  1. Assume that you have available to you a randomized algorithm that finds the convex hull of any set of n points in 3-space in expected time O(n log n).

    Suppose that you are given X1 ... Xm, a finite list of finite sets of points in 3-space, where each Xi has ni points. Let Ki denote the convex hull of Xi and let K be the intersection of all Ki. Your problem is to find the vertices of the polyhedron K.

    Show that there is a randomized algorithm for this problem whose expected running time is O(n log n), where n = n1 + ... + nm.

    To make the problem easier for now, assume that you know that:

    • (0,0,0) is not a member of any Xi.
    • (0,0,0) is a member of each Ki.
  2. Consider the Traveling Salesman Problem, which (as you should know) is NP-hard. Consider the following randomized algorithm for finding the minimum length tour.
    • Take some randomized algorithm A which finds a tour. (There are many out there.)
    • Run A a large number of times, noting the the length of the tour each time.
    • Pick the smallest of those lengths, and announce that the tour of that length is the minimum length tour.
    What do you think of this? Write approximately half a page discussing it. (Definitely not more than a page.) (Suggestion: use the internet as a resource.)
  3. Let L = {000,010,011,100,110}. Suppose that x is a string of three bits, and you must determine whether x is a member of L. We will say that the cost of your algorithm is the number of "looks," where a look is defined as querying a particular bit of x.

    For example, if the string is 000, and if your algorithm looks at the first and third bits, it is done, since it knows the string is in L, without looking at the second bit, and its cost is then 2. On the other hand, if it looks at the first and second bits, it does not know whether the string is in L, and is forced to look at the third bit.

    • Prove that the worst-case cost of any deterministic algorithm for this problem is 3.
    • Find a randomized algorithm whose expected cost is less than 3. (It isn't much less, but it's less.)

Back to Course Page