S18 Final Jeopardy
The version of the browser you are using is no longer supported. Please upgrade to a supported browser.Dismiss

ABCDEFGHIJKLMNOPQRSTUVWXYZ
1
2
TopicsRunning TimeDivide and Conquer/Greedy AlgorithmsBFS/DFSGraph AlgorithmsHashing, Tries, TreesFinal Jeopardy
3
100Q: Amortized Runtime for operations on a resizing deque

A: O(1)
Q: Name 2 divide and conquer algorithms you have learned:

A: Mergesort, Binary Search, Inversion Counting, Median Selection
Q: State the white path theorem

A: When doing DFS, u is a descendant of v iff there is a white path from v to u when you discover v
Q: A topological ordering is only possible with this type of graph

A: a DAG
Q: Explain the difference between expected and worst case running time

A: Expected amount of time a given call would take vs worst case amount of time a given call to the algo will take. Expected running time assumes a probability distribution over the inputs, whereas worst case does not.
1000 points!!! : Linear algorithm for whether a graph is almost strongly connected: can adding one edge make the entire graph an SCC? Answer: Create SCC graph using Kosaraju's and toposort it. Add an edge from the last SCC in the toposort to the first one and then run Kosaraju's again and check for a single SCC.
4
200Q: Name an algorithm with this recurrence relation (and give the solution to it): T(n) = T(n/2) + 1

A: Binary Search and Theta(log n)
Q: Name 2 algorithms that use heaps

A: Dijkstra, Prims, Heapsort, Huffman
Q: What types of edges can you find when doing DFS on an undirected graph

A: Tree and back edges
Q: What type of graph can you construct from the output of kosaraju's algorithm

A: SCC Kernel graph (which is a DAG)
Q: Describe the properties of an AVL tree

A: BST property and height balance: heights of children differ by at most 1, this gives it a height of logn
5
300Q: Name an algorithm with this recurrence relation and the solution: T(n) = 2T(n/2) + n

A: Mergesort and Theta(n log n)
Q: What is the worst case running time for deterministic quicksort? What is the expected running time for randomized Quicksort?

A: O(n^2) and O(nlogn) (note that if median-finding is used in deterministic quicksort, they can correctly give a worst case running time of O(nlogn)
Q: Name one problem you would use BFS to solve and one you'd use DFS to solve

A: BFS: bipartite graph, shortest path in unweighted graph, DFS: solving a maze, recursion on a graph, cycle detection
Q: What is a safe edge? How does each MST algorithm use that notion?

A: minimum edge crossing a cut (i.e. edge in the MST). MST algos just repeatedly add safe edges until an MST is formed
Q: What is a patricia trie and how does it improve the runtime/space usage of a normal trie?

A: Saves space by "compressing" nodes of a trie. It does not improve runtime.
6
400
Q: Explain the full running time of Kruskal's algorithm and its importance

A: O(mlgn) to sort the edges by edge weight + O(n) to makeSet() on each vertex + O(mlg*n) to find and union vertices per edge = O(mlgn) time. This means Kruskals runs faster than Prim's if edges are already sorted by edge weight.
Q: Give a high level argument for why huffman produces an optimal prefix free tree

A: Highest frequency nodes have shortest encoding. Prefix free encoding problem can be solved by a greedy algorithm (Huffman)
Daily double! Each team wagers points. Go up and write the pseudocode for DFSQ: Why doesn't Dijkstra work for negative edge weighted graphs?

A: Greedy choice assumes you've already found the shortest path at any given step
Q: Explain every way for dealing with collisions in hashing and the pros and cons of each

A: Chaining (use linked list for collisions) Pros: easy to implement, reason about Cons: chains can grow long if table size not managed, overhead from traversing linked lists
Open Addressing: various types, depends which types they talk about
7
500Q: What is the running time of this loop :
for (i = 1; i <= n; i = 2*i) do
for j = 1 to i do
print j

A: O(n) see lecture notes
Q: Name 2 greedy algorithms you have learned and explain the greedy choice for each

A: Huffman and heap or Dijkstra/Prim.
Q: During a DFS on a directed graph, for each edge (u,v), what can you determine about the type of edge if v is black? Grey? White?

A: Cross or forward, Back, Tree
Q: Will Dijkstra still work if you square the weights of all the edges?

A: no, a^2 + b^2 <> (a+b)^2
Q: With n balls in m bins what is the probability that no bucket has more than 1 ball?

A: Pr(no bucket has more than 1 ball) = m!/((m-n)!*m^n)
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100