Task:
This homework is about balanced binary trees, Huffman’s algorithm, and graph traversals. You may write explanations in English, mathematics, or some mixture of the two. You may write procedures in Cormen’s pseudocode, or in any commonly used programming language. Page numbers refer to the usual Cormen text.
1. Suppose there is an algorithm that turns an unbalanced BST into a balanced BST. It is not the AVL algorithm discussed in the lectures. It is not the Red-Black algorithm discussed in Cormen. The algorithm uses these two rotations, called R1 and R2.
In R1 and R2, x and y are nodes; α, β, and γ are subtrees. Any or all of the subtrees may be empty. Now suppose that the algorithm is given the following degenerate BST. The numbers in the nodes are the BST’s keys. Its values are not shown. The BST’s root has key 1.
Show one way that the algorithm might use R1 and R2 to turn this BST into one with the same keys, but having the minimum possible height. Do not write code or pseudocode.
2. Huffman’s Algorithm is given a set of characters and their frequencies. It constructs a Huffman tree that assigns binary codes to those characters. Suppose that Huffman’s algorithm is given three or more characters. Will it ever assign the binary code 0, or the binary code 1, to a character? (In other words, will any character have a single-bit code?) If your answer is yes, then briefly explain one way that it could happen. If your answer is no, then briefly explain why it cannot happen.
3. In the lectures, the procedure GRAPH-BREADTH-FIRST takes a graph G and a source vertex s as its parameters. Starting from s, it visits G’s vertexes in breadth-first order. (The misnamed procedure BFS on page 595 is very similar.)
Write a new version of this procedure, called MARKY-GRAPH-BREADTH-FIRST, that does the same thing, but is different in two ways.
1. MARKY-GRAPH-BREADTH-FIRST must not use color attributes in any way. Instead, each vertex v must have an attribute v.mark, whose value is either TRUE or FALSE. If v.mark is FALSE, then v has never been visited. If v.mark is TRUE, then v has been visited, and will never be visited again. MARKY-GRAPH-BREADTH-FIRST must use v.mark
instead of v.color to prevent being trapped in cycles.
2. MARKY-GRAPH-BREADTH-FIRST must not use other vertex attributes in any way. In particular, it must not use Cormen’s v.d or v.π in any way.
MARKY-GRAPH-BREADTH-FIRST must call a procedure VISIT exactly once on each vertex it visits. However, do not write a definition for VISIT! We don’t know what it does—it shows only when a vertex is visited. If you think you must write VISIT, then you do not understand this question, and you should ask for help.
4. Let G be a directed graph. It has a set of edges G.E, a set of vertexes G.V, and an adjacency structure G.Adj. It also has a vertex r ∊ G.V. We say that G is rooted at r if, for each vertex v ∊ G.V, there is exactly one path from r to v.
4a. Write a procedure IS-ROOTED that takes G and r as its parameters. It must return TRUE if G is rooted at r. It must return FALSE otherwise. Hint: It may be helpful to assume that there is always a path from r to itself, even if (r, r) ∉ G.E.
4b. When does the best case for IS-ROOTED occur? How fast is IS-ROOTED in the best case? Express your answer using O or Θ notation. You need not prove that your answer is correct, but you must briefly explain it.
4c. When does the worst case for IS-ROOTED occur? How fast is IS-ROOTED in the worst case? Express your answer using O or Θ notation. You need not prove that your answer is correct, but you must briefly explain it.
Send your request at realcode4you@gmail.com to get above data structure problem solution or need any other data structure assignment problem solution.
Комментарии