Undergraduate Teaching 2023-24

Engineering Tripos Part IIB, 4M26: Algorithms and Data Structures, 2023-24

Engineering Tripos Part IIB, 4M26: Algorithms and Data Structures, 2023-24

Not logged in. More information may be available... Login via Raven / direct.

PDF versionPDF version

Module Leader

Dr S Albanie

Lecturers

Dr S Albanie & Prof Per Ola Kristensson

Timing and Structure

Lent term. 16 lectures (including 3 examples classes).

Aims

The aims of the course are to:

  • Introduce the principles behind algorithm and data structure design and evaluation.
  • Cover key topics including elementary and advanced data structures, sorting algorithms, graph algorithms, etc.
  • Provide an extensive hands-on understanding of the aforementioned topics via coding-focused computerised examples papers and exam.

Objectives

As specific objectives, by the end of the course students should be able to:

  • Analyse computational efficiency of most algorithms.
  • Re-implement and debug algorithms taught under time constraints.
  • Correctly choose the right algorithmic solution and data structures for the problem encountered.
  • Understand relative theoretical and practical advantages and disadvantages of various methods.
  • Devise and implement new algorithms or modify existing algorithms to solve previously unencountered tasks.

Content

  • Introduction (1L)
    • Algorithms and Data Structures: what are algorithms, why study algorithms and how? Introduction of the coding platform and other resources. Applications.
  • Fundamentals of Algorithms (2L)
    • Elementary data structures - stacks and ques, linked-lists, arrays, dictionaries. Algorithmic complexity. Strategies for algorithmic design: divide and conquer, dynamic algorithms, greedy algorithms.
  • Advanced Data Structures (2L)
    • Hash tables, binary search trees, red-black trees, B-trees.
  • Sorting Algorithms (2L)
    • Sorting algorithms - Heapsort, Quicksort, sorting in linear time.
  • Graph Algorithms (3L)
    • Graph algorithms - shortest path (BFS, DFS, Dijkstra, Bellman-Ford), topological sorting, strongly connected components, maximum flow (Ford-Fulkerson), minimum spanning trees (Kruskal’s, Primm’s).
  • Further Topics (2L)
    • Parallel algorithms, NP-completeness
  • Recent Developments (1L)
    • Large language models for code generation.
  • Example classes (3L)
    • Discussion of examples papers and past examination papers.

Booklists

Introduction to Algorithms (3rd ed) by Cormen, T., Leiserson, C., Rivest, R., Stein, C. The MIT Press. ISBN:978-0-262-03384-8.

Also, please refer to the Booklist for Part IIB Courses for references to this module, this can be found on the associated Moodle course.

Examination Guidelines

Please refer to Form & conduct of the examinations.

 
Last modified: 01/10/2023 20:27