Data Structures and Algorithms
A
AY21/22 S2
Probably the most important course for technical interviews. This is a crash course on all things algorithms. The course starts off with the basics of complexity analysis, then moves on to sorting algorithms, searching algorithms, tree algorithms and finally graph algorithms.
Be prepared to spend a lot of time on the sorting algorithms, as there are like 6 of them. You have to know what each of them does, what are their invariants, and what conditions are best for them. Put these all in your cheatsheet and you should be fine.
For complexity analysis, you are mainly dealing with loops and recursions, so take note of how many loops there are, and how many times the loops run. A rule of thumb would be:
1. If you're in a loop and the variables are incrementing by a fixed amount, then think linear O(n).
2. If you're in a loop and the variables are changing by multiplication or division, then thing O(logn).
3. If you're using recursion and calling f(n-1) twice, then think exponential O(e^n).
4. If you're using recursion and calling f(n-1) once, then think linear O(n).
5. If you're using recursion and calling f(n/2) a fixed number of times, then think logarithmic O(logn).
Tree algorithms are very error-prone, as there are so many different edge cases you need to worry about. The AVL tree, for example, is a self-balancing tree, which means that when things are added or deleted, the tree needs to be able to rearrange itself to not let any side be too long. Remembering and coming up with the edge cases is not a easy task.
Lastly, for the graph algorithms, the star of the show is the Dijkstra algorithm. It's the most famous out of them, but with a little tricky implementation. It's a valuable algorithm to learn and master.
As for workload, we use the Coursemology platform, which gives score based on the amount of XP you earn from homework and tutorial participation. Again, you don't need to worry so much about getting full XP for everything, as most people get it anyway. Homework is usually solving some algorithmic problem, and you use the different data structures and algorithms you're learnt to solve them. They're all in Java, so it is typically recommended to take this course alongside CS2030S. I usually finish the problem sets within 2 hours of the release, so it's not too bad. I'm usually one of the first ones to submit their work, which means I usually get my XP very early on, easily putting me near the top of the leaderboard week after week.
The midterms and finals are pretty manageable, as they test you on your problem solving skills. Be prepared to write lots of pseudocode and draw lots of diagrams. Don't waste time writing curly braces or writing type declarations, as these all will slow you down. Instead, just focus on writing the core structure of the algorithm IN PENCIL, and if you have time after completing the questions, then you can go back and fill in the details. What they are testing you on are your concepts, and NOT your knowledge of Java syntax. So don't worry too much about that.