This course is a prerequisite for Algorithms II, Computer Graphics and Image Processing, Complexity Theory, Artificial Intelligence I.
Aims
The aim of this course is to provide an introduction to computer
algorithms and data structures, with an emphasis on foundational
material. It is suitable for people who did not take discrete
mathematics in Part IA.
Lectures
Discrete Mathematics. Common mathematical notation. Proofs.
Induction. Sets, tuples, functions. Relations and Graphs.
Combinations and permutations. [Ref: Ch 1; App B, C] [3-4
lectures]
Algorithm Fundamentals. Algorithm analysis and design.
Models of a computer; costs. Asymptotic notation. Computational
complexity. Recurrences. Ideas for algorithm design: divide and
conquer, dynamic programming, greedy algorithms and other useful
paradigms. [Ref: Ch 1, 2, 3, 4, 15, 16] [2-3 lectures]
Sorting. Insertion sort. Merge sort. Heapsort. Quicksort.
Other sorting methods. Finding the minimum and maximum. [Ref: Ch 2,
6, 7, 8, 9] [4-5 lectures]
have a good understanding of how several fundamental
algorithms work, particularly those concerned with sorting and searching
have a good understanding of the fundamental data structures
used in computer science
be able to analyse the space and time efficiency of most
algorithms
be able to design new algorithms or modify existing ones for new
applications and reason about the efficiency of the result
Recommended reading
* Cormen, T.H., Leiserson, C.D., Rivest, R.L. & Stein, C. (2001). Introduction to Algorithms. MIT Press (2nd ed.). ISBN 0-262-53196-8
Sedgewick, R. (2004). Algorithms in Java, vol 1. (note that C and C++ editions are also available and are equally good for this course). Addison-Wesley. ISBN 0-201-36120-5.
Kleinberg, J. & Tardos, É. (2006). Algorithm design. Addison-Wesley. ISBN 0-321-29535-8.
Knuth, D.E. (1997). The art of computer programming (three volumes so far; a boxed set is also available). Addison-Wesley (3rd ed.). ISBN 0-201-89683-4, 0-201-89684-2 and 0-201-89685-0.
Students are expected to buy and make extensive use of one of the
above references: those not doing so will be severely disadvantaged.
The easiest and recommended choice is Cormen et al. which
covers all the topics in the syllabus: the pointers in the syllabus
are to chapters in that book. The other textbooks are all excellent
alternatives and are sometimes clearer or more detailed than Cormen,
but they are not guaranteed to cover every item in the syllabus. Their
relative merits are discussed in the course handout.