Skip to the content

/

Algorithms

C++20

Algorithms: 0% done

Module 1 · What an algorithm is

An algorithm is a recipe a machine could follow

Loading the slide…

A line of words about as long as a slide’s first line, and its second.

Another line, shorter.

1 / 194 · What an algorithm is

Course progress

0%

An algorithm is a recipe a machine could follow
, 1 to practiseYou already run algorithms every day
, 1 to practiseA good algorithm is correct and finishes
, 1 to practiseFrom steps in words to pseudocode
, 1 to practiseFrom pseudocode to C++
, 1 to practiseTrace it by hand on a small input
, 1 to practiseTry it: find the largest score
, 1 to practiseThe same idea works on structs
Recap

Speed depends on how much input there is
, 1 to practiseCount what runs for each element
, 1 to practiseBig O keeps only what matters as n grows
, 1 to practiseThe common growth rates
, 1 to practiseReading Big O from loops
, 2 to practiseTry it: count the comparisons
, 1 to practiseMemory counts too: space complexity
, 1 to practiseBest case, worst case
See the difference: time it
Recap

Searching means: is it there, and where?
, 1 to practiseLinear search in code
, 1 to practiseThe standard library’s searches are linear too
, 2 to practiseTry it: write linear search
, 2 to practiseSearching with a condition
, 1 to practiseStop as soon as you know
, 1 to practiseEdge cases: empty, missing, and index 0
, 1 to practiseSearching records by a field
Recap

, 1 to practiseA sorted list can be halved
, 1 to practiseTracing binary search
, 1 to practiseBinary search in code
, 1 to practiseTry it: write binary search
, 2 to practiseThe off-by-one traps
, 1 to practiseLower bound: where it would go
, 1 to practiseTry it: how many can I afford?
, 1 to practiseSearching for an answer
Linear against binary, and the library’s versions
Recap

, 1 to practiseSorted data is easier to use
, 1 to practisestd::sort puts things in order with <
, 1 to practiseA comparator tells sort which comes first
Bubble sort swaps neighbours until nothing moves
, 1 to practiseSelection sort picks the smallest each time
, 1 to practiseInsertion sort is how you sort a hand of cards
, 2 to practiseTry it: write insertion sort, and use a comparator
, 1 to practiseA stable sort keeps ties in their original order
, 1 to practiseThese sorts take n² steps, except on nearly sorted data
Recap

A recursive function solves a smaller copy of the problem
, 1 to practiseEvery recursion needs a base case it is sure to reach
, 2 to practiseThe call stack remembers every call that is waiting
, 1 to practiseA list is its first item and the rest
, 1 to practiseRecursion is natural for nested data
, 1 to practiseToo deep, and the stack overflows
, 1 to practiseRecursion and loops can do the same work
Recap

Divide and conquer: split, solve, combine
, 1 to practiseMerging two sorted piles is easy
, 1 to practiseTry it: merge two sorted lists
, 1 to practiseMerge sort: split, sort both halves, merge
, 1 to practiseWhy merge sort takes n log n steps
, 1 to practiseTry it: merge sort with a comparator
, 1 to practiseMerge sort is stable, if the merge takes left on ties
, 1 to practiseThe price is extra memory
Recap

Pick a pivot, split the rest around it
Partitioning: one scan, one wall
, 2 to practiseTrace a partition by hand
, 1 to practiseTry it: write partition
, 2 to practiseQuicksort: partition, then sort each side
, 1 to practiseTry it: sort in place
, 1 to practiseA bad pivot makes quicksort slow
A random pivot fixes the worst case
, 1 to practiseQuickselect finds the k-th smallest
Recap

, 1 to practiseTwo fingers on a list beat trying every pair
A pair with a given sum, in a sorted list
, 2 to practiseWhy moving one pointer never skips the answer
, 2 to practiseReversing in place: swap the ends, move inwards
, 1 to practiseA read pointer and a write pointer
, 1 to practiseMerging two sorted lists
A sliding window reuses the last sum
, 1 to practiseTry it: the best k days
, 1 to practiseA window that grows and shrinks
Recap

, 1 to practiseRemembering what you have seen saves looking again
Two-sum in one pass
, 1 to practiseTry it: two-sum
, 2 to practiseCounting how often each thing appears
, 1 to practiseTry it: the most borrowed book
, 1 to practiseSame letters, different order: anagrams
, 1 to practiseA set spots duplicates in one pass
, 1 to practiseGrouping: a map from a key to a list
, 1 to practiseCounting sort: sorting without comparing
Recap

