When a client is released from a server it executes the following.

If the list of queues to be visited is not empty then remove the next one and
	enqueue on that queue.

Otherwise mark the completion time by consulting the clock and wait on (insert
	self into) a list so that termination statistics may be computed when all
	clients finish.  



Build such a system and test it.  



5.  Huffman Encoding and Decoding Problem


It is a common occurrence for us to have a text file of some kind that we want
to compress, so it will take up as little space a possible.  Perhaps this is
because we want to save on storage space or charges or because we are about to
send the file over an expensive phone link.


You probably know that computers use some sort of numeric encoding to represent
characters - EBCDIC and ASCII are the two most popular ones.  These encodings
all have the property that any legal character is represented by the same
number of bits (7 bits in ASCII, 8 in EBCDIC).  This makes these encodings
convenient to use, but also makes them somewhat redundant: if we could come up
with an encoding that uses only a few bits for common characters like E or T,
it would more than make up for a corresponding growth in the encodings for rare
letters like X or Q.


One way to think about the notion of character encodings is to consider a tree
structure where 0 means "go left" and 1 means "go right".  If I am interested
only in the letters ABCDEFGH, I could assign them three-bit codes as follows:


	A	000		E	100
	B	001		F	101
	C	010		G	110
	D	011		H	111


This corresponds to the tree structure in Figure 5.5, where each code for a
letter is represented by the path from the root to the corresponding letter.




If we know that E happens a lot more often than G, we might want to distort
this tree, so that E is fewer steps from the top and G is correspondingly more.
The tree in Figure 5.6 is the best tree possible given the actual English
frequencies of these eight letters.  This gives the encodings:


	A	11			E	01
	B	00000			F	0001
	C	100			G	00001
	D	001			H	101


 


One thing to notice is that the numerical order is no longer the same as the
alphabetical order.  However, since E is about eight times as common as G, we
can see that we will use a lot less space.  The word GEEEEEEEE required 27 bits
before, but only 21 now.  (In practice, compression of better than 50% is
common.)

If we know the expected frequencies of characters in the file, we can use an
encoding that gives us the smallest expected file length.  Such an encoding is
called a "Huffman encoding" and the tree that summarizes such an encoding is
called a "Huffman tree".


We can use a table or dictionary of Huffman codes to compress a file.  For
instance, if the file consisted only of the word CHAFED, we could look up C and
output 100, look up H and output 101, and so on, producing the output file
10010111000101001.  This is slightly compressed, requiring only 17 bits in
contrast to 18 needed if we use fixed-length codes, or 42 if we use ASCII.)


To decompress the compressed file, it is convenient to use the tree.  We start
at the root and look at the first bit of the compressed file.  Since it is a 1,
we move down to the right and read the second bit.  Since it is a 0, we move
left.  The third bit is 0, so we move left again, which brings us to the C.
Thus the first letter is C; we output it and start over at the root again.




Huffman's Tree Building Algorithm


1. Collect all the characters you want to encode and assign a weight to each,
based upon the expected frequency of each character in a typical input file.
Frequencies are given below.

2. Create a list of one node binary trees with these weights and characters.
	

3. Repeat until there is only one node left in the list (n-1 times):

	a. Remove the two nodes with the smallest weights and connect 
	them to a common parent.

	b. Assign the weight of the parent to be the sum of the weights of the two
	children.

	c. Insert this new tree into the list of trees.

4. The remaining tree is the Huffman tree.



Relative frequencies of allowed character set:




	73	9	30	44	130	28	16	35	74	2
	A	B	C	D	E	F	G	H	I	J

	3	35	25	78	74	27	3	77	63	93
	K	L	M	N	O	P	Q	R	S	T

	27	13	16	5	19	1
	U	V	W	X	Y	Z

	2	2	9	15	258	20
	(	)	,	.	space	eoln


