Date: Sun, 16 Nov 2003 15:58:54 -0500
From: Jonathan D'Andries 
To: venkat@cc.gatech.edu
Subject: cs6505, hw4 - old book question map

1. No match in the old book, but see section 24.1 and the following text of the question:

   (15 points) Exercise 23.1-11, page 567 of the new text. Given a graph G and a minimum spanning tree T, suppose that we decrease the weight of one of the edges not in T. Give an algorithm for finding the minimum spanning tree in the modified graph.

2. Exercise 32.1-6, page 783. Here is the question:

   (15 points) Exercise 30.1-7, page 830 of the new text. Consider two sets A and B, each having n integers in the range from 0 to 10n. We wish to compute the Cartesian sum of A and B, defined by

   C = {x + y : x is in A and y is in B}.

   Note that the integers in C are in the range from 0 to 20n. We want to find the elements of C and the number of times each element of C is realized as a sum of elements in A and B. Show that the problem can be solved in O(n lg n) time. (Hint: Represent A and B as polynomials of degree at most 10n.)

3. Exercise 34.2-4, page 862. Here is the question:

   (15 points) Exercise 32.2-4, page 915 of the new text. Alice has a copy of a long n-bit file A = {an-1, an-2, ... a0}, and Bob similarly has an n-bit file B = {bn-1, bn-2, ^Å, b0}. Alice and Bob wish to know if their files are identical. To avoid transmitting all of A or B, they use the following fast probabilistic check. Together, they select a prime q > 1000n and randomly select an integer x from {0, 1, ... q ^Ö 1}. Then Alice evaluates

   A(x) = (SUM(i=0 to n of ai*x^i)) mod q

   and Bob similarly evaluates B(x). Prove that if A != B, there is at most one chance in 1000 that A(x) = B(x), whereas if the two files are the same, A(x) is necessarily the same as B(x). (Hint, See exercise 31.4-4. (33.4-4 in the old book))

4. Exercise 36.4-7, page 946. Here is the question:

   (15 points) Exercise 34.4-7, page 1003 of the new text. Let 2-CNF-SAT be the set of satisfiable Boolean formulas in CNF with exactly 2 literals per clause. Show that 2-CNF-SAT is in P. Make your algorithm as efficient as possible. (Hint: Observe that x or y is equivalent to not-x implies y. Reduce 2-CNF-SAT to a problem on a directed graph that is efficiently solvable.)

5. No match in the old book, here is the question:

   (15 points) Exercise 35.4 (a), (b), page 1051 of the new text. Maximum matching. Recall that for an undirected graph G, a matching is a set of edges such that no two edges in the set are incident on the same vertex. In section 26.3 (27.3 in the old book), we saw how to find a maximum matching in a bipartite graph. In this problem, we will look at matchings in undirected graphs in general (i.e., the graphs are not required to be bipartite).

   1. A maximal matching is a matching that is not a proper subset of any other matching. Show that a maximal matching need not be a maximum matching by exhibiting an undirected graph G and a maximal matching M in G that is not a maximum matching. (There is such a graph with only four vertices.)
   2. Consider an indirecte graph G = (V, E). Give an O(E)-time greedy algorithm to find a maximal matching in G.