Name: ___________________________

Final Exam      CSC 344

May 12, 2003

This exam is open-book, open-notes, closed-friends.  It adds up to 120 points.  Read all problems before starting, and decide which to do first.

1) (30 points) The "Relative Problem" is defined as follows:
Imagine that you have n relatives, some of whom like one another and some of whom don't. You have to invite them all to a wedding, but you want to make sure no two people who dislike one another are seated at the same table. How many tables will you need?

a)    What familiar graph problem is hiding inside this problem?
(Or, what familiar graph technique could you use to solve it?)

b)    Describe a reduction that either allows you to solve this problem efficiently or proves that it's hard.  Which problem are you reducing to which?  What conclusions can you draw about its complexity?

2) (30 points) Read the following problem description:

You're designing a campus local computer network, and you

want to make sure of two things:

(a)           it's possible to get a message from any computer in the network to any other, and

(b)           even if any one computer in the network goes down, it'll still be possible to get a message from any computer in the network to any other.

How can you tell, given a proposed list of computer-to-computer connections, whether it has these properties?

a)    Rewrite this problem in graph-theoretic terms (leaving out the inessential details).  In other words, rephrase it as a graph problem (perhaps one you haven't seen before).

b)    Design (in pseudocode) and analyze an efficient algorithm to solve this problem.  You may use well-known graph algorithms without writing them out in full.  Hint: an O(n(n+m)) algorithm is easy; an O(n+m) algorithm is extra credit.

3) (30 points) The Kumquat Bogosity Problem (KBP) is one of the more obscure problems in computational complexity.  For each of the following scenarios, tell me what you can conclude about its time complexity.  (For example, if I told you "KBP is O(n)-time reducible to sorting a list of n floating-point numbers," what could you conclude about the difficulty of KBP?)

a)    KBP is O(n)-time reducible to sorting a list of n floating-point numbers.

b)    KBP is O(n2)-time reducible to sorting a list of n2 floating-point numbers.

c)    KBP is O(n)-time reducible to finding a minimum-cost path between two specified vertices in a graph with O(n) vertices and O(n2) edges.

d)    KBP is O(n)-time reducible to finding a maximum-sized clique in a graph with O(n) vertices and O(n2) edges.

e)    Finding a maximum-sized clique in a graph with n vertices is O(n)-time reducible to an instance of KBP of size n.

f)     Determining whether a given n-line program will halt on a given input is O(n)-time reducible to an instance of KBP of size n.

4) (30 points) Choose something interesting you learned this semester, and explain it to me; convince me you know what you're talking about.

Some examples:

a)    Your favorite sorting algorithm (e.g. insertion, selection, bubble, Shell, quick, heap, merge, tree, bucket, radix); tell me briefly how it works and what you know about its time complexity.

b)    Memoization and dynamic programming.

c)    Computational complexity classes (e.g. P, NP, co-NP, PH, PSPACE, NC, NC1, LOGSPACE, AC0).

d)    Computability and uncomputability (recursive problems, r.e. problems, co-r.e. problems, the halting problem, etc.)

5) (unspecified extra credit) Have a safe and happy summer!