Math Is Fun Forum

Prakash Panneer

Member

Registered: 2006-06-01

Posts: 110

URGENT_Mathematical Algorithms_Please help me

Please help me with these problems...

4.  Ternary Huffman. Trimedia Disks Inc. has developed “ternary” hard disks. Each cell on a disk can now store values 0, 1, or 2 (instead of just 0 or 1). To take advantage of this new technology, provide a modified Huffman algorithm for compressing sequences of characters from an alphabet of size n, where the characters occur with known frequencies f1, f2, . . . , fn. Your algorithm should encode each character with a variable-length codeword over the values 0, 1, 2 such that no codeword is a prefix of another codeword and so as to obtain the maximum possible compression. Prove that your algorithm is correct.

5.  The basic intuition behind Huffman's algorithm, that frequent blocks should have short encodings and infrequent blocks should have long encodings, is also at work in English, where typical words like I, you, is, and, to, from, and so on are short, and rarely used words like velociraptor are longer.

However, words like fire!, help!, and run! are short not because they are frequent, but perhaps because time is precious in situations where they are used.

To make things theoretical, suppose we have a file composed of m different words, with frequencies
f1, . . . , fm. Suppose also that for the ith word, the cost per bit of encoding is Ci. Thus, if we find a prefix-free code where the ith word has a codeword of length li, then the total cost of the encoding will
be (summation) i  fi  Ci  li.

Show how to modify Huffman's algorithm to find the prefix-free encoding of minimum total cost.

6.  A server has n customers waiting to be served. The service time required by each customer is known in advance: it is ti minutes for customer i. So if, for example, the customers are served in order of increasing i, then the ith customer has to wait  (summation)( j = 1 to i) tj minutes.

We wish to minimize the total waiting time

                T = (summation((i = 1 to n) (time spent waiting by customer i)

Give an efficient algorithm for computing the optimal order in which to process the customers.

This is urgent.
Thanks in advance!

---

Letter, number, arts and science
of living kinds, both are the eyes.

Kurre

Member

Registered: 2006-07-18

Posts: 280

Re: URGENT_Mathematical Algorithms_Please help me

6. Isnt the order just with increasing serice time? ie if a is served before b, Ta≤Tb.

Prakash Panneer

Member

Registered: 2006-06-01

Posts: 110

Re: URGENT_Mathematical Algorithms_Please help me

Yes, Tb is higher. Since here we used summation notation.

---

Letter, number, arts and science
of living kinds, both are the eyes.