-
Recent Posts
Recent Comments
Archives
Categories
Meta
Protected: Assignment #6 Sample Solution
Enter your password to view comments.
Posted in Assignments
Bonus assignment (PageRank algorithm)
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).
Posted in Assignments
August 9 Handouts and Notes
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)
Assignment #6
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).
Posted in Assignments
Protected: Assignment #5 Sample Solution
Enter your password to view comments.
Posted in Assignments
August 7 Handouts and Notes
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.
Posted in Handouts
August 2 Handouts and Notes
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.
Posted in Handouts
Assignment #5
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).
Posted in Assignments
Protected: Assignment #4 Sample Solution
Enter your password to view comments.
Posted in Assignments
July 31 Handouts and Notes
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.
Posted in Handouts