CS 3510: Advanced Algorithms/Data Structures
Spring 2018 Assignment 3
Problems due as noted.
Problems identified by x.y(z) denote the problem “y”, in chapter “x” of the textbook, with part “z”. If “z” is not noted, then the entire problem is required.
Due Feb 26 Connectivity in Graphs
- 3.2 (b) DFS with pre/post numbers and edge type identification.
- 3.12 Prove means give a convincing arguement. Counter example means a concrete example that proves the statement is false.
- 3.18 Give the preprocessing algorithm, and the query algorithm. Analyze their complexity.
- 3.28(a,b) Show all satisfying truth assignments, and show why your formula is unsatisfiable.
Due Feb 28 Connectivity in Graphs
- 3.4 (ii)(a,b,c,d) (ii) is the second graph in the problem.
- 3.22 The algorithm is a simple extension of one in the chapter.
- 3.28 (part c) This means draw the graphs that result from the example and your example.
Due Mar 2 Connectivity in Graphs
- 3.11 Give an algorithm, argue correctness, analyze runtime
- 3.24 The algorithm is a simple extension of one in the chapter.
- 3.15 (a) Describe a graph problem that represents this problem, and the graph algorithm that will answer the question in linear time.
- 3.28 (d) The hint should give it away.
Due Mar 5 Connectivity in Graphs
- 3.15 (b) Describe a graph problem that represents this problem, and the graph algorithm that will answer the question in linear time.
- 3.28(e,f) For f, prove that the runtime is linear.
- At the beginning of class on the due dates, submit paper copies of your solutions, tables and graphs.
Last Updated 03/01/2018