 Title: Algorithmics 415.320SC
 Credits: 2 Points
 Lecturers: Dr Michael J. Dinneen (supervisor),
mjd@cs.auckland.ac.nz and Professor Cristian S. Calude, ext 5751,
cristian@cs.auckland.ac.nz
 Taught: Second semester 2000, three lectures a week.

Timetable: 9.00  10.00 am on Tuesday, Wednesday, Friday
 Short Description:
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 paper we study greedy algorithms, divideandconquer, dynamic
programming, graph techniques, and probabilistic algorithms. We focus on methods for developing algorithms
which are both correct and efficient. A fundamental tool is that of mathematical induction which can be used
not only to verify that a given algorithm does the job intended, but which also assists in designing the
algorithm in the first place, and in generating a proof of correctness along the way. 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 NPcompleteness.
 Textbook:
Brassard & Bratley: Fundamentals of Algorithmics, PrenticeHall (1996).
 Assignment 1
Assignment 2
 Complimentary notes
 Assessment: There are four assignments designed to complement the material from class, as well
as the reading from your textbook. Assignments are due at the beginning of lecture
on the date specified. Each one of the assignments is worth 5%, the midterm is worth 10%, and the final exam is worth 70%.
There is no computer programming!
The midterm
test was scheduled for 14 September 2000, time 6.00pm7.00pm, SLT1.
 For queries or related matters send me an
email.