Degrees

Data structures and algorithms

Big-O, lists, stacks, queues, hash tables, trees, heaps, sorting and graphs: how to store data and how fast you can work with it.

Course · 8 lessons · 61 min

Taught inComputer ScienceData ScienceArtificial Intelligence

  1. 1Complexity and Big-OFreeMeasure an algorithm by how its work grows with the input, not by seconds on one machine. O, Ω and Θ, the growth ladder, and how to count loops.1965–1976 · 8 min
  2. 2Arrays versus linked listsOne contiguous block or a chain of nodes: the two basic ways to store a sequence, and the trade-off in access, insertion and memory between them.1950s–today · 7 min
  3. 3Stacks and queuesTwo restricted lists: a stack takes from the top, a queue from the front. Why the restriction is useful, and where each one turns up.1961–today · 7 min
  4. 4Hash tablesTurn a key into an array index and you can find it in constant time on average. Hash functions, collisions, load factor and the attacks on them.1953–2011 · 8 min
  5. 5Trees and binary search treesA tree organises data as a hierarchy; a binary search tree keeps it ordered so a search halves the candidates at each step, if the tree stays balanced.1960–1972 · 8 min
  6. 6Heaps and priority queuesA priority queue always hands out the most urgent item. A binary heap does it in O(log n) inside a plain array, with no pointers at all.1964 · 7 min
  7. 7SortingInsertion sort, merge sort and quicksort: three ways to put data in order, what each costs, and why stability matters when keys repeat.1959–2002 · 8 min
  8. 8Graphs: BFS, DFS and DijkstraGraphs model roads, networks and dependencies. Breadth-first and depth-first search explore them; Dijkstra's algorithm finds the cheapest routes.1956–1959 · 8 min