
Algorithms and Data Structures
By downloading or studying this deck you agree to the deck directory terms, including the deck's licence.
Algorithms and data structures flashcards for a bachelor's course: analysis, data structures, sorting and searching, graph algorithms and design paradigms, in pseudocode with typeset maths, with 20 exam-style exercises.
What's inside
- Analysis of Algorithms — correctness and loop invariants, cost models, O, Ω and Θ, recurrences and the master theorem, amortised analysis.
- Data Structures — lists, stacks and queues, hash tables, binary search trees, AVL, red–black and B-trees, heaps, union–find, tries and skip lists.
- Sorting and Searching — searching, elementary sorts, merge sort, quicksort and heapsort, the lower bound, linear-time sorts and selection.
- Graph Algorithms — representations, BFS and DFS, topological sort and strong components, shortest paths, minimum spanning trees, flows and matching.
- Design Paradigms — exhaustive search and A*, divide and conquer, greedy algorithms, dynamic programming, string matching and a first look at P and NP.
- Practice — 20 exam-style exercises with traces, recurrences, proofs and design tasks.
Every card is written in our own words with our own examples, and every worked example, trace and model answer is checked by script. The Practice deck is an exam: it draws three exercises at random, and you grade your answers against each marking scheme. Scope and checks draw on two open textbooks: Jeff Erickson, Algorithms (CC BY 4.0), and Pat Morin, Open Data Structures (CC BY).
1,949 cards in total.
What's inside
- 1 Analysis of Algorithms 256 cards
- 2 Data Structures 449 cards
- 3 Sorting and Searching 248 cards
- 4 Graph Algorithms 469 cards
- 5 Design Paradigms 507 cards
- Practice Exam 20 cards
A few cards
1 Analysis of Algorithms
256 cards
Front
Algorithm: definition
Back
A precisely described procedure, made of steps simple enough for a machine to carry out without judgement, that turns every valid input of a problem into a matching output after finitely many of them.
core · An algorithm is the method, independent of any programming language; a program is one implementation of it.
Front
Computational problem and instance: the difference
Back
A problem states, for every allowed input, which outputs count as right, such as "given numbers, return them in non-decreasing order". An instance is one input, such as [7, 2, 5]. An algorithm solves the problem only if it is right on every instance.
core · Tip: tests check some instances; only a proof covers them all.
Front
Specification of an algorithm: what it states
Back
Which inputs are allowed, the precondition, and how the output must relate to the input, the postcondition, precisely enough that the algorithm can be used, and its correctness checked, without reading its steps.
core · Contracts in code: → Software engineering 2, Design principles: "Design by contract (Meyer): definition".
2 Data Structures
449 cards
Front
Abstract data type: definition
Back
A type described only by the values it can hold and the operations on them, with what each operation does, and nothing about how the values are stored. A stack, for instance, is fixed by Push, Pop, Top and IsEmpty and the rule that the newest item leaves first.
core · Liskov and Zilles 1974. Morin's Open Data Structures calls an ADT an interface.
Front
Abstract data type and data structure: the difference
Back
An abstract data type says which operations exist and what they do; a data structure is one concrete way to store the values and carry the operations out. The stack ADT can be built on an array with a top index or on a linked list that pushes at its head.
core · Arrays, lists, stacks and queues are linear structures; trees, which are hierarchical, and graphs are nonlinear.
Front
Stack ADT: the equations its operations satisfy
Back
For every stack S and value x: Top(Push(S, x)) = x, Pop(Push(S, x)) gives back S, IsEmpty(New()) is true and IsEmpty(Push(S, x)) is false. Any implementation that satisfies them all behaves as a stack.
depth · Specifying an ADT by such equations is an algebraic specification (Guttag 1977). Here Pop yields the shortened stack.
3 Sorting and Searching
248 cards
Front
Linear search: definition
Back
Comparing x with the items one after another, from the first, until one equals x or the items run out: comparisons in the worst case. It needs neither sorted data nor random access, so it works on any list, file or stream.
core · Also called sequential search. Its best, worst and average case: → Analysis of algorithms.
Front
Search for x among 1000 unsorted keys, read in any order the method likes: why an absent x costs every method 1000 reads
Back
A method that answered "absent" after skipping a key would be wrong whenever that key is x, so it must read all 1000. Linear search is therefore optimal on unsorted data; only structure built in advance, a sorted order or a hash table, lets a search skip keys.
core · The same argument as for the minimum: → Analysis of algorithms: "Largest of unsorted values: the running time of finding it".
Front
SentinelSearch(A[1..n + 1], x): how the sentinel saves a test
Back
x is copied into the spare cell , so the loop is sure to stop and no longer tests i ≤ n: each step makes one test instead of two. A single check after the loop tells a real match from the copy.
SentinelSearch(A[1..n + 1], x) // A[n + 1] is a spare cell
A[n + 1] ← x
i ← 1
while A[i] ≠ x do i ← i + 1
if i ≤ n then return i
return 0 // only the copy matched
core · Knuth's Algorithm Q (TAOCP vol. 3, §6.1). → Data structures: "Sentinel (linked list): definition".
4 Graph Algorithms
469 cards
Front
Simple undirected graph on 1000 vertices: the most edges it can have, and the fewest if it is connected
Back
499,500 and 999: each of the pairs can be joined once, and a connected graph needs at least edges, which a tree has exactly. So lies between 0 and , and .
core · A directed graph without self-loops has up to edges. Trees: → Discrete mathematics.
Front
Sparse and dense graphs: the difference
Back
A sparse graph has far fewer edges than the possible, typically or a little more; a dense graph has . The difference decides whether reading the graph costs or in practice.
core · The terms are informal: still counts as sparse.
Front
Road map of junctions with about three roads meeting at each: its number of edges against
Back
About edges, since each road has two ends and the degrees add up to , against : the graph is sparse. An algorithm in reads it in a few million steps, one in needs about .
core · is the handshake lemma: → Discrete mathematics.
5 Design Paradigms
507 cards
Front
Brute force (exhaustive search): definition
Back
Solving a problem by generating every candidate solution and testing each one, keeping one that passes or the best of them. It is correct whenever the candidates can be listed completely, and it costs the number of candidates times the cost of one test.
core · → Analysis of algorithms: "Trying every subset of items to find one with a given total: its running time".
Front
A search over choices of items examines subsets, a search over orders examines arrangements, and a search over choices of exactly items examines combinations.
Back
A search over choices of items examines subsets, a search over orders examines arrangements, and a search over choices of exactly items examines combinations.
core · For : about subsets, orders and 184,756 combinations of 10 items.
Front
A search over choices of items examines subsets, a search over orders examines arrangements, and a search over choices of exactly items examines combinations.
Back
A search over choices of items examines subsets, a search over orders examines arrangements, and a search over choices of exactly items examines combinations.
core · For : about subsets, orders and 184,756 combinations of 10 items.
Practice
20 cards
Front
Exercise 1: Loading a bike-share van
A bike-share operator rebalances its stations with a van that drives the same route every morning. At stop the crew picks up D[i] bikes if D[i] > 0 and drops off −D[i] bikes if D[i] < 0. The van must never be asked to drop off more bikes than it carries, so the depot loads some bikes before the van leaves, and StartLoad computes how many. Its postcondition: it returns the smallest with for every from 1 to , where is the partial sum after stop and .
StartLoad(D[1..n]) // D[i] > 0: bikes picked up at stop i; D[i] < 0: dropped off
load ← 0 // change in the van's load since the depot
need ← 0 // bikes the depot must load
for i ← 1 to n do
load ← load + D[i]
if load + need < 0 then need ← −load
return need
Today's route has nine stops: D[1..9] = [1, −3, −4, 1, −2, 6, 6, 4, 4].
1.1 Trace StartLoad on today's route: the values of load and need after each stop, and the result. (2 points)
1.2 State a loop invariant for the for loop that is strong enough to prove the postcondition. (2 points)
1.3 Prove the invariant's initialisation and maintenance, and the termination step that gives the postcondition. (3 points)
1.4 A colleague simplifies the test to if load < 0 then need ← −load. What does this version return for today's route, and which step of your proof breaks? (2 points)
Back
1.1 Trace StartLoad on today's route: the values of load and need after each stop, and the result. (2 points)
2 points: load after stops 1 to 9 is 1, −2, −6, −5, −7, −1, 5, 9, 13 (1) · need after stops 1 to 9 is 0, 2, 6, 6, 7, 7, 7, 7, 7, so the depot loads 7 bikes (1)
Model answer: load runs through the partial sums 1, −2, −6, −5, −7, −1, 5, 9, 13. need rises only when the load drops below every earlier low: to 2 at stop 2, to 6 at stop 3 and to 7 at stop 5, and it stays 7 from then on. The procedure returns 7: with 7 bikes the van is down to 0 after stop 5 and never below it.
1.2 State a loop invariant for the for loop that is strong enough to prove the postcondition. (2 points)
2 points: at the start of the iteration for i, load = D[1] + … + D[i − 1], the partial sum of the stops already passed (1) · and need is the smallest s ≥ 0 that keeps the van at 0 or above after each of the stops 1 to i − 1, that is the larger of 0 and minus the lowest of those partial sums; an equivalent form counts (1)
Model answer: At the start of the iteration for i:
load;needis the smallest with for every , which is , or equally with .
The first part alone says nothing about need, and "need " is true but too weak to give the postcondition.
1.3 Prove the invariant's initialisation and maintenance, and the termination step that gives the postcondition. (3 points)
3 points: initialisation: for i = 1 no stop has been passed, load = 0 is the empty sum and need = 0 is the smallest s ≥ 0 when there is nothing to cover (1) · maintenance: after load ← load + D[i], load is the partial sum up to stop i; if load + need < 0, stop i is lower than need can cover, and need ← −load is the smallest start that covers it and, being larger, the earlier stops too; otherwise need already covers stop i and stays the smallest (1) · termination: the for loop stops after i = n, so the invariant for i = n + 1 says that need is the smallest s ≥ 0 covering all stops 1 to n, the postcondition (1)
Model answer:
- Initialisation: before the iteration for
i = 1,load = 0, and with no stop to cover, 0 is the smallest . - Maintenance: let
needfor stops . The assignment makesload. If , any start that covers stop must be at least , and covers the earlier stops too, since it exceeds ; soneedis the new smallest start. If , then already covers stop , and nothing smaller covers the earlier stops, soneedstays right. - Termination: a
forloop over the stops always ends, and on exit the invariant holds for :needis the smallest with for , which is the postcondition.
1.4 A colleague simplifies the test to if load < 0 then need ← −load. What does this version return for today's route, and which step of your proof breaks? (2 points)
2 points: it returns 1 instead of 7: need runs 0, 2, 6, 5, 7, 1, 1, 1, 1, as the load of −5 at stop 4 lowers it from 6 to 5 and the load of −1 at stop 6 sets it to 1, and with 1 bike the van is already short at stop 2 (1) · maintenance breaks: when a later partial sum is negative but above the lowest one, need is overwritten by a smaller value, first at stop 4 (6 to 5) and again at stop 6 (7 to 1), and either stop shows it; initialisation still holds, and termination would follow if maintenance did (1)
Model answer: It returns 1. need runs through 0, 2, 6, 5, 7, 1, 1, 1, 1: at stop 4, load = −5 < 0 already lowers it from 6 to 5, stop 5 raises it to 7, and at stop 6 load = −1 sets it to 1; the later loads are positive. One bike isn't enough: after stop 2 the van would hold bikes. The broken step is maintenance: from need for stops 1 to 3, the iteration for stop 4 must keep the smallest start for stops 1 to 4, still 6, but it replaces it by 5. At stop 6 it breaks again, replacing 7 by 1. The original test load + need < 0 changes need only when the new stop needs more than the old value.
Front
Exercise 2: Compressing a game level map
A puzzle game stores each level as a square map M[1..s, 1..s] of tiles, each wall or open, with a power of 2. To save memory, the engine turns the map into a quadtree by calling Compress(M, 1, 1, s): a block that is all wall or all open becomes a leaf, and any other block is split into four quarters. Leaf and Node build a tree node in constant time. Let be the number of tiles.
Compress(M, r, c, s) // the s × s block of M whose top-left tile is (r, c)
walls ← 0
for i ← r to r + s − 1 do
for j ← c to c + s − 1 do
if M[i, j] = wall then walls ← walls + 1
if walls = 0 or walls = s · s then return Leaf(M[r, c])
h ← s/2
return Node(Compress(M, r, c, h), Compress(M, r, c + h, h),
Compress(M, r + h, c, h), Compress(M, r + h, c + h, h))
2.1 Write a recurrence for the worst-case running time of Compress on a block of tiles, and name a map that reaches the worst case. (2 points)
2.2 Solve the recurrence with the master theorem, and state the bound in terms of the side as well. (2 points)
2.3 For a checkerboard, how many calls does Compress(M, 1, 1, 64) make, and how many tiles do its loops read in all? (2 points)
2.4 Make Compress run in linear time in the worst case: what do you precompute or change, what is the new recurrence and its solution, and why can no method do better? (3 points)
Back
2.1 Write a recurrence for the worst-case running time of Compress on a block of tiles, and name a map that reaches the worst case. (2 points)
2 points: T(n) = 4T(n/4) + Θ(n) for n > 1, with T(1) = Θ(1): the loops read all n tiles of the block, then four calls get blocks of n/4 tiles (1) · worst case: no block larger than one tile is all wall or all open, for example a checkerboard of walls and open tiles; any such map counts (1)
Model answer: A call on tiles reads each of them once, , and then, if the block is mixed, makes four calls on blocks of tiles; building the node is . So
The four calls happen whenever a block is mixed, so the worst case is a map in which every block of two or more tiles side mixes walls and open tiles, such as a checkerboard. A uniform block stops the recursion early.
2.2 Solve the recurrence with the master theorem, and state the bound in terms of the side as well. (2 points)
2 points: a = 4 and b = 4, so n^(log₄ 4) = n, and f(n) = Θ(n) has the same order: case 2 gives T(n) = Θ(n log n) (1) · in the side: n = s², so Θ(s² log s), by substituting or from T(s) = 4T(s/2) + Θ(s²), also case 2; either way counts (1)
Model answer: With and the leaf exponent is , and , so case 2 applies: . Every level of the recursion reads all tiles, and there are levels. Since and , this is ; the recurrence in the side, , has and also falls under case 2.
2.3 For a checkerboard, how many calls does Compress(M, 1, 1, 64) make, and how many tiles do its loops read in all? (2 points)
2 points: 5461 calls: on level d = 0 to 6 there are 4^d calls on blocks of side 64/2^d, 1 + 4 + 16 + … + 4096 (1) · 28,672 tile reads: each of the 7 levels reads all 4096 tiles once, 7 · 4096 (1)
Model answer: Every block of side 2 or more is mixed, so the recursion runs down to single tiles: level has calls on blocks of side , for . That gives calls. On each level the blocks cover the map once, so each level reads 4096 tiles, and the 7 levels read , which is . A map that is all open costs one call and 4096 reads.
2.4 Make Compress run in linear time in the worst case: what do you precompute or change, what is the new recurrence and its solution, and why can no method do better? (3 points)
3 points: a way to know each block's walls in O(1): a table W[i, j] of the walls in M[1..i, 1..j], with row and column 0 set to 0, built in Θ(n) by W[i, j] = W[i − 1, j] + W[i, j − 1] − W[i − 1, j − 1] + 1 for a wall tile or + 0 for an open one, so that a block's walls are W[r + s − 1, c + s − 1] − W[r − 1, c + s − 1] − W[r + s − 1, c − 1] + W[r − 1, c − 1], four look-ups; a table of the walls of every aligned block, each the sum of its four quarters, or a Compress that recurses first and turns four leaves of one kind into a leaf, counts too (1) · the recurrence becomes T(n) = 4T(n/4) + Θ(1), case 1 since 1 = O(n^(1 − ε)), so T(n) = Θ(n), and Θ(n) together with the table (1) · no method does better in the worst case: every tile must be read once, and a checkerboard's tree has (4n − 1)/3 nodes, 5461 for 64 × 64, all of which must be built (1)
Model answer: Precompute a summed table: W[i, j], the number of walls in M[1..i, 1..j], with W[0, ·] = W[·, 0] = 0 and
if M[i, j] = wall then w ← 1 else w ← 0
W[i, j] ← W[i − 1, j] + W[i, j − 1] − W[i − 1, j − 1] + w
in one pass, . The walls of the block at (r, c) with side s are then W[r + s − 1, c + s − 1] − W[r − 1, c + s − 1] − W[r + s − 1, c − 1] + W[r − 1, c − 1], and the double loop goes. A call now costs besides its four calls: , case 1 of the master theorem, since for , so , also with the table's . That is optimal: any method must look at every tile, and for the checkerboard it must build nodes, exactly the 5461 calls of 2.3. Two other ways work as well: a table with the walls of every aligned block, each the sum of its four quarters, built level by level in ; or a Compress that recurses first and turns a node whose four children are leaves of one kind into a leaf, which needs no table. Both give the same recurrence.
Front
Exercise 3: Waiting for the river to rise
A water authority records the level of a river gauge once an hour, L[1..n] in centimetres. For its flood report it wants, for each hour , W[i]: the number of hours until the level is next strictly higher than L[i], or 0 if it never is. Count the cost of a run as the number of Push and Pop calls.
WaitHigher(L[1..n])
S ← empty stack // hours still waiting for a higher level
for i ← 1 to n do
while S is not empty and L[Top(S)] < L[i] do
j ← Pop(S)
W[j] ← i − j
Push(S, i)
while S is not empty do
W[Pop(S)] ← 0
return W[1..n]
Today's readings: L[1..9] = [173, 164, 164, 146, 149, 153, 162, 147, 172].
3.1 Trace WaitHigher on today's readings: the stack after each hour, bottom first, and the array W. (2 points)
3.2 State the invariant of the for loop, and use it to show that every hour gets the right W. (2 points)
3.3 How much can a single iteration of the for loop cost, and why does a whole run still cost ? Use the aggregate method. (2 points)
3.4 Give a potential function that shows the amortised cost of each iteration is constant, and compute that cost. (2 points)
Back
3.1 Trace WaitHigher on today's readings: the stack after each hour, bottom first, and the array W. (2 points)
2 points: stacks [1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [1, 2, 3, 5], [1, 2, 3, 6], [1, 2, 3, 7], [1, 2, 3, 7, 8], [1, 9]; hour 3 doesn't pop hour 2, as 164 is not strictly higher (1) · W = 0, 7, 6, 1, 1, 1, 2, 1, 0 (1)
Model answer:
- Hours 1 to 4 fall or stay level, so each is pushed:
[1, 2, 3, 4]. Hour 3's 164 equals hour 2's and doesn't pop it. - Hours 5, 6 and 7 each pop the hour below them:
W[4] = 1,W[5] = 1,W[6] = 1, leaving[1, 2, 3, 7]; hour 8, at 147, is pushed on top. - Hour 9, at 172, pops 8, 7, 3 and 2:
W[8] = 1,W[7] = 2,W[3] = 6,W[2] = 7. It stops at hour 1, whose 173 is higher, and leaves[1, 9]. - The final loop sets
W[9] = 0andW[1] = 0.
So W = [0, 7, 6, 1, 1, 1, 2, 1, 0].
3.2 State the invariant of the for loop, and use it to show that every hour gets the right W. (2 points)
2 points: before the iteration for i, the stack holds, bottom to top in increasing order, exactly the hours j < i with no level above L[j] among the hours j + 1 to i − 1, so their levels never rise from bottom to top, and every hour below i that is off the stack has its correct W; an equivalent statement counts (1) · so a pop at hour i is right: L[i] > L[j] and no hour between them was higher, so i is the first higher hour and W[j] = i − j; the hours left at the end never meet a higher level, so 0 is right for them (1)
Model answer: Invariant: before the iteration for i, S holds exactly the hours such that no hour from to is higher than L[j], in increasing order from the bottom; hence their levels don't rise from bottom to top. Every hour not on the stack has its final W[j].
The while loop pops hours from the top while they are lower than L[i]. A popped has L[i] > L[j], and by the invariant no hour in between was higher, so is the first higher hour and W[j] = i − j is right. The loop stops at an hour at least as high as L[i], and since the levels below it are no lower, the hours left are exactly those that L[i] does not exceed; then i itself is pushed, so the invariant holds for i + 1. At the end, the hours still on the stack have no higher hour after them, and 0 is right.
3.3 How much can a single iteration of the for loop cost, and why does a whole run still cost ? Use the aggregate method. (2 points)
2 points: one iteration can pop every hour before it, for example when the level falls for n − 1 hours and then rises above them all, Θ(n) for that hour (1) · aggregate: every hour is pushed once and popped at most once, so a run makes at most 2n calls, Θ(n) in all; today's 18 calls needn't be given (1)
Model answer: The while loop of hour may pop all earlier hours: with levels falling for hours and a last hour higher than all of them, hour makes pops, . Counted over the run, though, every hour enters the stack once and leaves it at most once, in the for loop or in the final loop. So a run makes exactly pushes and at most pops, in all. Today: 9 pushes, 7 pops in the for loop (four of them at hour 9) and 2 in the final loop, 18 calls.
3.4 Give a potential function that shows the amortised cost of each iteration is constant, and compute that cost. (2 points)
2 points: Φ = the number of hours on the stack, or c times it for a constant c ≥ 1: 0 at the start and never negative (1) · an iteration with p pops costs p + 1 and changes Φ by 1 − p, so it costs 2 amortised; a pop in the final loop costs 1 and lowers Φ by 1, 0 amortised; so a run costs at most 2n; with c times the stack size an iteration costs at most c + 1 (1)
Model answer: Take , the stack's size. It starts at 0 and can't go below 0, so the amortised costs bound the actual total. An iteration of the for loop that pops hours has actual cost and changes by , so its amortised cost is , however large is. Each pop of the final loop costs 1 and lowers by 1: amortised 0. A run therefore costs at most . Today hour 9 costs 5 calls, but falls from 5 to 2, so it is charged like every other hour.
Licence: Personal use Report this deck
New Computer science decks by email
Hear when they arrive, or tell us which deck you need.
Comments
Loading comments…