Reference no: EM13968329
1. A ?le contains only colons, spaces, newlines, commas, and digits in the following frequency: colon (100), space (605), newline (100), comma (705), 0 (431), 1 (242), 2 (176), 3 (59), 4 (185), 5 (250), 6 (174), 7 (199), 8 (205), 9 (217). Construct the Huffman code.
2. Part of the encoded ?le must be a header indicating the Huffman code. Give a method for constructing the header of size at most O(N) (in addition to the symbols), where N is the number of symbols.
3. Complete the proof that Huffman's algorithm generates an optimal pre?x code.
4. Show that if the symbols are sorted by frequency, Huffman's algorithm can be implemented in linear time.
5. Write a program to implement ?le compression (and uncompression) using Huffman's algorithm.
|
Analysis of the sampling algorithm
: 1. Much of the information used to compute the median-of-median-of-?ve is thrown away. Show how the number of comparisons can be reduced by more careful use of the information. 2. Complete the analysis of the sampling algorithm described at the en..
|
|
Determine the instantaneous acceleration
: An object moves along thex axis according to the equationx = 2.55t2 - 2.00t + 3.00, wherex is in meters andt is in seconds. Determine the average speed between t = 3.00 s and t = 5.00 s.
|
|
Implement the closest-pair algorithm
: 1. Write a program to implement the closest-pair algorithm. 2. What is the asymptotic running time of quickselect using a median-of-median-of- three partitioning strategy?
|
|
What fact or piece of information did you learn that was new
: Take the "Find Your Fit" assessment under "The profession" menu along the left hand side. What does it suggest as "you early career" type, if you were to go into the accounting field?
|
|
Method for constructing the header of size
: Part of the encoded ?le must be a header indicating the Huffman code. Give a method for constructing the header of size at most O(N) (in addition to the symbols), where N is the number of symbols. Complete the proof that Huffman's algorithm generates..
|
|
What are benefit of federal and state social welfare program
: What are the benefits of federal and state social welfare programs today? What are the drawbacks? What experiences have you, or someone you know, had with a social welfare program?
|
|
Consider an oil-wildcatting problem
: Consider an oil-wildcatting problem. A decision maker has mineral rights on a piece of land that he believes may have oil underground. There is a 30% chance that the decision maker will strike oil if he drills. If he drills and strikes oil, then the ..
|
|
Completion time for multiprocessor
: 1. Show that the greedy algorithm to minimize the mean completion time for multiprocessor job scheduling works. 2. The input is a set of jobs j1, j2, ... , jN, each of which takes one time unit to complete. Each job jiearns di dollars if it is comple..
|
|
Determine the electric potential energy of the initial state
: There is the information and then the questions: A stationary block has a charge of +6.0×10-4 C. A 0.80-kg cart with a charge of +4.0×10-4 C is initially at rand separated by 4.0 m from the block. The cart is released and moves along a frictionles..
|