Dec 20,
4-6
C205
lecture 12-23
not cumulative

homeworks due the 27th

List of Homeworks

HW1: Iterable, generic, array-based stacks.
HW2: Your own String data type, with methods:
len
get
set
append
insert(string s, int pos), which will insert s into position pos in your MyString type.
HW3: From Sept 22:
Write a recursive printLastToFirst(Node here):
write an iterative printLastToFirst(Node here):
If you can, figure out what the recursive and iterative implementations are O of.
HW4: The Huffman tree, with all its parts

The empty slots are optional, for students who wanted to submit each part / development as a separate entry.

HW# 4.4: Modify your priority queue class so that instead of storing ints, it stores a generic, Comparable type.

what this entails:
change some ints to T
instead of if (a[i]<a[i+1])
put in
if (a[i].compareTo(a[i+1]) < 0)

Now, implement the following algorithm to **build** your HuffmanTree:
1) read your file to generate CharFreqs.
2) Take each CharFreq and put it into a new BTree, at the root. You will thus create a forest of BTree<CharFreq>s.
3) Take each BTree in that forest and insert it into your PriorityQueue.

4)
while (PQ.size() != 1)
{
BTree a = PQ.pop();
BTree b = PQ.pop();
BTree c = BTree.join(a,b);
PQ.push(c);
}
BTree huffmanTree = PQ.pop();

HW 4.3

modify what you have prev.

make a generic BinaryTree class. each Node's element will be Comparable. (The plan is that the element we will store in each node will be a CharFreq.)

implement the following 2 methods:
1) join(t1, t2), in which a new tree will be returned with t1 and t2 as the subtrees.
2) Binary Trees (or BTNodes) should be Comparable. so we will have compareTo. it will be based on the compareTo of the element contained in the node at the top of the respective trees.

class BinaryTree<T>:
BinaryTree left, right
T element

class BTree:
int element
BTree left, right, parent

processList(int a[])
{
if (*a == -1) // base case
return;
cout << *a;
processList(a+1);
}

processList(Node *a)
{
if (a == NULL) // base case
return;
cout << a->element;
processList(a.next);
}

HW 4.2: Two components to build.
Read in a file.

"The quick brown fox jumped over the lazy dog. It jumped nicely."

The file will have ASCII text.

Make a frequency array to count up how many times each character occurs. Then, print out how many times each character occurs.

Make a CharFreq class. It will store a Character and its Frequency.

class CharFreq
{
char Char;
int Freq;
}
CharFreqs should be Comparable.
There is an interface in Java called Comparable.

http://download.oracle.com/javase/1.4.2/docs/api/java/lang/Comparable.html

How is a < b, a > b, a == b? Based only on their Frequency.

The Data Structures test

has been delayed until Thursday.

HW #4.1: Write a Priority Queue of ints. A collection. size, isempty, enqueue, dequeue.