Name: ____________________________________________________ Alpha: _____________________
Describe help received: _________________________________________________________________
Per-problem assessment:
• 5 (Perfect): Correct solution
• 4 (Good effort): Good effort, solution may or may not be correct.
• 2 (Poor effort): Some basic misunderstandings demonstrated that could have
been cleared up by reading the notes or giving a serious try.
• 0 (No effort): No progress towards a solution.
Problem 0 (assessment: self_______ final_______)
Consider the Longest Common Subsequence (LCS) from the notes.
We phrased the solving of this problem as a sequence of choices:
add&chop, chop-X and chop-Y.
I stated that no greedy choice works for this. Find
counterexamples for the following two greedy choice strategies:
-
Strategy 1:
choose add&chop if the last letters of X and Y are
equal, and otherwise chose to chop whichever of X and Y is
longer.
-
Strategy 2:
choose add&chop if the last letters of X and Y are
equal, and otherwise
- set S to the set of letters appearing in both X and Y
- set dX to the number of chop-X's needed to get to
where the last character of X is an element of S
- set dY to the number of chop-Y's needed to get to
where the last character of Y is an element of S
- if dX < dY choose chop-Y else choose chop-X