CS 3510: Advanced Algorithms/Data Structures
Spring 2017 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 23 Graphs and Representations
- 3.8(a) By model, we mean define how the problem can be translated to a graph problem.
- 3.16(a) Show the prerequisite graph for all CS and MATH courses for the CS degree requirements.
- 3.16(b) What is the number of semesters required under the constraints of the problem?
- 3.28(a,b) Show all satisfying truth assignments, and show why your formula is unsatisfiable.
Due Feb 28 Depth First Search and Connectivity
- 3.2(a) Start from node ‘A’.
- 3.12 Prove means give a convincing arguement. Counter example means a concrete example that proves the statement is false.
- 3.28( c) This means draw the graphs that result from the example and your example.
Not Due Feb 28 NOT REQUIRED
- 3.8(b) Just state the algorithm. It should be one in the text. Pay attention, you need to implement this algorithm.
- 3.26(a) A tour is a cycle that starts and ends at the same vertex. Start by proving that if an Eulerian tour exists, then all vertices must have an even degree. Then try to prove that if all vertices have an even degree an Eulerian tour must exist.
- 3.26(b) A path need not start and end at the same vertex. What can you say about the number of odd/even degree vertices if an Eulerian path exists?
Due Mar 2 Directed Graph Search
- 3.3(a,b,c,d) This looks harder than it is.
- 3.24 The algorithm is a simple extension of one in the chapter.
- 3.28(d) The hint should give it away.
Not Due Mar 2 NOT REQUIRED
- 3.16( c) What algorithm solves this problem in the general case?
- 3.26( c) Find a condition on directed graphs that must be true for a Eulerian tour to exist.
Due Mar 7 Strongly Connected Components
- 3.4(i)(a,b,c,d) (i) is the first graph in the problem.
- 3.22 The algorithm is a simple extension of one in the chapter.
- 3.28(e,f) For f, prove that the runtime is linear.
Due Mar 21 Connectivity (Only one of this or the one from chapter 4 is required) 10 points
- Implement a program to run your algorithm for problem 3.8. Your program must be able to answer the generic question “You are given 3 jugs of size ‘a’, ‘b’ and ‘c’. Jug ‘a’ starts out empty, and ‘b’ and ‘c’ start out full. Is there a sequence of pourings that leaves exactly ’d’ units of water in either ‘b’ or ‘c’?“, with ‘a’ >= ‘b’ >= ‘c’ >= ’d’. Experimentally determine its runtime as a function of the largest jug size, ‘a’. Create a table and a graph comparing the experimental runtime to log, linear, quadradic and cubic curves. (Food for thought: if explore is linear, why isn’t your algorithm’s runtime linear?)
- At the beginning of class on the due dates, submit paper copies of your solutions, tables and graphs.
Last Updated 04/06/2017