Category Archives: Assignments

For anyone who is interested, here is a written tutorial and bonus mini-assignment on how to compute the PageRank of a graph. You can earn up to 3 course bonus points for this assignment by submitting it online on Gradescope up to 48 hours after the final exam (i.e., by 2:30 PM Thursday).

A few caveats:

• These bonus points are FAR LESS IMPORTANT than your final exam! Do not sacrifice ANY necessary final exam practice/study time OR any necessary rest/relaxation to work on this. Unless you feel 100% confident that you are totally prepared for the exam, do not waste your pre-exam time and energy on this! (Also, if you DO feel 100% confident that you are totally prepared for the exam, you should read this article on the Dunning-Kruger effect before you decide to work on the bonus assignment instead of studying.)
• There is some probability and matrix algebra here, so it’s possible that not everyone will have the necessary background to answer all the questions without struggling a bit.
• Because this assignment is all for bonus points, I won’t provide any help with these questions (because bonus questions are supposed to be a challenge!).
• I will probably not release the solutions to these problems.
• I’ll return the assignments on Gradescope (possibly with feedback), but will not allow any regrade requests (because this is a bonus assignment and because we want to be prompt about submitting final grades).

Here is Assignment #6, due 11 pm on August 11. LaTeX source for the assignment will be posted on Piazza (because UBC blogs doesn’t allow upload of .tex files).

Here is Assignment #5, due 11 pm on August 6. LaTeX source for the assignment will be posted on Piazza (because UBC blogs doesn’t allow upload of .tex files).

To help you with question 4 of the assignment, here is the individual version of quiz 4 and a partial sample solution.

In today’s class we’ll work on making our change-making algorithm more efficient using memoization. If we have time, we may also start on a 2D dynamic programming algorithm to compute the longest common substring of two strings.

Announcements for today:

• The midterm exams are graded and the grades have been published on Gradescope.
• Our final exam has been scheduled for 12:00-2:30 pm on Tuesday August 13.
• Assignment 4 has been released and is due on Tuesday.
• Your tutorial quiz is today. It’s based on question 4 of your assignment and will provide a hint to help you with that question.
• Your first reading quiz on NP-completeness is due Sunday night.

Here are today’s clicker questions.

Here is Assignment #4, due 11 pm on July 30. LaTeX source for the assignment will be posted on Piazza (because UBC blogs doesn’t allow upload of .tex files).