COMP3821: Extended Algorithms and Programming Techniques

Obviously because of COVID-19, assessment changed for this course. In 20T1, our assessment was entirely composed of written homeworks/assignments:
- Assignment 1, worth 10%
- Assignment 2, worth 30%
- Assignment 3, worth 30%
- Assignment 4, worth 30%

The original plan for the course however was to have both an in-person midterm and final exam worth 40% each with 2 assignments each worth 10%.

Formally, there is one simple requirement:
- COMP2521 with at least a CR grade (65+)

If you ask me though, this particular course is probably best suited to students with a top-end DN and HD grade. This course is also rather math heavy; be very prepared to wrangle with some ugly summations and complex number theory in some topics.

I suppose I should start with the good points. I found the content in this course quite interesting, and I think you will too if you’re an algorithms kind of person. My favourite part of this course was probably the intractability and introduction to computational complexity theory at the very end. Around midway through we had a talk by Dolby engineers at the end of the FFT topic to relate it to the real world was also interesting, even if it really was just listening to someone shill a company for 2 hours. I will say that this course definitely has some career value despite it being a bit theoretical, since you learn a few of the more advanced programming techniques to help you with some of those harder technical interview questions you might face when looking for work.

So, the million-dollar question you’re all wondering: should I do this course over COMP3121? My answer for the time being, despite all of my glowing comments above, is no. Aleks still takes 3121, and 3821 under his control was well-regarded, so I would say that is the safe option for now. 3821, unfortunately, has some issues. With that said, allow me to rant a little.

I find it hard to reason what is “Extended” about this course over its normal counterpart, COMP3121. If you look at the course materials right up until 2018, the distinction is pretty clear; for example, there used to be an extra question or two for the 3821 students in the midterms which were either harder applications of the base content, or some various questions with probabilistic twists and such. Nowadays though, I struggle to notice such a difference. I asked for clarification from Song, the person who ran our Piazza forum during the term (massive props to him, by the way), and he had this to say:

“Sore topic unfortunately. Before trimesters, the extended course included Randomised Algorithms (hashing, skip lists, etc.), Order Statistics, Resource Allocation, a bit of Complexity Theory, and also approximation algorithms for NP-C problems, while the regular course covered everything up to DP and then also LP, Max Flow, Intractability, and String Matching. After trimesters, the extended course no longer received its additional lecture hour and so all of that had to be cut. Currently, you've got the allocation (LP, intractability) pretty spot on. The regular version last year was not able to cover LP, Intractability, or String Matching but they did cover Max Flow. This was not entirely intentional, so I'm not too sure what Aleks' plan will be this year. Prior to COVID-19, we did also plan to cover Max Flow in extended, but alas."

It seems then that there is some difference, and that nowadays 3821 has been reduced to what 3121 used to be pre-trimesters sans a couple of topics. Moreover, it seems like a lot of the extra content that has disappeared instead appears in COMP4121 now. I think one big step towards making the course worthy of the “Extended” title would be to have an extra tutorial/lecture hour every now and then to build upon some special interest topics or the base theory common to both 3121 and 3821.

I’d be remiss if I didn’t talk about the organisational issues this course has had since 2019. At the same time, I’ll cut the course staff some slack here. I was actually satisfied with the organisation of this course for the most part until the university shut down and we all transitioned to online learning. But after that, this course became a bit of a nightmare. It was mostly a lack of communication; the alternative plan for our midterm was quite drawn out (as in, it took a couple of weeks for them to decide what to do), and the future of lectures going forward was significantly drawn out (although we learned in week 10 that there was a good reason for this). I don’t know if Aleks had the same problems when he ran this course as well, and I do genuinely think Abdallah is a good lecturer, but at the same time I think based on my own experience and the things I heard about the 2019 run of this course that the administration side of the course has declined from Aleks’ days. I know the pandemic did absolutely no favours for any course, but I think my observations are more general about the way this course is now run. My only hope is that there’s enough constructive feedback left during MyExperience for them to make the changes which need to be made.

It’s a real pity. Put simply as possible, I think the course has just lost itself after the trimesters move. I don’t know what the future will hold for this course, but I hope it’s good. One other idea I heard while talking to some other students was that maybe what’s best for the course is if it split into two separate courses, one focusing on the more practical aspects of the course (essentially the first half), and one on more theoretical, less practically-minded content (linear programming, intractability). That way, each course has its own more significant window of time to build upon content. Maybe that would be the best path for this course going forward.
/rant

