Intermediate Algorithm Design and Analysis
“In this course, we mostly just do a high-level analysis of algorithms which are heavily used in the real-world. Today, we do the opposite. We actually implement an algorithm that is utterly useless.”
Text: Algorithm Design by Jon Kleinberg and Eva Tardos
Prof: Dr. Steve Wolfman
Wolfman is really entertaining. He is also a big believer in ‘flipped classroom’ approach, so the lectures are mostly problem-solving. I like the practice, but others may not like the lack of highly structured lectures and the necessity to do readings ahead of the class. He thinks deeply about his students’ education, so few pedagogical decisions are arbitrary though they may appear so.
The assignments were initially easy but became increasingly lengthy and time-consuming. A background with mathematical proofs might help. I found the level of rigor required for the proofs lower than in CPSC 221, but the concepts were definitely more complex. The midterms were closely linked to the assignments and tested generic problem-solving skills rather than accumulated knowledge (though you probably need to know your definitions and the high-level idea of important algorithms). The tutorial and pre-reading quizzes were hit and miss, but they were more for familiarizing yourself with the topic than an actual assessment.The final was a bit longer than I expected, but all the questions were definitely doable if I had ~20 more minutes.
Divide and Conquer
NP-Completeness: Some reductions are very sophisticated, but they rarely expect us to come up with complex reductions.
Counterexamples: Sometimes it can take a lot of time to come up with a counterexample. Sometimes it’s better to list some constraints your counter-example must satisfy before diving into a brute-force search.
Enjoyable, useful sequel to CPSC221.