**Subject Code/Name:** COMP3821 - Extended Algorithms and Programming Techniques**Contact Hours:** 2x 2 hour lectures

**Assumed Knowledge:** 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.

**Assessment:** 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%.

**Lecture Recordings?** 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).

**Notes/Materials Available**: 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.

**Textbook:** 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.

**Lecturer(s):** Dr. Abdallah Saffidine

**Year & Trimester of completion:** 20T1

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

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

**Your Mark/Grade:** SY (unofficially I would've gotten 100 using my raw assignment marks)

**Comments:** 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