Early Project Review

Goal: Catch misconceptions and lack of progress early enough that the feedback can guide the major implementation work of Week 2.

Points: 10

Reviews begin near the end of Week 1. They intentionally overlap the transition from Checkpoint 1 into Checkpoint 2 rather than creating a separate phase of project work.

The review has two parts.

Part A: Individual understanding check

Each team member will answer one or two short questions independently about the team’s assigned problem.

These questions are intentionally basic. Examples include:

• Is this proposed coloring legal? If not, identify a conflicting edge.
• Is this set a vertex cover? If not, identify an uncovered edge.
• Is this set a clique?
• Is this sequence a legal simple path?
• Is this sequence a legal TSP tour, and what is its cost?
• Is the optimization problem a minimization or maximization problem?
• What must the verifier check?
• Does a feasible solution have to be optimal?

The purpose is to verify that every project member understands the problem being studied, not to create a high-pressure oral examination.

Part B: Team progress review

The team should be prepared to:

1. show the working verifier;
2. show the exhaustive baseline on a small example;
3. explain how the baseline was validated;
4. identify where the exhaustive approach begins to grow rapidly;
5. explain the proposed improved exact strategy;
6. explain the proposed bound;
7. explain the proposed first heuristic; and
8. identify what each team member is working on next.

You are not expected to have the improved exact algorithm or heuristic completed before the review.

However, the team should be able to show that work has moved beyond merely discussing the project. If you have already started implementing the next algorithms, bring that work even if it is incomplete.

After the review

Record the important feedback and use it immediately during Checkpoint 2. The instructor may recommend that the team revise an algorithmic approach, correct a misunderstanding, replace an invalid or unhelpful bound, simplify a heuristic, or prioritize a particular implementation or testing task.

Grading