HW #3

None of these are due until after the midterm.

3.1 Implement Djikstra's Shunting-yard algorithm, to convert from Infix to Reverse Polish Notation (Postfix).
3.2 Using Binary expression trees, convert from RPN to Infix, using the algorithm described in this link.
3.3 Evaluate a RPN expression using a stack. I'll describe how to do this in class.

test moved to next wednesday

lecture

void print(char *s)
{
if (*s == NULL)
return;
cout << *s;
print(s + 1);
}

void print(int a[], int start, int end)
{
if (start > end)
return;
cout << a[start] << ", ";
print(a, start + 1, end);
}

main()
{
int X[5] = {1, 4, 5, 7};
print(X, 0, 3);
}

HW:
take the map of letters to bitstrings and use it to encode
your text

The cat in the hat

step 1: make one big string of 1s and 0s. concatenation.
say, a for loop through "The cat in the hat", each time, concatenating a[i] to previous string.

step 2: divide strlen by 8 to find size to allocate
byte buffer = new byte[properSize]

step 3: loop through each 8 bits to create a byte. assign
the byte to the proper slot. as you read each "bit", if it is "0", bitshift to left and dont do anything. if it is "1", bitshift to left and bitwise or it with 1.

"0110110"

byte b = 0;
if current is 0:
 b = (b << 1)
else if current is 1:
 b = (b << 1) | 1;

after 8 bits, write it into position buffer[i] and increment i;

going forward, what do we want to store?
a) huffman tree
b) size
c) buffer

we will want to serialize it.
but not yet.

HW #2.6
a rough algorithm for discovering the bit patterns from the Huffman tree:
Algorithm postOrder(v, s)
     if (v is leaf)
arr[v.character] = s;
return;
postOrder (n.left, s+”0”)
postOrder (n.right, s+”1”)


implement that to build an array mapping letters to bit strings

in C++, a char takes up one byte
in Java, a byte takes up one byte

byte b = 0;

to set bit i to 1
b = b | (1 << i);

to set bit i to 0
b = b & ~(1 << i);

to find out if bit i is 1?
if (b & (1 << i) != 0)

to find out if bit i is =?
if (b & (1 << i) == 0)

assuming binary trees:
preorder traversal: SLR
postorder traversal: LRS
inorder traversal: LSR

Sample data structures midterm

See here.

some interesting, useful code

T arr[] = (T []) new Object [n];

int x[] = new int [n];

int front, rear;
front = 0;
rear = 0;

how insert?
arr[rear] = o;
rear++;

how remove?
arr[front] = null;
front++;

eventually, off end of array.
rather, how insert?
arr[rear] = o;
rear = (rear+1) % n;

and same thing for front.

class Person implements Comparable
{
// guts
int compareTo(Object b)
{
Person B = (Person)b;
if (this.age > B.age)
return 1;
else if (this.age < B.age)
return -1;
else
return 0;
}
}

class MyComparator<T> implements Comparator<T>
{
int compare(T a, T b)
{

}
}

main()
{
PriorityQueue<Person> pq = new PriorityQueue<Person> (new MyComparator());
}

class BTree <T extends Comparable> implements Comparable
{
 T element;
 BTree left, right;
 int compareTo(Object o)
 {
BTree<T> bt = (BTree<T>)o;
return this.element.compareTo(bt.element);
 }
}

class LetterAndFreq implements Comparable
{
char letter;
int freq;
int compareTo(Object o)
{
LetterAndFreq b = (LetterAndFreq)o;
if (this.freq > b.freq)
....
}
}

Sorry about Blackboard. Will be up soon.

let us pretend that I have an alphabet of 8 letters. ABCDEFGH
A = 000
B = 001
C = 010
D = 011
E = 100
F = 101
G = 110
H = 111

CAFE
010 000 101 100

AAAAAAAAAAAAAABAAAAAAAAAF

frequencies of these letters
A = 500
B = 10
C = 5
D = 18
E = 200
F = 7
G = 23
H = 2

HW 2.5: using all the data structures you have already created, implement a Huffman tree, which you can later use to encode and decode text.

http://en.wikipedia.org/wiki/Huffman_coding

tentative midterms date Mon, March 21
(two Mon from today)

HW:
implement a binary tree class.

class BTree implements Comparable
{
int element;
BTree left, right;
}
it should be either comparable, or else
you should write a comparator for it.

http://en.wikipedia.org/wiki/Huffman_coding

my own lazy implementation of List-based stack
public class NodeStack<E> implements Stack<E> {
   protected SLinkedList<E> mylist;
   // protected int size; // number of elements in the stack
   public NodeStack() { // constructs an empty stack mylist = SLinkedList<E>(); }
   public int size() { return mylist.size(); }
   public boolean isEmpty() {return mylist.isEmpty()}
   public void push(E elem) {      myList.insertFront(elem);}
   public E top() throws EmptyStackException {      if (isEmpty()) throw new EmptyStackException("empty");      return mylist.front(); }
   public E pop() throws EmptyStackException {      if (isEmpty()) throw new EmptyStackException("empty");      E temp = top(); myList.removeFront();      // link-out the former top node      return temp; } }

It is better, IMHO

class MyVeryOwnComparator implements Comparator<T>
{
boolean compare(T o, T p)
{ Person per1 = (Person) }
}

class PQueue<T>
{
private Comparator<T> comp;
PQueue(Comparator<T> c)
{
comp = c;
}
void pop()
{
if(comp.compare(elem1, elem2)
}
}

main()
{
PQueue<Person>(new MyVeryOwnComparator())
}

2.3:
take your priority queue, instead of ints, it should take Comparable objects. alternatively, you can make the constructor take a Comparator object of your own creation.
do both
*eventually*, it should implement Queue interface.

http://onjava.com/pub/a/onjava/2003/03/12/java_comp.html

if (a.compareTo(b) == 0)
// equivalent to: if (a == b)

if (a.compareTo(b) < 0)
// equivalent to: if (a < b)

if (a.compareTo(b) > 0)
// equivalent to: if (a > b)

Comparator
http://www.javadeveloper.co.in/java-example/java-comparator-example.html