# Applied Algorithmics: COMPSCI 320 Semester 2, City Campus

Objectives

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? Is it the best possible for the job? Is there any good algorithm for this problem?

It has been said that algorithms form the soul of computer science. Certainly the study of algorithms is a fundamental activity of a computer scientist. It is also very useful for those interested in programming competitions and getting past the interview process at companies like Google!

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.

Learning Activities

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.

Top
Assessment

There will be written and programming assignments 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 33% 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 in the course, and you must get a pass in both the practical and written components.

Top

You should read (at least) one of the following textbooks for the course. These should be on reserve in the library.

• S. Dasgupta, C. Papadimitriou and U. Vazirani: Algorithms (1st Ed), 2008.
• J. Kleinberg and E. Tardos: Algorithm Design, (Addison Wesley 2006).
• G. Brassard and P. Bratley: Fundamentals of Algorithmics, Prentice-Hall, 1996.
• T.H. Cormen: Algorithms Unlocked (ebook) , 2013
• J. MacCormick: Nine algorithms that changed the future: The ingenious ideas that drive today's computers, 2012.
• S. Skiena: The Algorithm Design Manual (ebook), 2009.

Top
Seeking Assistance

For assistance with course material and course work you should arrange to discuss with the tutor. 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.

Top