Design and Analysis of Algorithms
A
AY22/23 S1
This is one of the killer courses in the CS core curriculum. Pretty much no coding is involved; the entire course is ffull of proofs and pseudocode. We need to prove why a certain algorithm works, and why it is the most optimal solution to a problem. There is also heavy emphasis on modifying algorithms, which means how to use the solution to one problem to solve another. This is a pattern you'll see time and time again, as many of the problems you'll find here are just the ones you already know, just in disguise. The course starts off with more advanced complexity analysis, be it asymptotic or probabilistic. There's lots more math involved here, and you'll often have to solve recurrence relations to get the right runtime complexity. Something like T(n) = T(n-1) + O(1).
Then, you'll move on to the different kinds of hashing algorithms (universal, uniform etc), all of which was tested for the midterms (I scored okay).
The second half of the module was a little more interesting, as we built up different families of algorithms. First, we had the classic Dynamic Programming, where we use recursion and memoisation to build up our solution space. Then for Greedy Algorithms, it's all about making the best decision at each step, and hoping that it leads to the best overall solution. Next, we have Incremental Algorithms, which is all about how to update our solution when new data comes in. Lastly, we have Linear Algorithms, which mainly focused on how to formulate a problem into a series of linear relations. Given a particular problem, you'll need to quickly identify which family of algorithms you need to use, and then modify them to suit your needs.
The last few lectures go through reducibility and NP-completeness. These are more for further studies, but are still useful to know. They are very theoretical in nature, and quite abstract so be warned. They basically talk about whether a particular problem is considered computationally hard. Basically remember how Cardinality works in CS1231S. It's the same concept, trying to find relations between the two algorithms and seeing if they are computationally equivalent. But if you don't fully get it, it's fine, as it doesn't matter too much in the industry anyway.
In terms of workload, it was quite small during my semester. It was just a weekly problem set, of which only 3 were graded for accuracy. The rest were graded just for effort, so we pretty much only had the midterms and finals to worry about.