Here is the worksheet and sample solution from our NP-completeness tutorials this week.
And here’s a summary sheet on NP-completeness.
Categories
-
Recent Posts
Archives
Meta
Category Archives: Tutorials
PageRank bonus worksheet
A tutorial and bonus mini-assignment (worth up to three bonus marks) on the PageRank algorithm has been posted. It’s based on the material in today’s PageRank session. If you weren’t able to make the session, there should be enough information in the walkthrough for you to be able to take a stab at the questions anyway.
If you’re interested, here is a zip file of the MATLAB functions I used in the session. (A warning that some of the plotting commands may not work as expected in Octave or older versions of MATLAB.)
Posted in Tutorials
Quiz 2 Pre-Reading
Here’s a pre reading document for quiz 2. Reading this before your quiz may help you avoid spending time reading/understanding it during the quiz. We’d urge you to do so!
(We may do this with future quizzes and exams.)
Posted in Assignments, Tutorials
Week 3 tutorial notes
Here are the notes for this week’s tutorial on combinatorics, reductions, and logarithm rules (which we didn’t end up having time for in any of the tutorials, but are included in here!).
Posted in Tutorials
2017/09/10: Readings, Handouts, and Notes
We’ll continue the first stable marriage handout and (maybe!) start talking about the critical concept of reductions on our next worksheet.
Important notes for today:
- Here’s the intro SMP handout we’re continuing work on.
- Here’s our new handout on reductions and stable marriage.
- Please be sure to review the syllabus.
- The next pre-class quiz is due by 10PM on Sunday (2017/09/17).
- Before Sunday’s pre-class quiz (pquiz): Read Chapter 2 of the textbook. Most of this should be review! Sections 2.3 and 2.4 are especially valuable for applied review of asymptotic analysis. This is what you should be good at to be awesome computer scientists. Work through the asymptotic analysis worked example. Here’s the blank worksheet and the screencast solution.
- Come to tutorial for your tutorial quiz (tquiz). We’ll be particularly lenient in marking this tquiz since you’re just getting to know the format and we’re being pretty aggressive about what we’re assessing on it. In general, the tquizzes also aren’t worth much of your grade. (See the syllabus!) The point of these is to give you hands-on time working on exam-like questions in a timed context, followed by group time to reinforce and expand what you learned from your individual work.
- The assignment version of the tutorial quiz questions will release shortly after Wednesday’s tutorial. Start looking those over and working on them! The assignment is due next Friday!