A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

1 | ||||||||||||||||||||||||||

2 | Topics | Running Time | Divide and Conquer/Greedy Algorithms | BFS/DFS | Graph Algorithms | Hashing, Tries, Trees | Final Jeopardy | |||||||||||||||||||

3 | 100 | Q: 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 | 200 | Q: 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 | 300 | Q: 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 DFS | Q: 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 | 500 | Q: 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 |

Loading...

Main menu