CSC 364H Summer 2002

Test #2 Information

Homework solutions:
Several people have asked me about solutions for the assignment. Some hints and adequate algorithm running times are posted in the newsgroup. You are welcome to come to office hours, or use the newsgroup and email if you have any questions about solving the problems.

What do I expect you to know for the test?

• The test will cover everything from greedy algorithms up to max-flow min cut. I have decided not to include computability on this test. Linear programming and later will not be on the test.
• I expect that you have solved and know the general solutions to all the homework problems. Don't bother memorizing answers! Know the techniques instead!
• Greedy: create a greedy algorithm, prove it correct (finds optimal solutions), and analysis of running time. Know examples from class, tutorial, hw, and notes.
• Divide and conquer/simplification: create such an algorithm, prove correctness, and derivation of recurrence (you will not need to solve complicated recurrences). Know examples from class and hw.
• Dynamic programming: create a DP algorithm, prove correctness, and analysis of running time. Know examples from class, tutorial, hw, and notes.
• Max-flow/min-cut: know how Ford-Fulkerson works, its running time analysis, Edmonds-Karp improvement for finding augmenting path, can convert problems to max-flow.

What is the format of the test?
It will be a series of 4-5 problems similar in style to those on the homework, except (hopefully) much easier. You will do 3-4 of them. You will have a choice of which problems to solve. You should be able to apply the ideas required for the homework to solve the test questions.

What is the format of the questions?
You will be asked to devise an efficient algorithm (possibly using one of the methods covered), prove or argue it correct, and justify its running time. You will receive less marks for an obviously inefficient algorithm (eg. O(n^2 log n) vs. O(n log n)). You will generally receive even fewer marks for an incorrect algorithm.
Some questions may give you an algorithm and ask you to prove, analyze, give a counter-example, or modify it in some way. Some questions may ask you for properties of algorithms, running times, or asymptotic notation or efficiencies.

How long is the test?
It will be 90 minutes long. Time should be sufficient if you have kept up with the homework.