CS3230 Review

Taken in AY18/19 Sem 1 under Prof Chang Ee Chien.

This module is a largely mathematical and theoretical module that covers topics such as big-O notation, sorting/searching, graphs, NP-completeness, and associated algorithms in those areas. Proofs of the various algorithms discussed are covered, and students are expected to devise algorithms and write some proofs in the exam.

Content is relatively light compared to many of the CS210x modules, so little memory work is required. While there are a number of algorithms covered in this module, the exams place significant focus on the ability to devise new algorithms and prove various properties about them. It is more important to learn the proving techniques and algorithm design techniques rather than memorising the algorithms covered.

There are some homework assignments in which students are required to devise and implement a solution to a well-defined problem (similar to the style of many competitive programming questions). Students can complete these assignments in either C++ or Java. These assignments are graded solely on correctness; no marks are awarded/deducted for coding style. Prior knowledge in at least one of those two programming languages is assumed — there is absolutely no C++ or Java refresher provided.

There are weekly tutorials, where the tutor goes through some tutorial questions. I suggest that students try out the tutorial questions before the tutorial, so as to get some practice on devising and proving algorithms (which is really important for the exam), and to make it easier to follow the tutor’s line of thought.

Prof Chang did not teach this module very rigorously (in the sense that there was less focus on proving the correctness and efficiency of algorithms) — he skipped over some algebraic manipulation and placed more focus on intuition instead. (For a more rigorous CS3230, I recommend taking the module under a different module coordinator.) However, his exams were well-designed — all the questions were clear, precise, and mathematically sound — so during the exam, it is generally easy to tell if the answers you have written are likely to be correct.

Midterms and finals are open-book. There are no group projects for this module.