The course will cover the following subjects:

  • Basic data structures and algorithms: binary search, self-resizing arrays and linked lists

  • Big-O complexity and how to reason about it, in iterative and recursive programs

  • Sorting algorithms: O(n^2) (insertion sort, quicksort), O(n log n) (mergesort), O(n) (e.g. counting sort)

  • Data structure invariants

  • Binary search trees, balanced binary search trees (AVL trees, AA trees), 2-3 trees

  • Stacks; queues implemented using a circular array or a pair of stacks

  • Hash tables, binary heaps, skew heaps, skip lists

  • Graphs; Dijkstra’s algorithm; Prim’s algorithm

You can find the official syllabus here.