Algorithm concepts

Question 1

Uniform cost model

Answer 1

All machine operations have a constant cost, whatever the values

Question 2

Time complexity

Answer 2

T(N) = aN + b

Question 3

Asymptotic notation

Answer 3

aN + b = O(N) T(N) = O(N) highest order term determines the bound

Question 4

Definition “Big O” (Upper Bound)

Answer 4

A function f(N) has an asymptotic upper bound given by the function g(N), written f(N) = O(g(N)), if and only if there are positive real numbers c and n0 such that 0 ≤ f(N) ≤ c g(N) for all N ≥ n0

Question 5

Definition “Big Omega” (Lower Bound)

Answer 5

A function f(N) has an asymptotic lower bound given by the function g(N), written f(N) = Ω(g(N)), if and only if there are positive real numbers c and n0 such that 0 ≤ c g(N) ≤ f(N) for all N ≥ n0

Question 6

Definition “Big Theta” (Tight Bound)

Answer 6

A function f(N) has an asymptotic tight bound given by the function g(N), written f(N) = Θ(g(N)), if and only if there are positive real numbers c1, c2, and n0 such that 0 ≤ c1 g(N) ≤ f(N) ≤ c2 g(N) for all N ≥ n0

Question 7

Space complexity

Answer 7

The space complexity of an algorithm is the total amount of memory used, including that used by input parameters, as a function of the size of the input

Question 8

Auxiliary Space

Answer 8

The auxiliary space is the amount of extra memory required, not including input parameters, as a function of the size of the input.

Question 9

Polynomial

Answer 9

p(N) = a0 + a1N + a2N^2 + … + adN^d in which ad ≠ 0 asymptotically positive iff ad > 0

Question 10

Exponential

Answer 10

include a term of the form a^N

Question 11

Divide and Conquer

Answer 11

Question 12

Recursion Tree

Answer 12

Question 13

Master Method

Answer 13

Question 14

Master Method pt 2

Answer 14

Question 15

Master Method pt 3 (extra check)

Answer 15

Regularity condition

Question 16

Master method excluded cases

Answer 16

The master method does not apply to these recurrences

T(N) = NT(N/2) + N
T(N) = 0.5T(N/2) + 4N
T(N) = 4T(N/8) − N2

T (N ) = 2T (N /2) + N / log N

The (mostly straightfoward) reasons are

the number of subproblems in the first two

negative divide and combine time (third example)

negative value of k (fourth example)

Question 17

Heap

Answer 17

Question 18

Binary search tree add code

Answer 18

Question 19

Hash function

Answer 19

common to implement hash function in two steps

either stage can cause collisions

Question 20

Adjacency lists

Answer 20

Question 21

Code for Kruskal’s

Answer 21

Question 22

Prim’s code

Answer 22

Question 23

Bellman-Ford

Answer 23

Question 24

Relax

Answer 24

Question 25

Bellman-Ford to detect negative weight cycle

Answer 25

Question 26

Bellman-Ford

Answer 26

Question 27

Dijkstra

Answer 27

Question 28

Dijkstra’s correctness

Answer 28

Question 29

Dijkstra’s correctness pt 2

Answer 29