**Subject Code/Name:** COMP20007 Design of Algorithms**Workload:** 2 x 1-hour lectures and 1 x 2-hour workshop, per week

**Assessment:**- 10% Assignment 1
- 20% Assignment 2
- 10% Mid semester test (<1 hour)
- 60% End of semester exam (3 hours)

**Lectopia Enabled:** Yes.

**Past exams available:** 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.

**Textbook Recommendation:** Algorithms (by Dasgupta et al.)

**Lecturer(s):** Andrew Turpin

**Year & Semester of completion:** Semester 1, 2015

**Rating:** 3.75-4.0 out of 5.0

**Your Mark/Grade:** H1

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