Optimisation Algorithms: CS4234 Review

Contents are as follows:

1. General practical approaches to NP-Hard problems
2. (Constant Factor) Approximation Algorithms
3. Steiner Trees (Algorithms not discussed in-depth)
4. TSP variants and (or impossibility of) approximation
5. Maxflow Problems and Algorithms
6. Matching Problem Variants and Algorithms
7. Stochastic Local Search: Design, common approach, metaheuristics, tuning, and research.

Preface and tl;dr:

I have some strong personal opinion on the structure of the course, but content-wise this is an extremely well-executed course for introducing state-of-the-art practical approaches to solving general problems involving optimization algorithm design or lack thereof.

Assignments are doable within a reasonable time and you always have people to help you if you need any. Lectures are alright in vibe but fun in content -but I might be biased as I will explain later. Tutorials are extremely fun as tutors are able to guide the class even though the class (my class especially) was constantly filled with discussion and ideas flowing from the students. Assessments are not alright but they're fun anyway.

The median of this course is approximately mid A for CS3230 and there is absolutely no way anyone can convince me otherwise. Take this course only if (a) you're already pretty good at everything that's about to be taught, or (b) you think you will enjoy the after this long review regardless of your grade.

Stats

Keep in mind before seeing this section that I had absolutely no problem understanding anything in CS3230, did rather well there, did a research internship involving some parts of this course before, and like learning algorithms generally. That said, with 0 being nothing, 5 being neutral, and 10 being the maximum, the following are the stats for CS4234:

What the Course is About

Prof Halim is a Competitive Programming-oriented person and is very fond of having competition between (smarter) students; thus, the course is implicitly designed around this premise of how exhilarating competition between students is making them excel more whilst maintaining the fun. However, I personally believe that this is not exactly the right thing to do. I will elaborate throughout this whole review.

Most of the contents taught have been taught before (I took 3230 under Arnab, not under Halim). The first half of CS4234 that introduces maxflow, constant approximation algorithms, and basic matching, had all been covered in CS3230, while basic SLS was already discussed partially in CS2109S. Unlike CS3230 that introduces these topics as "here is one category of approach to solve a problem", Prof Halim focuses on the practical implementation aspects of these algorithms with most of them being in the context of competitive programming. Example:

After deducing that a problem statement reduces to minimum vertex cover at first glance (meaning this problem looks like MVC but might not be as hard) which is known to be NP-Hard in general, we observe further and found that we can exploit some specific details of the problem statement to instead make the graph bipartite. We can therefore, by Kőnig's theorem, run Maximum Cardinality Bipartite Matching (e.g. Dinic's) algorithm to find the cover in polynomial time.

Notice how, unlike CS3230 which teaches "some problem categories are NP-Hard" or "there is this category of technique called incremental algorithm", CS4234 focuses on improving the students' acuteness in observing specific patterns of hard problems whilst training them to use the tools they already have in their arsenal (sometimes in a clever way) to tackle said problems.

I claim that there are only two ways you can be good (as in get a good grade) in this course:

