Category Archives: Handouts

Happy last day of class, everyone! We have some special, fun stuff planned for today.

Plan for today’s class:

• We will wrap up the extremely fun and exciting proof of correctness for our SP reduction.
• We have a special worksheet on Google’s PageRank algorithm (with subsequent opportunities for BPs).
• You will have time for TA and course evaluations.
• Prof. Steve Wolfman will be giving a guest lecture on the development of the QuickSort algorithm.
• If we have extra time, we will have Q&A about the final exam.

Administrative announcements for today:

• There will be a TA-led final exam review session today from 12:30-3:30 PM in DMP 310. This also means that there are no tutorials today.
• Remember that Assignment 6 is out and is due SUNDAY (not Tuesday!).
• A few end-of-term things you should remember to do:
  • Read the Piazza post about final exam information if you haven’t already done so
  • Register your iClicker/REEF mobile device
  • Review your grades on Canvas and Gradescope to make sure nothing is missing or obviously wrong in some way
  • Complete course evaluations (if you don’t manage to do so in today’s class)

Today we’ll develop a reduction to show that the Steiner Problem is NP-hard and then work on proving the correctness of our reduction.

Announcements for today:

• Assignment 6 has been released as of 11:15 PM on August 6. Be sure to note the earlier-than-usual deadline (11 PM Sunday)!
• You have a quiz today in tutorial, based on Assignment 6 (there will be some additional details given in lecture).
• Please fill in your course evaluations! Your feedback is helpful both for me personally and for future CPSC 320 instructors. We will allow time in class for this on Friday, but this is in case you won’t be here or would like extra time.
• We have some miscellaneous fun stuff planned for our last lecture on Friday! Details to follow at the start of today’s lecture.

Today we’ll continue our worksheet on revisiting reductions, and then start working on a pipe-laying problem (and depending on how far we get, we may start the second worksheet for this problem).

Announcements for today:

• Assignment 5 has been released and is due on August 6.
• Tutorials today will focus on additional practice in reasoning about NP-complete problems.
• You have no more assigned readings for the rest of the term! 🙂

Here are today’s clicker questions.

We’ll start today’s class by discussing complexity classes and NP-completeness. Then we’ll dive into a new worksheet on reductions (used differently than before).

Announcements for today:

• You have a tutorial quiz today. Assignment 5 (mainly on memoization/dynamic programming) will be released today at the usual time.
• We’ve posted some information about the final exam. See the Piazza post.
• Your second reading quiz on NP-completeness is due Thursday night.

Here are today’s clicker questions.

Today we will continue working on a 2D dynamic programming algorithm to compute the longest common substring of two strings. If we have time, we may start talking about NP-completeness.

Announcements for today:

• Assignment #4 is due tomorrow at 11 PM.

Here are today’s clicker questions.

Today we’ll start on our memoization/dynamic programming unit with a worksheet on making change (the kind with coins, not the kind you wish to be/see in the world).

Announcements for today:

• The midterm exam is on Wednesday. We will discuss logistics at the beginning of class today. If you miss the beginning of today’s class, make sure you read the exam information we have on Piazza.

Today we’ll finish up our worksheet on divide and conquer and talk about a cool variant of the QuickSelect algorithm with better theoretical performance guarantees. We also have a handout on the Master Theorem.

Announcements for today:

• Assignment 3 is up on the course webpage. This one is just practice for the midterm exam and won’t be for submission. We’ll release solutions on Sunday morning.
• Tutorials today will be about proofs on 320 exams. The proof questions we ask on exams tend to be structured a bit differently from the ones we ask on assignments (though they obviously deal with the same kinds of concepts). Tutorials today will work through some examples.
• Your first reading quiz on dynamic programming is due on Sunday night.

Here are today’s clicker questions, along with PDF versions of today’s Jupyter notebooks on how to select the pivot, and Steve Wolfman’s more elaborate and complete notebook on the actual algorithm. UBC Blogs does not allow upload of .ipynb files, so the actual notebooks can be downloaded on Piazza.

Today we’ll spend a bit of time reviewing our proof of correctness from last time. Afterwards, we’ll start on our divide and conquer unit with this worksheet on QuickSelect.

Announcements for today:

• You have a tutorial quiz today.
• Assignment 3 will be released after tutorials, as usual, but unusually, this assignment is only for practice (because the normal deadline would have been the night before the midterm exam, which didn’t strike us as desirable). We strongly recommend you work through it as part of your exam preparation and put as much effort into it as you would an actual assignment.
• Assignment 1 grades have been released on Gradescope. If you wish to submit a regrade request, please read our policy on regrade requests first. (In particular: read the sample solution before you dispute your grade!)
• Your reading quiz on divide and conquer is due Thursday night. (Yes, this is after we will have started on the unit in class; the alternative was having a reading quiz and assignment due at the same time!)

Here are today’s clicker questions and the slides reviewing the proof of correctness of our greedy clustering algorithm.

In today’s class we’ll wrap up our worksheet on clustering and then we’ll prove that the algorithm we developed is optimal.

Announcements for today:

• Assignment 2 is due tomorrow night.
• We have some information about the midterm exam posted on Piazza.

Here are today’s clicker questions.

In today’s class we’ll start on greedy algorithms. In our worksheet we’ll develop an algorithm for clustering photos.

Announcements for today:

• Assignment 2 has been released and is due on Tuesday.
• Tutorials today will cover how to write good pseudocode and a review of asymptotic analysis notation (big- and little-O/omega, etc.). A reminder to please attend your registered tutorial section if possible, as the earlier sections are nearly full and priority needs to be given to students registered in that section.
• The second reading quiz on greedy algorithms is due on Sunday night. 

Here are the clicker questions from today’s class.