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!