3. Explain why a non-full binary tree cannot correspond to an optimal prefix-free code. (This is similar to problem 15.3-2 from CLRS) 4. Find an optimal Hoffman code for g:5, o:15, u:28, m:25, b:10, c:17. 5. Given an optimal Hoffman code represented by B(T) for characters C, what is the expected length in bits of a string of n characters?

3. Explain why a non-full binary tree cannot correspond to an optimal prefix-free code. (This is similar to problem 15.3-2 from CLRS) 4. Find an optimal Hoffman code for g:5, o:15, u:28, m:25, b:10, c:17. 5. Given an optimal Hoffman code represented by B(T) for characters C, what is the expected length in bits of a string of n characters?

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

Consider eight points on the Cartesian two-dimensional x-y plane. a g C For each pair of vertices u and v, the weight of edge uv is the Euclidean (Pythagorean) distance between those two points. For example, dist(a, h) = V4? + 1² = v17 and dist(a, b) = v22 + 0² = 2. Using the algorithm of your choice, determine one possible minimum-weight spanning tree and compute its total distance, rounding your answer to one decimal place. Clearly show your steps.
Given an undirected weighted graph G with n nodes and m edges, and we have used Prim’s algorithm to construct a minimum spanning tree T. Suppose the weight of one of the tree edge ((u, v) ∈ T) is changed from w to w′, design an algorithm to verify whether T is still a minimum spanning tree. Your algorithm should run in O(m) time, and explain why your algorithm is correct. You can assume all the weights are distinct. (Hint: When an edge is removed, nodes of T will break into two groups. Which edge should we choose in the cut of these two groups?)
Suppose there is undirected graph F with nonnegative edge weights we ≥ 0. You have also calculated the minimum spanning tree of F and also the shortest paths to all nodes from a particular node p ∈ V . Now, suppose that each edge weight is increased by 1, so the new weights are we′ = we + 1. (a) Will there be a change of the minimum spanning tree? Provide an example where it does or prove that it cannot change. (b) (3 points) Will the shortest paths from p change? Provide an example where it does or prove that it cannot change.
In a lecture the professor said that for every minimum spanning tree T of G there is an execution of the algorithm of Kruskal which delivers T as a result. ( Input is G). The algorithm he was supposedly talking about is: Kruskal() Precondition. N = (G, cost) is a connected network with n = |V| node and m = |E| ≥ n − 1 edges.All edges of E are uncolored. postcondition: All edges are colored. The green-colored edges together with V form one MST by N. Grand Step 1: Sort the edges of E in increasing weight: e1 , e2, . . . , em Grand step 2: For t = 0.1, . . . , m − 1 execute: Apply Kruskal's coloring rule to the et+1 edge i dont really understand this statement or how it is done. can someone explain me what he meant?
a) Why can Dijkstra's algorithm not work properly on graphs with negative weighted edges? Explain with example. Implement the greedy approach for coin change algorithm and show your step by step approach to give change of 139 in coin change with {1, 3, 5, 25, 45, 60} unit values. c) Write the procedure for calculating GCD and LCM of the following numbers. Also write the answers at last. 2, 4, 5, 20
a. Write the Kruskal's Algorithm to find minimum spanning tree! b. Use Kruskal's algorithm to find a minimum spanning tree for the given weighted graph and list the stages! 2 1 b 2 1 d 3 1 If 3 8 2 3 4 3 li 4 k 3 4 2 2 3 m 2. 3. 3. 2. 3. 2. 3. 2.
find the solution of the following ip problem using branch and bound method in order to find solutions of the arising Lp relaxations, you can use the graphical solution method. Use breadth first search while evaluating branch and bound tree. Z= 7x + 5y Subject to x+4y≤10 3x-4y≤6 x,y € N
In the Euclidean (metric) Traveling Salesperson Problem (TSP), we started with a DFS traversal of the minimum spanning tree (MST) and then skipped vertices that we had already visited. Why were we able to allow skipping of nodes? O Because DFS run on an MST adds an exponential number of vertices O In a metric space the triangle inequality states that removing a vertex cannot lengthen the path O In the Euclidean metric, distance in measured in the number of edges, so removing edges makes the path shorter O It feels right
Consider the Fibonacci sequence F(0)=0, F(1)=1 and F(i)=F(i-1)+F(i-2) for i > 1. For the sake of this exercise we define the height of a tree as the maximum number of vertices of a root-to-leaf path. In particular, the height of the empty tree is zero, and the height of a tree with a single vertex is one. Prove that the number of nodes of an AVL tree of height h is at least F(h) and this inequality is tight only for two values of h.
Determine P(A x B) – (A x B) where A = {a} and B = {1, 2}.
Consider the following graph. b Q 17 3 6 5 3 7 d 3 QU 2 g 7 h $ برا 3 N نی k 1 (i) Using either Prim's or Kruskal's algorithms, determine the minimum spanning tree of the tree given below. State which algorithm you used. (ii) Find the shortest path of the graph below from A to L. Use Dijsktra's algorithm and show all working.
Problem 5 R y. Let G be a connected weighted undirected graph with n nodes and m edges. The weight of edge e is represented as we. We define a minimum-maximum spanning tree to be a spanning tree T that minimizes the quantity Y = max we eeT A minimum-maximum spanning tree has the smallest maximum edge weight of all possible spanning tree. To show a statement is correct, you need to provide a proof. To show a statement is wrong, you only need to provide a counter-example. (a) maximum spanning tree for G. Prove that a minimum spanning tree of graph G is always a minimum- Show that a minimum-maximum spanning tree is not necessary a minimum (b) spanning tree.