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.