Readings – CPSC 320

Lecture 2016/11/25

Today we’ll finish discussing NP-completeness.

Here is a sample solution to part 3 of the NP-completeness handout.
For Monday, please read Section 8.10 one more time now that we’ve made our way through most of the rest of Chapter 8. There will be no pre-class quiz for Monday.

Lecture 2016/11/23

Today we’ll continue with the Steiner Tree Problem. We’ve just about got a reduction; so, it’s time to prove our reduction is correct.

Here are today’s new notes on the proof (part 3 of the series).
Here’s a solution to the second part of our SP notes.
For next time, please read Section 8.8. (It’s got a lovely little discussion of dynamic programming as well!) There will be no reading quiz.
Assignment due tomorrow!

Lecture 2016/11/21

Today we’ll make a reduction to prove the Steiner Tree Problem is NP-hard (and therefore NP-complete, since it’s in NP). We won’t prove the reduction correct quite yet, however.

Note: this is a doozy of a reduction. So, it’s good practice for us, but much harder than, e.g., the SAT/ELEC problem on the assignment!

Here is the new handout on NP-hardness of SP.
For Wednesday, please read section 8.7 of the textbook (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!
No quiz for Wednesday.
Keep trucking on the assignment due Thursday!

Lecture 2016/11/18

Today, we’ll lay some pipe… or not. We may just decide it’s too hard to lay pipe.

Here again are the new notes for today on part 1 of the futility of laying pipe.
For Monday, please read section 8.5.
Complete the pre-class quiz on sections 8.4 and 8.5.
Assignment #5 is due Thursday. Make progress! It’s a substantial assignment.

Lecture 2011/11/16

Today we’ll finish our first brush with NP-completeness.. and do some more!

Here are the new notes for today on part 1 of the futility of laying pipe.
For Friday, please read section 8.4, but there is no pre-class quiz.
Don’t forget to get started on Assignment #5, due next Thursday.

Lecture 2016/11/14

Today we continue to talk about reductions and NP-completeness.

Please read section 8.3 by Wednesday and complete the pre-class quiz on 8.2 and 8.3 due at noon on Wed.
Here’s a sample solution to our current notes on reductions and NP-completeness.
Don’t forget this week’s quiz, and start in on the assignment.

Lecture 2016/11/09

Today we’ll start talking about NP-completeness with special guest host and TA Raunak Kumar! Thanks, Raunak!

Here are our notes on NP-completeness.
Don’t forget that there’s an assignment due Thursday!
Please read Section 8.2 and skim Section 8.10 for this coming Monday. Keep skimming 8.10 as we read each section. It will help to keep the problems straight in your head! (Note that we won’t discuss every type of problem categorized in 8.10, however.)
No reading quiz for Monday. (It’s a long weekend; have fun, remember those who have served the country, but do think for at least a while about algorithms!)

Lecture 2016/11/07

Today we’ll do some live-coding. Fun! Adventure! Steve making ridiculous mistakes and writing strange-looking code! 🙂

For Wednesday, please read Section 8.1 (and the very important intro to Chapter 8) and complete the reading quiz due at noon on Wednesday.
(Note: I know this is a long-ish section. I hope you’ll find that, since we’ve already discussed reductions many times, this will be a new twist on how to use them but not brand new material. Take time over the next week or so to consolidate your understanding of this very important section!)
No new handouts for today.
Come to class Wednesday, but don’t forget that Friday is a holiday: no class and no office hours.

Lecture 2016/11/04

Today we’ll finish up our 2-D DP handout.

For Monday, please read section 6.8 (the last required section in the dynamic programming chapter, although I recommend the other sections as interesting reading, particularly if you’re continuing on to CPSC 445, which uses DP heavily). No reading quiz.
Don’t forget we have an assignment due Thursday! Keep up with the post pinned on Piazza with some (largely minor but still important) updates on the assignment.

Lecture 2016/11/02

We’ll continue our longest common subsequence problem in class today.

Get started on the Assignment somewhat dubiously numbered “4” that is due on Thursday 10 Nov! It’s posted on this blog.
Read Section 6.6 and complete the pre-class quiz by noon Friday.
If you have US citizenship: vote! I did 🙂