CS 330

Summer 2007

Assignment #1

Date Due: Monday, May 28

Reading: Chapter 1-3, pages 3-56

Chapter 9, pages 183-189

Review Chapter 22 and read Chapter 23, pages 552-577 Please Note: We will only use Section I, II, and III as needed.

You should look through Section I, reading parts of chapter 1-3 which are unfamiliar, and skimming through chapters 4 and 5. Parts of chapters 4 and 5 will be assigned and discussed as needed.

Problems:

1. Two algorithms take n ² weeks and 2 ⁿ days, respectively to solve a problem instance of size n. What is the size of the smallest instance for which the first algorithm outperforms the second ? Approximately how long does such an instance take to solve ?

2. Page 50, problem 3.1-4

3. Page 59, problem 3-4, parts (b) and (d).

4. Consider the function T(n) defined by,

       
         0 if n=0,
T(n) =   5 if n=1,
         3T(n-1) + 4T(n-2) if n>1
       
Prove by induction that, for all natural numbers n,
T(n) = 4  n  - (-1)n.

5. Consider the problem of finding a smallest and second smallest numbers in a list of n integers. Something surprisingly this can be done more efficiently than finding the max and the min of the list (which was shown in class to take (3/2)n-2 comparisons).

(a). Show how to find the smallest and second smallest numbers in a list of 8 integers using only 9 comparisons. (Note this is one less than the 10 comparisons needed to find the max and min of this list.)

(b). Give an algorithm which finds the smallest and second smallest numbers in a list of n integers and which uses only n + [log n] -2 comparisons at most. (Here [log n] means log base 2 of n rounded up to the next integer.)

6. A graph G=(V,E) is called BIPARTITE if V can be decomposed into two disjoint sets U and W such that every edge in E joins a vertex in U to one in W. A bipartite graph is called complete if for every u in U and w in W, (u,w) is in E. Let K(m,n) denote the complete bipartite graph with U containing m vertices and W containing n vertices.

a. Prove that K(m,n), n>1 and m>n, has a cycle of length 2n.

b. Prove that any cycle in a bipartite graph contains an even number of edges.

7. Prove that is an undirected, connected graph G has the property that every vertex is incident to an even number of edges, then there is a cycle through G which goes over every edge exactly once. Prove that this fact is true by writing an algorithm which constructs the required cycle.