COMP20007: Design of Algorithms

Overview:
As the subject title says, you learn a bunch of algorithms. This includes sorting, graph, compression-related, and a bit of string-searching algorithms. You will also get a glimpse of programming approaches, including greedy algorithms and dynamic programming. Some algorithms are mind-boggling, and interesting. I found it to be a bit all over the place because of so many algorithms to learn, but this was not necessarily a bad thing.

For the first few weeks, you revise on what you've learned from first year. This included quicksort, mergesort, Big-O notation and recursive equations. Not many new things here, but you will need it for your mid-semester test. You will also go through binary search trees (BST), and a similar data structure called AVL trees at some point in the semester. Besides this, you will also learn new data structures, including disjoint-set data structure and hashing.

From there, you learn graph algorithms (a graph meaning vertices possibly connected by edges). Finding the shortest path from A to B (eg. Dijkstra's algorithm), finding the lowest number edge cost so that the edges cover all of the vertices (Prims and Kruskal's algorithm), and finding strongly connected components in a graph are a couple of things you get to learn. These seem quite practical and useful to know, so no complaints here. As an aside, I believe there was a topic that is specially covered for this year. In 2013 Euler paths were covered; this year it was about (unicost) set cover. Hence there were some irrelevant content in 2013's exams, but I think that was about it.

In learning compression algorithms, you learn techniques to encode text in order to make files smaller, for instance. These included the Shannon-Fano coding, arithmetic coding, and Huffman coding. One of the more 'mind-boggling' methods that I found were Wavelet trees and Burrow Wheel transforms. We also touched a bit on string searching algorithms, but not much on the Knuth-Morris-Pratt algorithm for instance.

Lastly, you learn dynamic programming and a bit about NP and NP-complete problems. Dynamic programming involves trying to solve a problem in polynomial time through splitting into sub-problems, and solving the sub-problems without solving the same one again. Otherwise, the idea of NP involves finding out whether a problem can be verified in polynomial time, but cannot be solved in polynomial time. We touched on this a little bit, but it was in our exam.

Aside from this, you will also learn how to do strong induction and see a bit of proof. However, it did not seem that we had to understand why a method like Wavelet Trees worked; the applying bit is more important (for those bitter in math and proofs).


Lectures and workshops:
You've probably met Andrew in COMP10001 before. He's quite friendly, explains concepts well and gets straight to the point, and his slides were easy to understand. I feel quite bad for him with the criticisms he gets from the bad structure in the assessments he gives. I found him more likeable than Alistair from COMP10002, who seemed more obscure to me despite his humor.

The accompanied book by Dasgupta also helps, and has questions probably harder than the exam. It is worth reading the relevant content in the book, since it does give more detail than Andrew's slides. Otherwise, you can also find a draft of Dasgupta's book somewhere online for free, which some people on the internet have commented that it has less typos than the physical copy of the book. However, I believe the physical copy also contains a code to obtain an online solution manual for the book, which I did not buy.

I did not attend most of the workshops, but for the first few I did attend, one hour was devoted to the tutorial questions, and one hour for a programming exercise. The questions were somewhat tough, so doing questions from the book would help. The programming exercises were easier, and were more of a way to strengthen your basic understanding of the concepts learned. Partial solutions to the workshops were given later, which would be quite helpful in exam revision.


Assessments:
For us, assignment 1 (10% of marks) involved creating an explicit stack data structure to be implemented in both quicksort and mergesort algorithms. Bonus marks also provided interesting tasks, including merging (not dividing!) with space and only using a word for a stack frame in some cases. This was more of a C programming exercise (and stuff you learned from first year) than anything else. In general, I felt the assessment was clear in what we had to do, although the bonus mark tasks were a bit confusing. We also had to do some Praze feedback after the assignment.

The second assignment was more free in what we could do. A somewhat generic set cover problem, it involved finding the minimum amount of schools such that the schools covered all of the towns, where each school covered 1km in radius. There was quite a bit to do in this assignment, which involved creating a binary min/max heap, some structure to manipulate sets (union, intersection, exclusion etc), a graph data structure and some algorithm for set cover. Fortunately, the workshops gave time to work on some of these needed data structures. Accounting for 20% of marks, cramming it was definitely a bad idea. Nonetheless, I had fun working on it, particularly on implementing an algorithm from a paper, which was a variant on the typical greedy set cover approach.

