Random questions Flashcards
Which of the following assertions are true about open address tables?
A. You cannot store more records than the total number of slots in the table.
B. There are no collisions.
C. We cannot delete elements in open address tables.
D. Families of hash functions must allow a full permutation of the index of the table.
A. You cannot store more records than the total number of slots in the table.
D. Families of hash functions must allow a full permutation of the index of the table.
Let n be the number of keys and m the number of slots in a hash tables where collisions are resolved by chaining. The load factor n/m is:
A. The average number of slots used to store the keys.
B. The maximal number of collisions.
C. The average length of a list.
C. The average length of a list.
**Chaining, average length of the linked list at each slot
Assuming we can compute the hash value of a key k in O(1) time, the search time in an hash table where collisions are resolved by chaining is:
A. Always executed in constant time O(1).
B. Determined by the load factor.
C. O(1) if and only if there are no collisions.
B. Determined by the load factor
*for C because a very small number of collision doesn’t mean we loose O(1) overall
What is the recursive equation giving the best case running time of the function heapify on a heap of size n (i.e. when n nodes are stored in the heap)?
A. T(n) = O(1)
B. T(n)=T(n/3)+O(1)
C. T(n) = T( 2*n/3 ) + O(1)
A. T(n) = O(1)
Best case, compare, no swap needed so no need to recurse down
The worst case running time of insertions in BST trees with n nodes is:
A. Ω(logn)
B. O(n)
C. Θ(logn)
D. Θ(n)
E. O(logn)
B. O(n)
Which assertion(s) are true?
A. AVL properties can be restored using rotations.
B. Rotations preserve BST properties.
C. Rotations preserve AVL tree properties.
D. In the worst case, a rotation has a O( log n ) running time.
A. AVL properties can be restored using rotations.
B. Rotations preserve BST properties.
*Rotations do not always preserve AVL tree properties
Let G be a directed graph. We explore G using the BFS algorithm. Which of the following assertions are true?
A. All vertices of G are visited even if G has disconnected components.
B. The source s can be any vertex of G.
C. All vertices at distance d from the source s are visited before vertices at distance d+1.
D. The best case running time of BFS is Ω(V+E).
B. The source s can be any vertex of G. → but will only visit reachable vertices from this node
C. All vertices at distance d from the source s are visited before vertices at distance d+1.
D. The best case running time of BFS is Ω(V+E).
*BFS visits only reachable vertices
Let G=(V,E) be a connected undirected weighted graph on which we run the Prim’s algorithm to compute a MST. How many iterations the main loop of the algorithm (i.e. while loop in the slides used in class) will do?
A. |V|^2
B. |E|
C. |V|-1
D. |E| + |V|
C. |V|-1
What is the best and worst case running time of Gale-Shapley’s algorithm?
Best case: Ω (n) → They each get their 1st choice accepted
Worst case: O (n^2) → each compagny proposes to each student exactly once if they keep rejecting and get their last choice (nxn)
Let G be a flow network, on which we ran the Ford-Fulkerson algorithm. At the end of its execution, which assertion are true?
A. There are no augmenting paths in the residual graph.
B. It exists at least one path from source s to the sink t in the residual graph.
C. The value of the flow is equal to the sum of the capacities of the outgoing edges from s.
D. The sum of the flow out of the source s is equal to the sum of the flow in the sink t.
A. There are no augmenting paths in the residual graph.
D. The sum of the flow out of the source s is equal to the sum of the flow in the sink t.
We consider a binary counter that does not limit the number of bits used to represent numbers (i.e. we can use as many bits as we need). We now consider a sequence of n operation INCREMENT. What is the amortized cost of INCREMENT?
O(1) for each increment operation
We introduce a new function MULTIPUSH(k) that pushes k object in a stack. We now consider sequences of PUSH, POP, MULTIPUSH and MULTIPOP operations. Here, k is a fixed value. What would be the amortized cost of MULTIPUSH(k) in the accounting method?
A. 2*k
B. 2
C. k
C. k
*Amortized cost = average cost/operation
Consider the set of all trees of height h that can be constructed by a sequence of “union-by- height” operations. How many such trees are there?
There are infinitely many of these trees, since there is no constraint given on the number of nodes and “union-by-height” trees (trees built by union-by-height operations) have no constraint on the number of children of any node.
In breadth first search, each vertex has a “visited” field which is set to true before the vertex is put in the queue. What happens if BFS instead sets the visited field to true when the vertex is removed from the queue? Does the algorithm still work? Does it run just as fast? What if we want to find the shortest path between every pair of vertices in the graph ?
The algorithm still works. However, multiple copies of the vertex can be put the queue. The maximum number of copies is the in-degree of the vertex. The size of the queue grows as O(|E| ) rather than O( |V| ).
- In this case, BFS would explore all possible paths (all edges), which is much slower (redundant work)
- Doesn’t find shortest paths anymore
Dijkstra’s algorithm assumes the edges have non-negative weights. (Where does this come up in the proof of correctness?) But suppose we have a graph with some negative weights, and let edge e be such that cost(e) is the smallest (most negative). Consider a new graph in which we add cost(e) to all the edge weights, thus making all weights in the new graph non- negative. Now the conditions hold for Dijkstra to find the shortest paths, so we could now run Dijkstra. Is this a valid way to solve for shortest paths in the case that some edges have negative weights? Justify your answer.
No. For any path in the original graph, the distance of that same path P in the new graph will be greater by cost (e) multiplied by the number of edges in the path P, since we incremented each edges cost by cost(e). But for two paths with a different number of edges, the totals for the extra costs that we have added will be different. So there is no reason why you should expect to get the same solutions in the two cases. [Note that by ?same solutions? here, I don?t just mean the same distances of the shortest paths; I mean the paths themselves!] For example, take the graph with three edges cost(u,v) = -2, cost(v,w) = 2, cost(u, w)=1. The shortest path to w is (u, v, w). But adding 2 to the cost of each edge and then running Dijkstra would give the shortest path as (u, w).
Consider an instance of the stable matching problem in which, for all α ∈ A, α’s first choice is β if and only if β’s first choice is α. In this case, there is only one stable matching. Why?
By definition, a matching is unstable if there exists an α ∈ A and a β ∈ B that prefer each other over their present partners. Take any matching for which some α ∈ A doesn’t get its first choice. Let the first choice of α be β. Then β is not getting its first choice either, since β’s first choice is α. But then this matching is not stable. Thus, for any stable matching, every α gets its first choice, and so every β (by the constraints given in this question) gets its first choice too.
Suppose the capacities in a network flow are not integers. How would this change the O( ) runtime of the Ford Fulkerson algorithm? Does the algorithm terminate?
The stated runtime of Ford-Fulkerson is O( C m ) as explained in the lecture, where C is an integer namely the sum of integer capacities of edges out of s. If the capac- ities are not integers, then this O( ) no longer makes sense because O( ) always assumes we are talking about integers i.e. number of operations. More concretely, if we applied the Ford-Fulkerson algorithm to a flow network having non-integer capacities, we would still find that the flow increases in every pass through the main loop. However, the amount by which the flow increases might be a very small number and this number might get smaller and smaller indefinitely. There is no reason why the while loop would ever termi- nate.
Given an unbalanced BST, give a LINEAR algorithm to rebalance it.
- Run in-order traversal → flatten the tree into an array O(n)
- Build the Balanced BST using the median and recursively doing the same on the left and right sub-trees → O(n)
Suppose we remove the red nodes from a RB tree as follows. Remove each red nodes and make its children, children of black parent. Ignore what happens to the keys. In this questio we are just interested in the structure of the tree. A) What are possible degrees of the black nodes after this process is complete? Explain.
Case 1: A black node had 2 red children
- Its grand children are attached to it, goes from degree 2 → 4
Case 2: A black node had 2 red children, but no grand-children → degree 0
Case 3: Had 1 single red child → has degree 3
What is the Best-case running time of an algorithm getting a sorted list (x1 - xn) and an unsorted list (y1 - yk) and sorting them together (min number of decisions).
- Sort unsorted list → O(k log k)
- Insert sorted k values into sorted n list → O(n+k)
So lower-bound is Big-Omega of (K log k), can’t really do better
What is the difference between a forward and a cross edge in DFS traversal?
In both cases, the node is black (visited, but not in the recursion stack)
Forward edge: d[u] < d[v]
Cross edge: d[u] > d[v]
True or False? A fixed-length encoding is always a prefix code.
True
- Fixed-length code = all symbols have the same number of bits
- Prefix code = No symbol’s code is a prefix of another symbol
Let G = (V, E) be a weighted graph and let M be a minimum spanning tree of G.
True or False: The path in M between any pair of vertices v1 and v2 must be a shortest path in G.
False
Consider the graph in which V = {a, b, c} and the edges are (a, b), (b, c), (c, a). The weight of the edges are 3,3 and 4 respectively. The MST is clearly (a, b), (b, c). However, the shortest path between a and c is of cost 4 not 6 as seen from the MST
To determine the direction of an edge between two vertices in V, you are only allowed to ask a query. A query consists of two specified vertices u and v and is answered with:
“from u to v “ if (u, v) is in A, or
“from v to u “ if (v, u) is in A.
Give matching upper and lower bounds (as functions of n ) for the number of queries required to and a topological sort of G.
This problem reduces to sorting.
Since the graph is complete, there exists an ordering between every pair of nodes, in other words, we have a total ordering on the graph.
A query establishes an ordering between two nodes, i.e. (u, v) ‘s existence can be interpreted as u > v
and (v, u) as v < u.
We can simply run a comparison-based sort to output a topological sort.
The “max” element will be a source node with out-going edges to all other nodes. Similarly, the “min” element will be a sink node. Since query is selectively a comparison operator, there is a tight Ω(n log n) lower bound on performing a topological sort in this model
