Final Exam Spring 2011
Algorithms and Data CS 4800
Karl Lieberherr

Open Book and Open Notes
2 Hour Exam


Question 1: Graphs (20 points)

Let G=(N,E) be a directed graph.
Let M,X and R be pair-wise disjoint subsets of N.
Let Paths(X,R,G) be the set of all paths from
nodes in X to nodes in R in graph G.
Let Nodes(Paths(X,R,G)) be the set of all nodes
in paths in Paths(X,R,G).

We define a predicate S(M,X,R,G) to be true iff
(Nodes(Paths(X,R,G)) intersect M) is the empty set.

Design an algorithm S_Checker:
input: G,M,X,R.
output: S(M,X,R,G)

Analyze the running time of your algorithm.

Note that the brute-force approach:
Enumerating all paths from some node in X to some node
in R is very time-consuming. Find a better solution.

Question 2: Reasoning about hard versus easy problems (20 points)
=====================================================

In the VERTEX COVER decision problem, we are given as input 
a graph G and a number k, and must test whether G has a vertex 
cover with k or fewer vertices; that is, a set of k
or fewer vertices that are adjacent to all edges in the graph. 
This problem is NP-complete.

(a) If VERTEX COVER has no polynomial time solution 
(that is, if P!=NP), can there exist a
polynomial time algorithm that takes as input a graph G and 
finds the vertex cover of G with the
smallest number of vertices? Why or why not?

(b) If VERTEX COVER has no polynomial time solution (that is, if P!=NP), 
can there exist
a polynomial time algorithm that takes as input a graph G 
and finds the vertex cover of G with
the largest number of vertices? Why or why not?


Question 3:  Designing an algorithm for a satisfiability-like problem
20 points
=====================================================================

Let G = (V,E) be an undirected graph.
A partition of G is a partition of V into two disjoint sets V1 and V2.
An edge is said to be cut by a partition,
if one of its endpoints is in V1 and the other endpoint in V2.
Show that there always exists a partition that cuts at least |E|/2 edges
(i.e., half of the total number of edges in the graph).

Give a probabilistic algorithm that computes such a partition.

You don't have to analyze the algorithm but make an informal argument
why it should work well in practice.


Question 4: Making claims about claims (20 points)
======================================


4.1 NetworkFlow claims
======================
In homework 8, you worked with NetworkFlow claims called FC(G,c),
where G is a network instance and c is the value
of a flow in G.
We call a claim FC(G,c) good, if c is the value of a maximum 
flow for G.

Describe an algorithm to determine, whether a network flow claim 
FC(G,c) is good.  Analyze it's running time.

4.2 HSR claims
==============

In hw 1 and 2, we studied HSR claims called HSR(n,k)=q,
where n is the number of rungs, k the number of jars to break
and q is the maximum number of questions needed to determine the hsr.
We call a claim HSR(n,k)=q good if q is minimum.

Describe an algorithm to determine, whether a HSR claim 
HSR(n,k)=q is good.  Analyze it's running time.


Question 5: Decision to Search (20 points)
==============================

Assume that you are given a black box which can
answer the decision version of the Independent Set
problem. Use a polynomial number of calls to
the black box to construct the desired set (if it exists).

Decision Version of Independent set: 
Given a graph G and an integer k, does G have a subset of k vertices
that are pairwise nonadjacent?

In other words, using the above as a black box,
you construct an algorithm that constructs an
independent set (if it exists).

====================
Extra Question:

When you are done with all questions:
Go back to question 3 and design a deterministic algorithm
for the graph partitioning problem.