Final Exam

Question 1

running times of insertion sort

Answer 1

o Best case: O(n)
o Worst case: O(n^2)
o Average case: O(n^2)

Question 2

running times of bubble sort

Answer 2

o Best case: O(n)
o Worst case: O(n^2)
o Average case: O(n^2)

Question 3

running times of heap sort

Answer 3

o Best case: O(n log n)
o Worst case: O(n log n)
o Average case: O(n log n)

Question 4

running times of merge sort

Answer 4

o Best case: O(n log n)
o Worst case: O(n log n)
o Average case: O(n log n)

Question 5

recurrence relationship for merge sort

Answer 5

T(n) = 2T(n/2) + O(n) n > 1

O(1) n = 1

Question 6

running times for quick sort

Answer 6

o Best case: O(n log n)
o Worst case: O(n^2)
o Average case: O(n log n)

Question 7

running time and recurrence for quick sort with a 8 to 3 split

Answer 7

RT = O(n log n)

T(n) = T(8n/11) + T(3n/11) + O(n) n > 1
O(1) n = 1

Question 8

recurrence relationship for worst case of quick sort

Answer 8

T(n) = T(n-1) + O(n) n > 1

O(1) n = 1

Question 9

Djikstras priority queue implemented with array: running times for insert, decrease key, and delete min

Answer 9

insert: O(1)
decreasekey: O(1)
deletemin: O(n)

Question 10

Djikstras priority queue implemented with binary heap: running times for insert, decrease key, and delete min

Answer 10

insert: O(log n)
decreasekey: O(log n)
deletemin: O(log n)

Question 11

running times for search, insert, and delete on regular binary search tree with n nodes

Answer 11

O(h) where h is the height of the tree . . . or O(n)

Question 12

running times for search, insert, and delete in a red-black tree with n internal nodes

Answer 12

O(log n)

Question 13

running time for topological ordering (linearization) algorithm

Answer 13

O(|V| + |E|)

Question 14

running time for longest common string

Answer 14

O(n * 2^m)

Question 15

running time for edit distance

Answer 15

O(n * m)

Question 16

definition for Asymptotic / Big O Notation

Answer 16

f(n) = O(g(n)) if there exist positive constants c and n0 such at 0 <= f(n) <= c*g(n) for n >= n0

worst case / lower bound

Question 17

height of heap with n nodes

Answer 17

O(log n)

Question 18

height of red-black tree with n internal nodes

Answer 18

O(log n)

Question 19

definition of master theorem

Answer 19

T(n) = aT(n/b)+(n^d) for a > 0, b > 1, d >= 0
then,
O(n^d) if d > log_b a
T(n) = O(n^d * log n) if d = log_b a
O(n^log_b a) if d < log_b a

Question 20

definition of big omega notation

Answer 20

best case RT / lower bound

Question 21

definition of big theta notation

Answer 21

is both big O and big omega

Question 22

True or False: If f(n) = Θ(g(n)) and g(n) = Θ(h(n)), then h(n) = Θ(f(n)).

Answer 22

True

Question 23

True or False: If f(n) = O(g(n)) and g(n) = O(f(n)) then f(n) = g(n).

Answer 23

False

Question 24

True or False: 𝑛/100 = Ω(n).

Answer 24

True

Question 25

Properties of min heap

Answer 25

Complete tree where every parent must be of lower value than its children

Question 26

Properties of red-black tree

Answer 26

1. Every node is colored red or black.
2. The root is black.
3. Every “leaf” (the sentinel) is colored black.
4. Both children of a red node are black.
5. Every simple path from a child of node X to a leaf has the same number of black nodes.

Question 27

Under what condition will the Bellman-Ford algorithm not work?

Answer 27

When the graph contains a negative cycle

Question 28

what is black height for a RBT?

Answer 28

number of black nodes in a path (must be the same for all paths)

Question 29

running time of Kruskal’s

Answer 29

O( |E| * log|V|)

Question 30

running of time of Primm’s as binary heap, as array

Answer 30

binary heap: O(|E| + |V|) * log|V|),

array: O(|E|^2)
* same as running time of Djikstras

Question 31

running time of Djikstras: binary heap and array

Answer 31

binary heap: O(|E| + |V|) * log|V|),

array: O(|V|^2)

Question 32

running time of Bellman-Ford

Answer 32

O(|V| * |E|)

Question 33

running time of DFS

Answer 33

O(|V| + |E|)

Question 34

running time of BFS

Answer 34

O(|V| + |E|)