I found the mid-semester test (10%, in week 7) to be quite fair. If you have done consistent study and practice (not me, of course) throughout the semester then you should have little to no problem with it. Most of the questions were basic and just wanted to see whether you have understood it or not, while the last question was more difficult. Later we were able to get our tests back with solutions.

The exam questions from 2013 and 2014 were easier, compared to Dasgupta's exercises. Going over workshops, strengthening the understanding of concepts, understanding lectures and doing exam questions were helpful for preparation. This years exam seemed consistent in difficulty, so no shocks there. With 3 hours to finish the exam, I found it to be enough to complete most of the questions. Once more, if you were studying steadily and got your sleep, then you would have probably finished it in less than 3 hours confidently :').

In general, I found the assessments to be fair and in some way, enjoyable. It is worth remembering the algorithms after the subject also, since many of them have its practical uses. Particularly, having access to workshops, mid-semester tests and exams (and solutions) helps.


Resources:
Since the lecture slides and the book were very useful in understanding stuff, I did not really use much resources besides these. However, here are a few (the last link is if you are doing set cover ONLY, and requires you to understand proofs):

URL?	Topic:
l:m/epp.e7xtroic/tu/thy5wn	Wavelet Trees
nl:mc/ph/ii..tapmct/tmedreoh/ictpiaersieth	Arithmetic Coding
l:m/dwp.o5trvoi/ctu/thy3ln	Huffman coding
o:l/tU0p/7./4gogtAth	Set Cover

The decoding is left for you to find these links.

Yes.

Andrew Turpin

Yes.

• 2013/2014 mid-semester test and final exam, all with solutions.
• 2013 also contained a sample mid-semester and exam paper, both with solutions
• Some irrelevant content in 2013 exam, compared to this semester's content.

3.75-4.0 out of 5.0

Algorithms (by Dasgupta et al.)

2 x 1-hour lectures and 1 x 2-hour workshop, per week

Semester 1, 2015

H1

10% - Programming Assignment 1
10% - Mid-semester test in lecture
20% - Programming Assignment 2
60% - 2h exam in exam period

Great subject, if you actually had fun in first year algorithms it’s totally worth doing this subject even though it covers slightly more/harder stuff than the second semester equivalent ‘Algorithms and Data Structures’. I personally found it all really interesting! I was also the student rep for this subject.

The assignments are a fair bit of work to understand and then actually code up, and basically no time is spent on writing C code in lectures it’s all assumed from first year. This caught the whole cohort off guard in the first assignment which assumed a lot of C skill that people hadn’t used in a while, and there wasn’t much help available.

That said, the subject isn’t about C code or any code really, it’s about the algorithms and all mid semester test/exam questions that require code just want pseudocode english descriptions of what you would do. This allows us to go into detail on some of the most foundational data structures and algorithms in computer science like graph algorithms and balanced tree data structures. We also covered some very interesting computing topics in the second half of the course including compression theory, greedy algorithms, dynamic programming and NP-Completeness. Fun!

The exam stepped up from past years, which Andrew told me after it was finished, because ’too many H1’s’ in previous two years. So that was a surprise but it was still a completely accessible exam that tested us fairly on the stuff we had studied. No big surprises.
EDIT: Now that marks are back it looks like I got 73/80 on the exam (assuming no scaling) which is probably fair even though I was aiming for full marks sadface.


Overall, this was my favourite subject this year because of the interesting and intuitive content covered. Recommended if you enjoyed the first year subjects and were curious the whole time about what else you can do to solve computing problems!

Yep! Recordings and slides are great

Andrew Turpin (with two guest lectures, from Alistair Moffat and Mathias Petri)

Yes, 2013 and 2014 with solutions (so 2015 too i guess if you do it in 2016)

5/5

Not required, slides are enough, but Dasgupta’s ‘algorithms’ covered most of the stuff in the course, and is pretty good. There's also MIT's 'Introduction to Algorithms' (and their opencourseware subject of the same name, which I did watch all the lectures from), which cover the material in a lot more depth than required for this subject.

2x 1h lecture, 1x 2h workshop (half theory, half coding)

2015 Semester 1

95 (H1)