COMP3600

Runs	Semester 2, every year
Languages	Your choice of C, C++, or Java
Lecturers	Hanna Kurniawati
Course website	https://comp.anu.edu.au/courses/comp3600/

As the name suggests, COMP3600 is a course about algorithms and data structures, two of the foundational aspects of computer science. Hence, it is a compulsory course for many degrees. It is generally regarded as a hard course, due to the difficulty of the proofs required (see below for commentary and preparation recommendations). The course focuses on theory and problem solving; programming is only required for a small portion of two of the assignments.

The first portion of the course focuses on the analysis of algorithms, including proofs of computational complexity. The second part explores a variety of data structures, including heaps, binary search trees, AVL trees, red/black trees, and hash tables. The course then focuses on algorithm design techniques, including dynamic programming and greedy algorithms. Finally, problem complexity classes are briefly explored (including P, NP, NP-hard, NP-complete).

Assessment for the course consists of three assignments (20% each) and a final exam. The assignments all consist of algorithm design, analysis and complexity proofs. Assignments 2 and 3 additionally have a programming component, where you will be expected to design, implement and evaluate an algorithm to solve a problem. You are given a choice of 3 languages (C, C++ or Java), however support is only given for C++ (which is briefly taught in one of the labs). The use of Java is not recommended by the lecturers, but it will do if you don't want to learn a new programming language (C and C++ are both very useful for future study however, so consider giving it a go!). The exams are similar to the assignments, but with no programming. Generally speaking, 80% of the marks in this course are dedicated to your reasoning and proofs, so don't be tempted to skip straight to the answer (however obvious it may seem!).

If you're like most computer science students and MATH1005 is the only maths course that you have taken, it is likely that you will find the proofs very difficult. Additionally, the BAC/BAC(R&D) degree plans both list COMP3600 in second year, despite the fact that it is a third year course. Because of this, the teaching staff often overestimate the prior knowledge of students taking the course. Hence, many students struggle with this course, and it is rumoured to have a high failure rate.

To improve your chances in this course, it may be worth delaying it until third year or taking an extra MATH course. If you are mathematically inclined, taking MATH1115 in your first year is extremely good preparation for this course - many of the 1115 proofs are similarly structured to algorithmic complexity proofs. Other proof-based maths courses (e.g. MATH2222) would be helpful for similar reasons. However, these are also considered to be very difficult courses, so don't consider them a necessity by any means. If you want to prepare for the course in your own time, a review of basic calculus (mainly differentiation of polynomials), L'Hopital's rule, limits, logarithms & logarithm transformation rules (particularly in base 2), and probability will be helpful.

The CLRS textbook (Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein) is a very helpful companion to this course, as tutorial questions are often taken from this book, and algorithms from the textbook can be helpful for solving assignment questions. However, it is very formal and mathematical; if you would prefer a more approachable introduction to algorithms, you may like The Algorithm Design Manual by Steven S. Skiena.