NOTE: End-of-line is not treated as a character in many systems.  It is
present here because we want our compressed files to record the locations where
line boundaries appeared so that we can restore those line boundaries when we
decompress the files.  The easiest way to do this is to choose some character
not shown above (for ex, '$') to stand in for eoln in the Huffman tree.  When
an end-of-line condition (eoln) is detected on input, it should be encoded with
the compressed code.  When the compressed code for eoln is detected during the
decode operation, start a new line of decoded output.

	

Here is the beginning of an example of this.  After performing step three for
the first time we have




	2  2  3  3  3  5  9  9  and so on until  130  258
	(  )  *  K  Q  X  B  ,                    E  space
	     / \
	    Z   J

After
performing it the second time we have




	 3  3  3  4  5  9  9 and so on until  130  258
	 *  K  Q  *  X  B  ,                   E  space
	/ \      / \
	Z  J    (  )

And
after performing it the third time we have




	3   4   5   6   9   9 and so on until  130   258
	Q   *   X   *   B   ,                   E   space
           / \     / \
          (   )   *   K
                 / \
                Z   J


After you have built the tree, you must traverse it recursively to extract the
encodings.  An abstract version of this part might look like this:




ExtractCodes (node p, path fromroot ) IS
-- fromroot contains the path from the root to node p 

	if (p is a leaf node) then
		announce that the code for character in p is fromroot
	else 
		ExtractCodes(LeftChild(p), fromroot extended with 0);
		ExtractCodes(RightChild(p), fromroot extended with1);
	end
END 


Even though this doesn't discuss how to implement a "node" or a "path", this is
the correct algorithm for extracting the codes.  The action "announce" might
mean simply printing the code found, or might mean adding it to a table or
dictionary.


Encoding and decoding


Once the encoding table is built, encoding simply involves a table
look-up for each character.


To decode an encoded file, one must examine the bits of the file and use the
Huffman tree to decode.  An algorithm follows:


Huffman Decode:




1. Initialize p to the root of the Huffman tree.

2. While the end of the message has not been reached

Let x be the next bit in the string.

If x = 0 
	then set p to LeftChild(p)
	else set p to RightChild(p)

If p is a leaf then
	Display the character associated with that leaf
	Reset p to the root of the Huffman tree



Build and test a program or set of programs to:


a) Using the frequencies given above, construct a Huffman tree using the
algorithm described above.


b) Traverse the Huffman tree to make a table of the Huffman codes.


c) Use the table of Huffman codes to translate an input file into compressed
form.  Use any input text you like, but make sure it contains only those
characters you have codes for.  This input file should be at least ten lines
long.


d) Use the Huffman tree to translate the compressed file back into normal
text.


Your program should print the codes assigned to the alphabet above, and should
display the original file in character form, the Huffman encoded file in binary
form (that is, as zeroes and ones), and the decompressed file in character
form.  The decompressed file should, of course, be identical to the original.


Your program should also print the length of the original message (in
characters) and the length of the compressed file (in bits).  Since the
alphabet we are using has 32 characters, we would ordinarily need five bits per
character.  How does this compare with the translation done according to your
Huffman codes?


Notes:


1. Since you need to do insertions and deletions from the list of partial
trees, it may be helpful if you organize the partial trees into a list, sorted
by weight; i.e. when you initially build it, use an InsertInOrder procedure.
If you then keep it in order, all deletions are from the front of the list, and
insertions are done using InsertInOrder.


2. Since you will really be writing out ASCII or EBCDIC zeroes and ones to
create the compressed file, the output file will actually be considerably
larger that the original file.  To create a truly compressed file requires
knowledge of how the system stores  values in memory and how they are written
to a file, and the use of low level bit manipulations.


3. As you build the tree, the important data for the interior nodes is the
weight, while in the leaves, the only important data is the
character.  It's easiest to make all values inserted into the tree to be
objects with fields `weight' and `character' and use whichever is appropriate.
Even better is to use two different object types.  In the initial list of
trees, each tree would consist of a single node with both a weight and a
character.


4. You should implement writeIt for the new object types so that it will be
easy to write out the Huffman trees. 


