Applied Algorithmics: COMPSCI 320 Semester 2, City Campus

Algorithmics is the systematic study of the design and analysis of algorithms. It deals with such fundamental questions as: How do we go about designing an algorithm for a given problem?, Is the algorithm correct?, Does it perform efficiently?, and Is it the best possible for the job?. Algorithms form the soul of Computer Science, and consequently the study of algorithms is a fundamental activity of the Computer Scientist.

In this course we study fundamental design paradigms: greedy algorithms, divide-and-conquer, dynamic programming, and exhaustive search. We focus on methods for developing algorithms which are both correct and efficient. We analyse the efficiency of algorithms so that we have a basis for deciding which algorithm is best for the job. Finally we discuss limits on the power of computers by showing that there are many problems where an efficient solution is unlikely to exist. These limits are provided by the theory of NP-completeness.

These are based on lectures, graded assignments, and your detailed reading of your course textbook and other books. All of these ingredients are necessary if you are to get the most out of the course.

There will be written and programming assignments (3 each) worth 30%; the mid-term test is worth 10%, and the final exam is worth 60%. To pass the practical component of this class, you must get at least 5 (out of 15) marks in both the written and programming assignments. To pass the written component of this class, you must get at least 35 (out of a total of 70) marks in the test and exam. To get a passing grade in the course, you must get at least 50 of the total marks (100) in the course, and you must get a pass in both the practical and written components.

The main textbook for the course since 2008 is:
J. Kleinberg and E. Tardos: Algorithm Design, (Addison Wesley 2006).

There are several good books on reserve in the library. In addition, here are some others that may be of use.

• G. Brassard and P. Bratley: Fundamentals of Algorithmics, Prentice-Hall, 1996.
• G. Rawlins: Compared to what? An introduction to the analysis of algorithms.
• D. Harel: Algorithmics, the spirit of computing.
• S. Skiena: The Algorithm Design Manual.
• A. Levitin: Introduction to the Design and Analysis of Algorithms.
• Purdom, Purdom and Brown: Analysis of Algorithms.
• R. Sedgewick and P. Flajolet: Introduction to the Analysis of Algorithms.

For assistance with course material and course work you should visit the marker during his office hours. Assistance can also be obtained from course lecturers during their published office hours or from the course supervisor. The Department of Computer Science also has a team of support staff (see the posters around the labs for support contacts) who are happy to provide guidance on more general issues to do with your study in computer science.

Catching up on missed lectures and labs
If you miss a lecture, you should catch up as soon as possible by reading the corresponding sections of the textbook. If you miss the deadline for an assignment and have a valid reason, you should see the course supervisor. If you miss the test/exam for any valid reason, or you sit the test/exam but believe that your performance was impaired for some reason, then you may be able to apply for an aegrotat, compassionate or special pass consideration.