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(n^{2})-time reducible to sorting a list of n^{2}
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(n^{2}) edges.

d) KBP is
O(n)-time reducible to finding a maximum-sized clique in a graph with O(n)
vertices and O(n^{2}) 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, NC^{1},
LOGSPACE, AC^{0}).

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!