[cmps201] Mid-term review agenda

[Brad Eric Hollister]

Below are the points I'd like covered in the mid-term review today.

I'm most curious about (4), but it is probably out-side the scope of our mid-term. (However, it could factor into having a correct proof on the test, so I am asking it anyway.)

1. Explain the "chip and conquer" time-complexity of the recurrences of part 2 of the sample mid-term 2.

2. Will there be any other reductions asked besides: IS, VC, CL, HC and HP decision problems?

3. Review the basic boiler-plate prose of a reduction proof (not what needs to be done, i.e. steps 1-3) but the template proof itself (i.e., the required verbage: "Claim" statement, "By hypothesis, there exists", and all other REQUIRED elements of the proof).

*4. Question: How can we be sure by seeing basic trends in specific cases / instances of reductions on graph-based decision problems (meaning illustrative graphs and set sizes), that the reductions are true for the k = nth case of ALL possible input graphs satisfying the problem type (is this to be proved in the sub proofs of part 2. and 3.')? Also, do we need a sub-proof by induction to show that our transformation works on ALL possibly SIZED graphs for a given reduction proof to be completely correct? (More specifically, the HP -> HC reduction requires a transformation on the input graph to HP, say. How can we be sure that our graph transformation works for ALL possible graph input instances, OR how do we prove that, instead of just stating that our transformation works because it "appears" to work on small and specific instances of a graph for a range path lengths?)

5. Verify that one of the DFS properties proofs posted on Piazza is correct.

Regards,
Brad Hollister

[Brad Eric Hollister]

Additional clarification of question #5 for mid-term review.

5. Verify that one of the DFS properties proofs posted on Piazza is correct and which one is correct. Or, if none are correct, then for a specific incorrect proof, let me know why it is incorrect and what needs to be added and / or removed from that specific incorrect proof to make it correct.

Regards,
Brad

[Steven Burt]

For HP/HC (or reduction in general), can you discuss what makes a "wrong" solution (e.g. removing an edge)? Does it have to do with needing to have proof of that edges existence when you move to step 3'?

For Problem 6B, what is meant by "be specific about outputs?"

> _______________________________________________