Lectures: Data Structures and Algorithms

Spring term. Last update: 2022-07-27.

This is a joint lecture for the ICY and MSc students.

Overview

  1. Abstract data types, our memory model, arrays, linked lists (slides)
  2. Stacks, queues, circular queues (slides)
  3. Time complexity, O-notation, Binary Search (slides)
  4. Amortized complexity, dynamic arrays, binary search trees (slides)
  5. AVL trees, Fibonacci trees (slides)
  6. Priority queues, binary heaps, storing heaps in arrays (slides)
  7. Sorting, selection sort, heap sort (slides)
  8. Divide and conquer sorting algorithms: Merge sort, quick sort (slides)
  9. Hash tables, sticking-out vs tucked-in strategies, double hashing (slides)
  10. Graphs and their representations, Dijkstra’s algorithm, Jarník-Prim algorithm (slides)

Exercises (roughly following the above structure): Week 1, Week 2, Week 3, Week 4, Week 5, Week 6, Week 7, Week 8, Week 9, Week 10

See also John Bullinaria’s website for material for the first year students.

Web Analytics