5. A more sophisticated version of this, which is appropriate for long, unusual
files, is to first scan the file to be compressed, determining the actual
frequency of the characters.  Then determine a corresponding Huffman code
tailored to that file.  Then, before sending the file using this encoding, send
the code itself (or equivalently the frequency distribution used to build it)
in the clear (unencoded).  For a file that is long and contains character
distributions significantly different from English prose, this can represent a
large savings.   

 

(Thanks to David Wall of Digital Equipment Corporation for this assignment.)



6.
 Simulation of a simple computer system.  


A simple computer system consists of a processor, with its associated
peripherals, that is capable of processing one job at a time.  However, It is
desirable for the processor to share, or multiplex, its time among the various
jobs, so that when a process requests input or output (I/O) the processor may
execute another process while waiting for the I/O request to complete.  The
reason for this is that I/O is so much slower than the processor that if the
processor simply waited, too much time would be wasted and system throughput
would be reduced to the speed of the slowest device.  A processor contains a
job queue that holds jobs that are ready to be executed but not currently being
executed.  We would like to have a simulator of such a system so as to get
statistics on the time required to complete a job or a certain mix of jobs.
For this purpose,  the processor will provide two services to the jobs: execute
and processIO.  While a job executes the system advances a clock.  Each time a
job executes the system gives it a certain amount of time, and when the job
currently executing exceeds that time it is temporarily halted and placed on
the job queue.  It will be resumed when it reaches the head of the queue.
Whenever a job requests I/O by executing processIO it is also halted and placed
on the queue.  The processor always knows the current job, and when it puts a
job on the queue it extracts a new current job from the queue.  The processor
is also responsible for placing new jobs on the queue when the time comes for
them to be executed.  


Each job has a job number, a start time and an expected time requirement.  This
is the average value of the time the job would take to execute if it were not
interrupted for I/O and had exclusive use of the processor.  In reality the
actual amount of time needed by a job when it runs will always exceed this time
requirement because the delays are inevitable if the job does any I/O and very
likely even if it does not.  The job also has a parameter that measures the
probability that it will do I/O in a fixed time interval, or "clock tick."  The
job must provide services to the processor so that the latter may discover the
job number of a job and its parameters.  It should also permit a processor to
reduce its time requirement toward zero so that as the clock runs the processor
will know when the job has completed.  


When a job gets access to the processor it can be thought of as executing the
following "program" 




WHILE timeRequrement > 0 DO
	processor . execute ();
	IF randomNumber () < I_OProbability THEN
		processor . processIO ();
	END;
END;


The function randomNumber is assumed to return a random real number in
the range of zero to one. Random integers may be obtained from the system
function rand in <stdlib.h>.  Suitable processing will transform
them into the required float values.  


The processor may be assumed to execute the following pseudocode program.




REPEAT
	advanceClock;
	IF new_job_waiting THEN enter_it_into_queue; END;
	IF no_current_job THEN dequeue_a_current_job; END;
	IF current_job_finished THEN 
		terminate_it; 
	ELSIF current_job_requesting_IO THEN
		queue_it;
	ELSE
		advance_time_of_current_job;
	END;
UNTIL no_jobs_in_queue;


When a job terminates its statistics can be printed. 


A refinement of the above is to make the I/O processing more realistic by
requiring a time requirement for completion of the request to be submitted when
the I/O request is submitted.  Then when the processor removes a job from the
queue it can check to see if the previous I/O request has completed, and if not
will reinsert the job on the queue and process another.  Note that you must be
a bit careful here that you don't create an infinite loop of checking without
advancing the clock.  





Some Sample Test data:

	Job	Execution	I/O	Entry
	Number	Time		Prob. 	Time

	1	5		.6	1
	2	1		.2	2
	3	10		.1	4
	4	4		.4	5
	5	3		.2	7
	6	8		.3	9
	7	2		.5	10
	8	9		.9	12
	9	6		.2	13
	10	5		.4	15