1. You are trained in using the tools you already have in your arsenal (e.g. you're a seasoned competitive programmer with >1700 CF rating), or
2. You have a certain knack in observing CS-related patterns (i.e. you have no problem getting divine inspirations) --which usually means you have >1700 CF rating

Usefulness (?)

During my last internship right before I took this course, I had encountered novel problems that requires me to read through some systems/algo papers and implement them. Some of these involve constant factor approximation algorithms, SLS (simulated annealing), Steiner point insertion, and FPTAS.

Although CS4234 touches some of these topics, I still believe that if I had taken CS4234 beforehand, I would not have been better off in reading or implementing what's on those papers: The first half of CS4234 is either too detail-specific (e.g. explaining how various flow/matching algs work to solve specific kinds of competitive programming problems) or too theoretically-broad (e.g. only introduces very common p-approx algos), and the second half is the kind of topic that is very intuitive after you got exposed to it once -meaning you could get the hang of it easily yourself by reading the reference book when you encounter SLS-related problem later in the future (in my case I encountered q a few time since I also do transport geography).

I strongly advise you to read the previous paragraph again as I try to soften my comments on the usefulness of this course. I added a more explicit comment in the summary.

That said, the amount of competition forced me to at least get the trivial parts of the assessment i.e., CS2040S/CS3230 materials correct by revising them over and over again. Furthermore, the problem sets and tutorials are very useful to me as a person who barely had any exposure in competitive programming prior to taking the course.

Gripes

However, is this really what the course is trying to teach? Is it the goal of an advanced algorithms course for students to spend their time on memorizing implementation details of variants and subvariants of SSSP algos, practice tracing Kuhn-Munkres, reducing constant factors in their codes to pass the PS, practice eyeballing K7 TSP instances, etc.? I would argue that those are non-essential aspects that ought to be removed and can only be done if the tie between this course and CP is severed or weakened, and the non-essential parts removed.

IMO, written assignments with pseudocode and timely feedback (like midterm), and simple quizzes (like CS3210) is sufficient for the students to practice and internalize the concepts taught. Doing this and reducing the amount of implementation-specific details required to do CP will enable the students to have more time to explore the state-of-the-art researches in-depth, discuss broader amount of theory, and practice the science part more.

Practical coding knowledge is important, but it's not this particular course's responsibility to ensure that exists.

But wouldn't this make the course easier??

I understand the fun nature of competitiveness and the urge to "differentiate" the students; I, too, am excited on courses where I can have clear advantage over other people (whom I genuinely am saddened to see) that is then materialized in my A+. However, is that necessary? What's wrong in giving credit where credit is due anyway and test more towards the mastery of the course, rather than being a spectator to a really exciting match (midterms/finals) to see which student has the fastest access to the Vault of Divine Inspirations?

I did not fare well in the exams overall (surprisingly I did rather well in the finals' MCQ -whatever that means, but it's still a little comforting to know I'm not really THE problem) so I might be a little biased in giving this suggestion, but I try not to have any. I guess my gripe in this section can then be summarized into the following:

Is it necessary to execute the course in a certain (CP) way over the other? At what cost?

Comments on Some Parts of Contents

David Cohen-Steiner was one of the authors that often got referenced in the algorithms I read during my work involving spanning trees (for SLAM systems) or surface reconstruction (via wrapping algorithms) for his work which was briefly mentioned in this course (Steiner points). Unfortunately, this was never discussed any further in the class beyond "adding Steiner points is hard" and one or two MCQ problems in class. To be fair, there will probably be too much content involving this, but idk this one topic feels very out of place in the end.

Around half of the course (exaggeration) is about discovering the amazing neatness of bipartite graphs and its exploitation; however, during my short practical work experience and after doing some pondering, I realized that graphs are rarely bipartite (unless you're doing CP).

Matching, maxflow, and p-approx algorithms are just what they are and there's nothing to comment on.

What I'm trying to say is that content-wise there's really not much things to say, which is quite a bummer.

Assessments

I have nothing to say for the project part as I think it's just fine other than it's not as fun because we don't know how much we should copy off-the-shelf library codes and everyone just sorta do that in the end. I have no further comment on problem sets as I've talked about them in-depth above.

Midterm was not alright as it's just too heavy on 2 parts (out of four) that requires too much cleverness. I sincerely believe that almost all efforts I spent on learning what's taught prior is useless beyond rewarding 30-40 out of 100 points.

The quiz was so random and out of place that I still believe that it should be eradicated for the ridiculousness of the questions.

Finals, surprisingly, was ok-ish? (by the time I write this I haven't gotten my results). The MCQ part especially was extremely rewarding for me as it requires nontrivial knowledge you learn from the course. However, the competitiveness of the finals is on thinking speed (which I unfortunately lack compared to most other people taking the course): I ran out of time to do the last question after reading it (turns out everyone else also ran out of time and the highest score was <80/100). Again, I don't know why do this only for differentiating the (smartest) people if the purpose is actually testing knowledge taught by the course. Delete part D of the exam and you'll probably get a really good and fair test.

Afterword

Prof Halim is an extremely great teacher (so was my tutor, Zheng Han) in what they teach. This course was one of the most exciting courses I've ever taken where I looked forward to every tutorial and lecture. I met nice friends in this course, and I am grateful that I now have more exposure on the implementation side. However, I disagree with the content of the course and how they're assessed despite some learning benefits I get from trying to compete to not get an abomination of a grade.

Even though I tried my very best in this course and had fun doing so, it would be really hard to convince me that this course is more than that (which it should have). If you're not extremely confident in your brain, I am recommending you NOT to take this course unless, like me, you just like doing it.

ps

Just in case it's not clear enough, the materials in this course is very CP-oriented for arguably no good reason. This is not the course you'd like to take if you're seeking to have fun learning optimization algorithms thoroughly; it lacks stronger theoretical basis, overlaps a lot with other courses, and it lacks the usefulness that it should have had -had the course focused less on CP or Prof Halim's CP students.