2x 2 hour lectures

3.5/5, though some interesting questions came up in the assignments which would probably be a 4/5 or higher.

Yes, but towards the end of the term owing to some personal problems by the lecturer, we were instructed to watch the 2019 lecture recordings or those of earlier runs of the course conducted by Aleks (some of which are on YouTube).

Dr. Abdallah Saffidine

Lecture slides are the primary resource in this course. A bank of past assignments, midterms and final exams should also be gradually released to you as appropriate, filling the noticeable void of any regular exercises like a problem set or lab exercises you may be perhaps otherwise used to.

Content is a 4/5, course itself is maybe a 1.5/5 for reasons I will soon explain.

Both of these textbooks are recommended, but my personal preference is the first one:
- T. Cormen, C. Leiserson, R. Rivest, C. Stein, “Introduction to Algorithms: Third Edition”, The MIT Press (2009)
- J. Kleinberg, E. Tardos, “Algorithm Design”, P&C ECS (2005)

Neither book is mandatory for the course but I think it is absolutely essential due to how self-driven the course is in reality.

20T1

SY (unofficially I would've gotten 100 using my raw assignment marks)

For our year:
- 2 assignments, individual weighting unknown but combined to 20% total.
- 40% midterm w/ 1 page cheat sheet
- 40% finals w/ 1 page cheat sheet
Supposedly there were bonus marks for active contributions on piazza, but I have no idea how that worked out.

Only COMP2521. (For the extended version, at least 65 in COMP2521 is required.)

This course is the extended version of COMP3121, which is now core to computer science majors. (Basically the higher version.)

To be honest, despite somehow coming out alright, I was very disappointed by this course. I can never complain about 20% raw scaling, but after the bomb that was the mid-term (completely changed format, somewhat unrealistically spiked difficulty, pseudocode in the exam and also harsher marking criteria) this course became a huge trauma for a while. It was a huge struggle convincing myself to not drop this course in favour of the ordinary version later on.

Pseudocode is new to this course it seems. Not my cup of coffee, but not impossible to bear with for an assignment.

I do suspect that the course being hyped by not just like one person but several of my peers had an impact on this. I came into this course expecting a lot of things to be different.

Amazingly I found myself a bit rubbish at dynamic programming. Two tips about it: 1. don't expect good complexity all the time and 2. avoid greedy! I kept sidetracking into trying to find a greedy solution at time and had to remind myself "no that's not the way to do it".

NP-Completeness was new to the exam. It can occasionally get a bit challenging - make sure to think about those problems!

Wasn't the worst course I've done at the university though. At the very least the course is properly split into two halves. The midterm only examined the first half of the course, whilst the finals examined only the second half.

2 x 2hr lectures. (No tutes)

4/5

Yes

Dr. Abdallah Saffidine

Same lecture slides as has always been used for this course. The support staff that marked some of our solutions shared a reasonably large bank of past papers for the midterms/finals and also a piazza forum.

1.5/5

- Cormen, Leiserson, Rivest and Stein - Introduction to algorithms
- Kleinberg and Tardos - Algorithms design
Used the latter to help me learn NPC - that was useful at least.

19t2

94 HD

Prerequisites:

So far, my absolute favourite COMP course. The course focuses on problem solving, and a lot of it is trying to give you the tools to apply various algorithms to different problems, and adjusting them where needed. The extended content goes into randomised algorithms, which was my favourite topic of the course. It is certainly a difficult course, but is very very fun, and I would 100% recommend it. I only attended a few lectures, but Aleks explains the concepts well, and is very helpful if you attend the consultations. If you're on the fence about doing it, take a look at the questions in the final exams, and see if they're the kind of question you like.

1x 2hr + 1hr Lecture, 1x 1hr Lecture (extended class)

4/5

Yes - screen and voice recorded, as well as some videos of the lecture on YouTube as the blackboard was used regularly (especially in the extended lecture)

A/Prof. Aleks Ignjatovic

All lecture slides posted online, and past final exams available. Example midterm was supplied, and a list of problem solving questions was posted in preparation for both the midterm and final.

5/5

Note: I don't use textbooks and can't comment on their usefulness. One of

2018 S1

99 HD