CPSC 320: Intermediate Algorithm Design and Analysis
Instructor: Geoffrey Tien
Main topics from the syllabus:
- Stable Marriage Problem (Gale-Shapley Algorithm)
- Asymptotic Notation
- Linear-time Sorting Algorithms (Counting Sort, Radix Sort, Bucket Sort)
- Greedy Algorithms (Interval Scheduling, Huffman Coding, Djikstra’s Algorithm, Kruskal’s Algorithm, Prim’s Algorithm)
- Amortized Analysis
- Recurrence Relations
- Divide and Conquer (Counting Inversions, Closest Pair, Integer Multiplication)
- Master Method
- Dynamic Programming (Weighted Interval Scheduling, Knapsack, Shortest Paths, Sequence Alignment)
- Network Flow (Ford-Fulkerson Algorithm)
- NP-Completeness (Independent Set, Vertex Cover, 3-SAT, Hamiltonian Path, Traveling Salesman, etc.)
------------------------------------------------------------------------------------
Helpful links:
Comprehensive lecture slides for textbook:
http://www.cs.princeton.edu/~wayne/kleinberg-tardos/
Solving recurrences via substitution:
https://www.youtube.com/watch?v=Ob8SM0fz6p0
Master method:
https://www.youtube.com/watch?v=6CX7s7JnXs0
------------------------------------------------------------------------------------
Evaluation:
Assignments: 4 x 6.25% = 25% Midterm: 25% Final exam: 45% Maximum of the 3 activities above: 5%
------------------------------------------------------------------------------------
Review:
I thought this course had very interesting content (hooray for algorithms!). I enjoyed working through the problems given during tutorials and assignments, which I thought was great practice for the midterm and final exam. Being exposed to different problems and needing to come up with algorithm solutions for them would also help prepare oneself for interviews. ;)
What I find really helpful, to complement pre-readings, is to actually go on YouTube and look up the algorithm in action. Perhaps as a visual learner, this is a useful way to understand the basic idea of what is happening in the algorithm before jumping into the details of it.
As for the course itself, I thought the midterm was fairly easy but the final was difficult. They seemed to be quite generous on the marking for the final, so my mark was higher than expected. For the grading of the final, the markers seemed to be allotting quite a bit of marks on the structure of the proofs, even if you did not get the proof entirely correct. Say, if you proved that a given problem is NP but did not prove that it is in NP-complete (note that NP-complete problems are a subset of NP problems), you would still receive partial marks.
Interestingly for this course, the midterm was 2 hours and the final exam’s individual component was 1.5 hours. For the remaining hour of the final exam, there was a group component. The group component was worth 15% of the final, whereas the individual component was worth 85%. A significant portion of the final exam was to prove NP-complete problems, which is unsurprising since it was the last topic we learned and we spent a considerable amount of time on it. As for the midterm, recurrence relations was probably the most tested topic, followed by greedy algorithms.
So if you see a trend here, it would be that the course mainly tests you on your ability to solve problems rather than how well you know certain algorithms (although you still would know them quite well to answer the other problems on the exams to get a good grade). After all, you could write down the algorithms learned in class on cheat sheets (we were allowed 2 double-sided cheat sheets on both the midterm and the final).
I found that attending tutorials was most helpful in helping me prepare for the exams. Some of the assignment questions were helpful, while others were probably beyond the scope of what could be tested on the exam (but good practice, nonetheless). I would suggest to any student taking this course is to not get too wrapped up in completely understanding a proof that is shown during lecture if the proof is associated with some algorithm you learned. From just my own experience, those types of proofs are not tested on. The types of methods used to formulate those proofs (proof by contradiction, to name just one example), however, are tested on. So the important takeaway is to understand how the algorithm’s efficiency and whatever else was proved, rather than just memorizing the proofs themselves. Because chances are, you may have to prove some aspects of the algorithm on the exam (these were, in my experience, the short-answer problems).
The reason why I say this is because Dr. Tien may sometimes be disorganized and loses his train of thought when going through the proofs that he talks about in class. However, I find that he is helpful if you seek help from him outside of class, perhaps because he had more time to mull over the proofs in his own time. And perhaps, without the pressure of the attention from the entire class. But for the most part, I thought he was a great professor and a funny one too. One of his quotes:
“If you are ever crawling through a desert and find a magical genie in a lamp who grants you three wishes, your first wish should definitely be to get a (low-order) polynomial-time algorithm for solving 3-SAT." - G. Tien
(Just to clarify, this would allow you to formulate your proof that P = NP)
Out of all the undergrad CPSC courses that I took, I think I got the most out of this course as well as 221. :) They challenged me in my thinking, and while it’s no walk in the park, it is the most worthwhile to take. Why? Well, I am now able to solve problems that I was never able to before (take problems that require dynamic programming solutions, for just one example) because now I have learned various tools that I could use to solve problems.