Computing EN Exam

Algorithms and Data Structures

1,949 cards 0 Version 1, updated November 19, 2026

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: Θ(n)\Theta(n) 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 nn 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 n+1n + 1, 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 1000⋅999/21000 \cdot 999/2 pairs can be joined once, and a connected graph needs at least n−1n - 1 edges, which a tree has exactly. So mm lies between 0 and n(n−1)/2n(n - 1)/2, and m=O(n2)m = O(n^2).

core · A directed graph without self-loops has up to n(n−1)n(n - 1) edges. Trees: → Discrete mathematics.

Front

Sparse and dense graphs: the difference

Back

A sparse graph has far fewer edges than the n(n−1)/2n(n - 1)/2 possible, typically m=O(n)m = O(n) or a little more; a dense graph has m=Θ(n2)m = \Theta(n^2). The difference decides whether reading the graph costs Θ(n+m)\Theta(n + m) or Θ(n2)\Theta(n^2) in practice.

core · The terms are informal: m=nlog⁡nm = n \log n still counts as sparse.

Front

Road map of 10610^6 junctions with about three roads meeting at each: its number of edges against n2n^2

Back

About 1.5⋅1061.5 \cdot 10^6 edges, since each road has two ends and the degrees add up to 2m2m, against n2=1012n^2 = 10^{12}: the graph is sparse. An algorithm in Θ(n+m)\Theta(n + m) reads it in a few million steps, one in Θ(n2)\Theta(n^2) needs about 101210^{12}.

core · ∑deg⁡(v)=2m\sum \deg(v) = 2m 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 nn 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 n!n! arrangements, and a search over choices of exactly kk items examines (nk)\binom{n}{k} combinations.

Back

A search over choices of items examines 2n2^n subsets, a search over orders examines n!n! arrangements, and a search over choices of exactly kk items examines (nk)\binom{n}{k} combinations.

core · For n=20n = 20: about 10610^6 subsets, 2.4⋅10182.4 \cdot 10^{18} orders and 184,756 combinations of 10 items.

Front

A search over choices of items examines 2n2^n subsets, a search over orders examines   arrangements, and a search over choices of exactly kk items examines (nk)\binom{n}{k} combinations.

Back

A search over choices of items examines 2n2^n subsets, a search over orders examines n!n! arrangements, and a search over choices of exactly kk items examines (nk)\binom{n}{k} combinations.

core · For n=20n = 20: about 10610^6 subsets, 2.4⋅10182.4 \cdot 10^{18} 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 ii 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 s≥0s \ge 0 with s+Pi≥0s + P_i \ge 0 for every ii from 1 to nn, where Pi=D[1]+⋯+D[i]P_i = D[1] + \cdots + D[i] is the partial sum after stop ii and P0=0P_0 = 0.

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.1 Trace StartLoad on today's route: the values of load and need after each stop, and the result. (2 points)

2.

1.2 State a loop invariant for the for loop that is strong enough to prove the postcondition. (2 points)

3.

1.3 Prove the invariant's initialisation and maintenance, and the termination step that gives the postcondition. (3 points)

4.

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.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.

2.

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 =Pi−1=D[1]+⋯+D[i−1]= P_{i-1} = D[1] + \cdots + D[i-1];
  • need is the smallest s≥0s \ge 0 with s+Pj≥0s + P_j \ge 0 for every j<ij < i, which is max⁡(0,−min⁡(P1,…,Pi−1))\max(0, -\min(P_1, \ldots, P_{i-1})), or equally −min⁡(P0,…,Pi−1)-\min(P_0, \ldots, P_{i-1}) with P0=0P_0 = 0.

The first part alone says nothing about need, and "need ≥0\ge 0" is true but too weak to give the postcondition.

3.

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 =P0= P_0, and with no stop to cover, 0 is the smallest s≥0s \ge 0.
  • Maintenance: let need =s∗= s^* for stops 1..i−11..i-1. The assignment makes load =Pi= P_i. If Pi+s∗<0P_i + s^* < 0, any start that covers stop ii must be at least −Pi>s∗-P_i > s^*, and −Pi-P_i covers the earlier stops too, since it exceeds s∗s^*; so need ←−Pi\gets -P_i is the new smallest start. If Pi+s∗≥0P_i + s^* \ge 0, then s∗s^* already covers stop ii, and nothing smaller covers the earlier stops, so need stays right.
  • Termination: a for loop over the nn stops always ends, and on exit the invariant holds for i=n+1i = n + 1: need is the smallest s≥0s \ge 0 with s+Pj≥0s + P_j \ge 0 for j=1..nj = 1..n, which is the postcondition.
4.

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 1−2=−11 - 2 = -1 bikes. The broken step is maintenance: from need =6= 6 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 ss 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 n=s2n = s^2 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))
1.

