• 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, divide-and-conquer, 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 NP-completeness.
    • Textbook: Brassard & Bratley: Fundamentals of Algorithmics, Prentice-Hall (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 mid-term is worth 10%, and the final exam is worth 70%. There is no computer programming! The mid-term test was scheduled for 14 September 2000, time 6.00pm-7.00pm, SLT1.
    • For queries or related matters send me an email.