We’ll continue on the pipe-laying problem (here are part 1 and part 2) today.
- There’s an optional review session on NP completeness at 4-5:30PM Wed Mar 29 in FSC 1001.
- For next class, read section 8.7 (about the famous 3-coloring problem in graphs!). This is also a good time to go back and re-skim 8.10. You’ve seen a lot of those problems now!
- Here’s a sample solution to part 1 of our pipe-laying problem.
- Here’s a sample solution to part 2 of our pipe-laying problem.
- Don’t forget the assignment due today (Friday)!
- Next week we’ll have our last in-tutorial quiz, with a focus on NP-completeness.