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.