More pipe-laying as we establish that this fiendish problem is NP-complete.
- Here are all three parts of the pipe-laying handout: part 1, part 2, part 3, with sample solutions to part1 and part2.
- For next time, please read section 8.8. There’s an awesome special guest appearance by dynamic programming there.
- Don’t forget our last tutorial quiz this week! (Quiz posting may work a little differently this week than usual, as we’re likely going to shorten the assignment compared to the total of the quizzes.)