Algorithm concepts v2

Question 1

Recurrence

Answer 1

aT(N/b) + D(N) + C(N) , N ≥ c

T(N/b) is the total time to solve a subproblem

Question 2

Lomuto partitioning

Answer 2

compare all elements to last element in array

Question 3

Hoare partitioning

Answer 3

partition grows inward from the end

handles duplicates better

Question 4

Three-way partitioning

Answer 4

includes a region for values equal to pivot

handles duplicates better

Question 5

Median of 3 partition

Answer 5

choose pivot as median of three random elements

better balance between subproblems

Question 6

Amortisation

Answer 6

amortized analysis considers a sequence of operations
cost of expensive operations is ‘amortized’ across the sequence…
can never “be in debt”

pick a value to ‘pay’ per operation - show that this value covers all costs (never in debt)

Question 7

Amortized time

Answer 7

average time taken per operation to do many operations

worst-case run time per operation rather than per algorithm can be too pessimistic

Question 8

Amortized analysis

Answer 8

considers both the costly and less costly operations together over the whole series of operations of the algorithm

Question 9

Amortized analysis: aggregate analysis

Answer 9

determine the upper bound T(n) on the total cost of a sequence of n operations, then calculates amortized cost to be T(n) / n

Question 10

Amortized analysis: accounting method

Answer 10

a form of aggregate analysis that assigns to each operation an amortized cost, which may differ from actual cost

early operations have an amortized cost higher than their actual cost, which accumulates a saved “credit” that pays for later operations having an amortized cost lower than their actual cost

because the credit begins at 0, the actual cost of a sequence of operations equals the amortized cost minus the accumulated credit… the amortized cost is an upper bound on the actual cost

usually many short-running operations accumulate such a credit in small increments, while rare long-running operations decrease it drastically

Question 11

Arithmetic series

Answer 11

1 + 2 + … + (N - 1) + N

create a second series that is a reverse of the first and add together term by term

   1  +    2     + ... + (N - 1) + N
\+ N + (N - 1) + ... +     2    +  1
----------------------------------------
=(N + 1) + (N + 1) + ... + (N + 1) + (N + 1)
= N(N+1)
= 2s

2s = N(N +1)
s = N(N + 1)/2

a + (a + d) + (a + 2d) + … + (a + (k - 1)d)

Sk = a1 + ... + ak
Sk = k(a1 + ak)/2

Question 12

Geometric series

Answer 12

𝑁𝑐+(𝑁/2)𝑐+(𝑁/4)𝑐+⋯+2𝑐+𝑐

create second series by multiplying by r (common ratio)
r = 1/2

Nc + (N/2)c + … + 2c + c
(N/2)c + … + 2c + c + c/2

Nc + (N/2)c + … + 2c + c
(N/2)c + … + 2c + c + c/2

all but two of the terms are identical
take the difference

Nc + (N/2)c + … + 2c + c
- (N/2)c + … + 2c + c + c/2
———————————————-
Nc - c/2

Nc - c/2 = s - s/2
Nc - c/2 = s/2
2Nc - c = s

𝑆𝑘 =𝑎+𝑎𝑟+𝑎𝑟^2 +⋯+𝑎𝑟^(𝑘−1)
𝑆𝑘 − 𝑟𝑆𝑘 = 𝑎 − 𝑎𝑟^𝑘
𝑆𝑘=𝑎(1−𝑟^𝑘) / (1−𝑟)

final form
𝑆𝑘=𝑎(𝑟𝑘−1) / (𝑟−1)
𝑆𝑘 = 𝑟𝑎𝑘 − 𝑎1 / (𝑟−1)

Question 13

Arithmetic Series general form

Answer 13

Sk = a + (a + d) + (a + 2d) + … + (a + (k - 1)d)
so
Sk = a1 + … + ak
Sk = k(a1 + ak)/2

Question 14

Geometric series general form

Answer 14

𝑆𝑘 =𝑎+𝑎𝑟+𝑎𝑟^2 +⋯+𝑎𝑟^(𝑘−1)
so
𝑆𝑘=𝑎(𝑟𝑘−1) / (𝑟−1)
𝑆𝑘 = 𝑟𝑎𝑘 − 𝑎1 / (𝑟−1)

Question 15

RBT 5 properties

Answer 15

1. all nodes (including nil) are either red or black
2. the root node is black
3. every leaf (all nil) is black
4. both children of a red node are black
5. all paths from a node to a descendant leaf contain the same number of black nodes

Question 16

Simple Uniform Hashing Assumption

Answer 16

with reference to chaining

Given a hash table T with m buckets, using hash function h, the simple uniform hashing assumption (SUHA) states that each different key k is equally likely to hash into any of the buckets. So the probability that h(k) = I, for all 1 ≤ I ≤ m, is 1/m

most probable / expected outcome: same number in each bucket

Question 17

Memoisation

Answer 17

making a note for later

for dynamic programming

Question 18

Dynamic programming

Answer 18

makes a space-time tradeoff

conditions to apply it:

• optimal substructure
• overlapping subproblems

optimal substructure:
problem can be decomposed into subproblems
an optimal solution uses optimal solutions to the subproblems

overlapping subproblems
same problems are generated over and over
subproblems must still be independent
set of all subproblems is the subproblem space
subproblem space determines time complexity

Question 19

Top Down

Answer 19

set out to solve the biggest problem

Question 20

Bottom Up

Answer 20

complete the table in order

Question 21

Optimal substructure

Answer 21

problem can be decomposed into subproblems

an optimal solution uses optimal solutions to the subproblems

Question 22

Overlapping subproblems

Answer 22

same problems are generated over and over
subproblems must still be independent
set of all subproblems is the subproblem space
subproblem space determines time complexity

Question 23

Graph

Answer 23

A graph G is a pair (V, E) where V is a finite set (of objects) and E is a binary relation on V. Elements of V are called vertices and elements of E are called edges

Question 24

Breadth-first Search

Answer 24

search proceeds gradually down multiple paths at once
all vertices at depth I visited before any at depth I + 1
BFS maintains a set of vertices being searched

search from given s

use of FIFO queue characteristic of BFS
best-first search would use priority queue

Question 25

BFS shortest paths

Answer 25

shortest path to all vertices
record extra info during search when a vertex is visited
unreachable vertices have diet[v] = - 1

Question 26

Depth-first search

Answer 26

when vertex is visited, immediately use it to look for more vertices. only visit others found with v when this search is over

can use call stack instead of explicit queue
restart until whole graph searched

Question 27

Kruskal’s algorithm

Answer 27

set of edges is iterated over in weight order

if the next edge connects two distinct components, it is added