skip to primary navigationskip to content

Department of Computer Science and Technology

Undergraduate

Course pages 2021–22

Algorithms 1

Principal lecturer: Prof Frank Stajano
Taken by: Part IA CST
Hours: 12
Suggested hours of supervisions: 3
This course is a prerequisite for: Algorithms 2, Artificial Intelligence, Prolog, Randomised Algorithms
Past exam questions

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 complexity and O-notation. Trivial sorting algorithms of quadratic complexity. Review of merge sort and quicksort, understanding their memory behaviour on statically allocated arrays. Heapsort. Stability. Other sorting methods including sorting in linear time. Median and order statistics. [Ref: CLRS3 chapters 1, 2, 3, 6, 7, 8, 9] [about 4 lectures]
  • Strategies for algorithm design. Dynamic programming, divide and conquer, greedy algorithms and other useful paradigms. [Ref: CLRS3 chapters 4, 15, 16] [about 3 lectures]
  • Data structures. Elementary data structures: pointers, objects, stacks, queues, lists, trees. Binary search trees. Red-black trees. B-trees. Hash tables. Priority queues and heaps. [Ref: CLRS3 chapters 6, 10, 11, 12, 13, 18] [about 5 lectures].

Objectives

At the end of the course students should:

  • have a thorough understanding of several classical algorithms and data structures;
  • be able to analyse the space and time efficiency of most algorithms;
  • have a good understanding of how a smart choice of data structures may be used to increase the efficiency of particular 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. and Stein, C. (2009). Introduction to Algorithms. MIT Press (3rd ed.). ISBN 978-0-262-53305-8

Sedgewick, R., Wayne, K. (2011). Algorithms. Addison-Wesley. ISBN 978-0-321-57351-3.

Kleinberg, J. and Tardos, É. (2006). Algorithm design. Addison-Wesley. ISBN 978-0-321-29535-4.

Knuth, D.A. (2011). The Art of Computer Programming. Addison-Wesley. ISBN 978-0-321-75104-1.