2.1 Write a recurrence for the worst-case running time T(n)T(n) of Compress on a block of nn tiles, and name a map that reaches the worst case. (2 points)

2.

2.2 Solve the recurrence with the master theorem, and state the bound in terms of the side ss as well. (2 points)

3.

2.3 For a 64×6464 \times 64 checkerboard, how many calls does Compress(M, 1, 1, 64) make, and how many tiles do its loops read in all? (2 points)

4.

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

1.

2.1 Write a recurrence for the worst-case running time T(n)T(n) of Compress on a block of nn 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 nn tiles reads each of them once, Θ(n)\Theta(n), and then, if the block is mixed, makes four calls on blocks of n/4n/4 tiles; building the node is O(1)O(1). So
T(n)=4T(n/4)+Θ(n),T(1)=Θ(1).T(n) = 4T(n/4) + \Theta(n), \qquad T(1) = \Theta(1).
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.2 Solve the recurrence with the master theorem, and state the bound in terms of the side ss 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 a=4a = 4 and b=4b = 4 the leaf exponent is log⁡44=1\log_4 4 = 1, and f(n)=Θ(n)=Θ(nlog⁡ba)f(n) = \Theta(n) = \Theta(n^{\log_b a}), so case 2 applies: T(n)=Θ(nlog⁡n)T(n) = \Theta(n \log n). Every level of the recursion reads all nn tiles, and there are log⁡4n+1\log_4 n + 1 levels. Since n=s2n = s^2 and log⁡n=2log⁡s\log n = 2 \log s, this is Θ(s2log⁡s)\Theta(s^2 \log s); the recurrence in the side, T(s)=4T(s/2)+Θ(s2)T(s) = 4T(s/2) + \Theta(s^2), has slog⁡24=s2s^{\log_2 4} = s^2 and also falls under case 2.

3.

2.3 For a 64×6464 \times 64 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 dd has 4d4^d calls on blocks of side 64/2d64/2^d, for d=0..6d = 0..6. That gives 1+4+16+64+256+1024+4096=(47−1)/3=54611 + 4 + 16 + 64 + 256 + 1024 + 4096 = (4^7 - 1)/3 = 5461 calls. On each level the blocks cover the map once, so each level reads 4096 tiles, and the 7 levels read 7⋅4096=28,6727 \cdot 4096 = 28{,}672, which is n(log⁡4n+1)n(\log_4 n + 1). A map that is all open costs one call and 4096 reads.

4.

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, Θ(n)\Theta(n). 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 O(1)O(1) besides its four calls: T(n)=4T(n/4)+Θ(1)T(n) = 4T(n/4) + \Theta(1), case 1 of the master theorem, since 1=O(n1−ε)1 = O(n^{1 - \varepsilon}) for ε=1/2\varepsilon = 1/2, so T(n)=Θ(n)T(n) = \Theta(n), also with the table's Θ(n)\Theta(n). That is optimal: any method must look at every tile, and for the checkerboard it must build (4n−1)/3(4n - 1)/3 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 Θ(n)\Theta(n); 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 ii, 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].

1.

3.1 Trace WaitHigher on today's readings: the stack after each hour, bottom first, and the array W. (2 points)

2.

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.3 How much can a single iteration of the for loop cost, and why does a whole run still cost Θ(n)\Theta(n)? Use the aggregate method. (2 points)

4.

3.4 Give a potential function that shows the amortised cost of each iteration is constant, and compute that cost. (2 points)

Back

1.

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] = 0 and W[1] = 0.

So W = [0, 7, 6, 1, 1, 1, 2, 1, 0].

2.

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 j<ij < i such that no hour from j+1j + 1 to i−1i - 1 is higher than L[j], in increasing order from the bottom; hence their levels don't rise from bottom to top. Every hour j<ij < i 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 jj has L[i] > L[j], and by the invariant no hour in between was higher, so ii 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.3 How much can a single iteration of the for loop cost, and why does a whole run still cost Θ(n)\Theta(n)? 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 ii may pop all i−1i - 1 earlier hours: with levels falling for n−1n - 1 hours and a last hour higher than all of them, hour nn makes n−1n - 1 pops, Θ(n)\Theta(n). 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 nn pushes and at most nn pops, Θ(n)\Theta(n) 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.

4.

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 Φ=∣S∣\Phi = |S|, 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 pp hours has actual cost p+1p + 1 and changes Φ\Phi by 1−p1 - p, so its amortised cost is (p+1)+(1−p)=2(p + 1) + (1 - p) = 2, however large pp is. Each pop of the final loop costs 1 and lowers Φ\Phi by 1: amortised 0. A run therefore costs at most 2n2n. Today hour 9 costs 5 calls, but Φ\Phi falls from 5 to 2, so it is charged 5−3=25 - 3 = 2 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…