



Next: Paper 2: Probability Up: Easter Term 2010: Part Previous: Easter Term 2010: Part Contents
Paper 1: Algorithms I
Lecturer: Dr R.K. Harle
No. of lectures: 12
Prerequisite course: Discrete Mathematics I
This course is a prerequisite for Algorithms II and Prolog.
Aims
The aim of this course is to provide an introduction to computer algorithms and data structures, with an emphasis on foundational material.
Lectures
- Sorting.
Review of insertion sort, merge sort and quicksort. Understanding
their memory usage with arrays. Heapsort. Other sorting
methods. Finding the minimum and maximum. [Ref: Ch 1, 2, 3, 4, 15, 16] [4 lectures]
- Algorithm design.
Ideas for algorithm design: dynamic programming, divide and conquer,
greedy algorithms and other useful paradigms. [Ref: Ch 2, 15] [2 lectures]
- Data structures.
Abstract data types. Pointers, stacks, queues, lists, trees. Hash
tables. Binary search trees. Red-black trees. B-trees. Priority queues
and heaps. [Ref: Ch 10, 11, 12, 13, 18, 19, 20, 21] [6 lectures]
Objectives
At the end of the course students should
- 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. New edition forthcoming in 2008.
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.
The recommended choice is Cormen et al. which covers all the topics in the syllabus of Algorithms I and II and, in spite of its quality, is the cheapest. 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.




Next: Paper 2: Probability Up: Easter Term 2010: Part Previous: Easter Term 2010: Part Contents