A tree branches out from one root
, 1 to practiseDepth first: before, between or after the children
, 1 to practiseRecursion writes itself for trees
, 1 to practiseTry it: in-order, sorted for free
, 1 to practiseThe same walk with your own stack
, 1 to practiseLevel by level with a queue
, 1 to practiseTry it: one vector per level
, 1 to practiseHeight and path sums: answers built from the children
, 2 to practiseLowest common ancestor in a search tree
Recap

, 1 to practiseA graph is places and the links between them
, 1 to practiseBreadth-first search explores in rings
, 1 to practiseBFS in C++
, 1 to practiseDepth-first search follows one path to its end
, 1 to practiseA visited set stops you going round in circles
, 1 to practiseConnected components are the separate groups
, 1 to practiseA grid is a graph too
, 1 to practiseFinding a cycle in a directed graph
, 1 to practiseTopological sort puts tasks in a safe order
Recap

, 1 to practiseWhen roads have lengths, fewest steps is not enough
Dijkstra settles the nearest place first
, 1 to practiseA priority queue hands out the nearest place
, 1 to practiseDijkstra in C++
, 1 to practiseTry it: cheapest times from one place
, 1 to practiseRemember where each best time came from
, 1 to practiseNegative weights break Dijkstra
, 1 to practiseTry it: Bellman–Ford
, 2 to practiseA* aims at the goal
Recap

, 1 to practiseA greedy algorithm takes the best-looking step now
, 1 to practiseMaking change: biggest coin first
Greedy change fails for some coins
, 1 to practiseTry it: give change greedily
, 1 to practiseChoosing meetings: the earliest finish wins
, 1 to practiseWhy the earliest finish is always right
, 2 to practiseTry it: cancel as few meetings as possible
, 2 to practisePacking a bag: greedy by value per kilo
Recap

Some recursions solve the same problem many times
, 1 to practiseCount the calls to see the waste
, 1 to practiseMemoisation: remember every answer
, 1 to practiseBottom-up: fill a table from the smallest case
, 1 to practiseClimbing stairs: count the ways
, 2 to practiseCoin change: how many ways to pay?
, 1 to practiseCoin change: the fewest coins, for any coins
Getting the coins back, not just the count
, 1 to practiseTop-down or bottom-up
Recap

Some subproblems need two numbers
, 1 to practiseCounting paths through a grid
, 1 to practiseFilling the grid row by row
, 1 to practiseThe longest common subsequence
, 1 to practiseFrom exponential to a table
, 1 to practiseEdit distance: how far apart two words are
, 2 to practiseThe 0/1 knapsack: packing a bag
, 1 to practiseReading the answer back from the table
, 2 to practiseSaving memory with one row
Recap

Choose, explore, undo
, 1 to practiseSubsets: take it or leave it
, 1 to practiseChoosing k of n
, 1 to practisePermutations: every order
, 1 to practiseTry it: every arrangement of a word
, 2 to practiseChoices that add up to a target
, 1 to practisePruning: the N-queens puzzle
, 1 to practiseTry it: find a word in a letter grid
, 2 to practiseWhen to reach for backtracking
Recap

, 1 to practiseConnect every town with the least cable
Take the cheapest edge that does not make a loop
, 1 to practiseTrace it: a table of decisions
, 1 to practiseUnion-find answers “same group?” fast
, 1 to practiseKruskal in C++
, 1 to practiseTry it: the cost of a minimum spanning tree
Prim grows one tree outwards
, 1 to practiseTry it: Prim on a table of costs
, 1 to practiseWhat a spanning tree does and does not promise
Recap

, 1 to practiseA method beats a flash of insight
, 1 to practiseThe input size tells you how fast to be
, 1 to practiseFrom brute force to fast: the best run of days
, 1 to practiseClues that point to a technique
, 1 to practiseCheck the fast answer against the slow one
, 1 to practiseEdge cases are where solutions break
, 1 to practiseAmortised cost: expensive now and then, cheap on average
, 1 to practiseTry it: days until a warmer day
, 1 to practiseChoosing between correct solutions
Recap

, 2 to practiseHow this challenge works
, 2 to practiseName the technique
, 1 to practiseWrite it: count the islands
, 1 to practiseWrite it: the shortest word ladder
, 1 to practiseWrite it: merge overlapping bookings
, 1 to practiseWrite it: the longest rising run
, 1 to practiseWrite it: how many rooms are needed
, 2 to practiseWhich statements are true?
, 2 to practiseRead a recurrence: edit distance
Recap: the course in seven lines