1. _F_ The reverse postorder of a digraph’s reverse is the same as the postorder
ID: 3818849 • Letter: 1
Question
1. _F_ The reverse postorder of a digraph’s reverse is the same as the postorder of the digraph.
2. _F_ Adding a constant to every edge weight does not change the solution to the single-source shortest-paths problem.
3. ___ An optimization problem is a good candidate for dynamic programming if the best overall solution can be defined in terms of optimal solutions to subproblems, which are not independent.
4. ___ If we modify the Kosaraju algorithm to run first depth-first search in the digraph G (instead of the reverse digraph GR) and the second depth-first search in GR (instead of G), the algorithm will find the strong components.
5. ___ If you insert keys in increasing order into a red-black BST, the tree height is monotonically increasing.
6. ___ A good hash function should be deterministic, i.e., equal keys produce the same hash value.
7. ___ In the situation where all keys hash to the same index, using hashing with linear probing will result in O(n) search time for a random key.
8. ___ Hashing is preferable to BSTs if you need support for ordered symbol table operations.
9. ___ In an adjacency list representation of an undirected graph, v is in w’s list if and only if w is in v’s list.
10. ___ Every directed, acyclic graph has a unique topological ordering.
11. ___ Preorder traversal is used to topologically sort a directed acyclic graph.
12. ___ MSD string sort is a good choice of sorting algorithm for random strings, since it examines N logR N characters on average (where R is the size of the alphabet).
13. ___ The shape of a TST is independent of the order of key insertion and deletion, thus there is a unique TST for any given set of keys.
14. ___ In a priority queue implemented with heaps, N insertions and N removeMin operations take O(N log N).
15. ___ An array sorted in decreasing order is a max-oriented heap.
16. ___ If a symbol table will not have many insert operations, an ordered array implementation is sufficient.
17. ___ The floor operation returns the smallest key in a symbol table that is greater than or equal to a given key.
18. ___ The root node in a tree is always an internal node.
is this true or false? Could you explain?
Explanation / Answer
[1] FALSE No , Reverse Order is Not same.
[2] FALSE It, Will increase , Example : consider the graph where there are two paths from A to B, one traversing a single edge of length 2, and one traversing edges of length 1, 1, and -2. The second path is shorter, but if you increase all edge weights by 2,the first path now has length 4, and the second path has length 6, reversing the shortest paths.
[3] TRUE
[4] The Kosaraju-Sharir algorithm uses preprocessing time and space proportional to V + E to support constant-time strong connectivity queries in a digraph.
True, the strong components of a digraph are the same as the strong components of its reverse
[5] TRUE it will increase in monotonically .
[6] TRUE
We have three primary requirements in implementing a good hash function for a given data type:
It should be deterministic—equal keys must produce the same hash value.
It should be efficient to compute.
It should uniformly distribute the keys.
[7] TRUE for a random key.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.