Red black trees here.

An example of a red–black tree

class Queue<T>
{
SLL<T> list = new SLL<T>();
public int size() { return list.size(); }
public void enqueue(T t) { list.addAtTail(t); }
public T dequeue(void) { return list.removeFront(); }
}

class Stack<T>
{
SLL<T> list = new SLL<T>();
public int size() { return list.size(); }
public void push(T t) { list.addAtFront(t); }
public T dequeue(void) { return list.removeFront(); }
}

class Stack<T>
{
ArrayList<T> list = new ArrayList<T>();
public int size() { return list.size(); }
public void push(T t) { list.add(list.size(), t); }
public T pop(void) { return list.remove(list.size()); }
}

class Stack<T> extends SLL<T>
{
public int size() { return super.size(); }
public void push(T t) { addAtFront(t); }
public T dequeue(void) { return removeFront(); }
}

// NOT adapter pattern
class Stack<T>
{
SLNode<T> head, tail;
void push(T t) {
SLNode n = new Node<T>(t,head);
head = n;
size++;
}
T pop() {
SLNode n = head;
head = head.next;
return n.value;
size--;
}
}

class PQ<T>
{
Comparator<T> comp;
SLL<T> list = new SLL<T>();
PQ(Comparator<T> c)
{
comp = c;
}
void enqueue(T t) { list.insertAtEnd(t); }
T dequeue()
{
T theMin = list.getFirstItem();
for (T element : list)
{
if(comp.compare(theMin, element) < 0)
{
theMin = element;
}
}
// change to explicit iterator
for (T element : list)
{
if(comp.compare(theMin, element) == 0)
{
it.remove();
return theMin;
}
}
}
}

Sample final

is here.

http://www2.research.att.com/~bs/whitespace98.pdf

HW:
step 1)
find the freq table

2) charfreq class, comparable

3) revisit your generic binarytree class, where binarytrees should also be comparable. based on the value stored at the root.

4) Take your freq table, create a forest of trees, where each tree contains a charFreq.

Revisit your priorityqueuue. make sure it is generic.

5) Algorithm for creating a Huffman Tree:
a)  Take your freq table, create a forest of trees, where each tree contains a charFreq.
b) As you create each tree in your forest, insert it into the PQ.

c) While PQ.size() != 1
Tree T1 = PQ.dequeue();
Tree T2 = PQ.dequeue();
Tree T3 = join(T1, T2); // where root node's charfreq's freq is the sum of the freq of roots of T1 and T2
PQ.enqueue(T3);

outside of while loop:
d) Tree Huffman = PQ.dequeue();

6) Use the Huffman tree to encode a text file. (You may encode it as a string first.)
Do a visit of each node. If go to left, append a '0', else append a '1'.
Write to a table what string corresponds to a given letter.

Then, loop thru your file, creating an appropriate text string.

Using bitshifting, << >> | &, generate byte array. Write to a file.

7) Open a file, use your existing Huffman Tree, convert bit pattern (or string) to original text.

Solutions to sample midterm

12)
class Node
{
int val;
Node next;
}

13)
a) class SLL
{
Node head, tail;
int size;
// constructor present but not given here
// choose not to make header or trailer
}

b) void insertBefore(Node n, int x)
{
Node m = new Node(x);

if (n==head)
{
m.next = n;
head = m;
}
else
{
// traverse from head
for (Node cur = head; cur.next!=n; cur=cur.next)
; // do nothing
cur.next=m;
m.next=n;

}
size++;
}

c) void insertAfter(Node n, int x)
{
Node m=new Node(x);
m.next = n.next;
n.next = m;

if (n==tail)
m = tail;
size++;
}

d) void remove(int value)
{
if (size==0)
return;
Node prev = null;
for(Node cur = head; cur != null && cur.val != value; prev=cur, cur=cur.next)
; // do nothing
if (prev==null) // found item at head
{
head=head.next;
size--;
}
else if (cur != null && cur.val == value) // item found
{
prev.next = cur.next; // leapfrog
}
if (prev.next==null)
tail=prev;
}
d) void removeSpan(Node start, Node finish)
{
start.next = finish;
}

e) void swap(Node n, Node m)
{
int temp = n.val;
n.val = m.val;
m.val = temp;
}

Test: Thurs Mar 22

HW: Construct a Priority Queue
using the Adapter design pattern,
use a linked list or array (/vector)
to implement a PriorityQueue of ints.

Vote!

joshwaxman@gmail.com
CS313 vote
Thu Mar 15 vs. Tue Mar 20 vs Thurs Mar 22

Sample midterm

Data Structures Midterm     Name: __________________________

1) Draw a picture of a Doubly Linked List, with nodes holding values of 4, 5, and 7. You should not only have a head and tail, but also a header and a trailer.







2) Draw and describe the steps involved in removing the middle element (5).








3) Deleting from the end of a singly linked list is O(n). Demonstrate the steps in deleting from the end of such a list and explain why it is O(n).







4) Deleting an element from the middle of a singly linked list (the node is passed in) is O(n). Explain, in a sentence or two, why.







5) Deleting from the end of a doubly Linked list, where we have a reference to the tail, is on the order of what? Explain why.









6) Draw a circular array with a couple of elements and a front and rear.







7) How would you implement (in words) removal from the end of the circular array? What data members would you modify? How would you handle boundary conditions?






8) How would you implement removal from the middle of a vector based on a normal array, rather than a circular array? Explain in words.






9) Give one reason it might be better to use an array rather than a singly-linked list to implement a stack.






10) f(n) = 15n^2 + 10n + 1. This is O of what? Give a proof with c and n_0.








12) Write a Java class for a node for a singly-linked list.
13) Write code for a Singly Linked List class, which makes use of that node. Make a head, a tail, and a size. Include the following methods (others may exist, but you need not write them), and make certain to handle the boundary conditions and to check for error conditions:
insertBefore(Node n, int x);
insertAfter(Node n, int x);
remove(int value);
removeSpan(Node start, Node finish);
swap(Node n, Node m);

Queue based on a singly linked list, using the Adapter design pattern

size()
isEmpty()
enqueue()
dequeue()
front()

Queue based on a Vector, using the Adapter design pattern

size()
isEmpty()
enqueue()
dequeue()
front()

Thurs, Mar 15, make your StackArray into an iterable collection

class ArrayStack<T> implements Iterable<T>
{
// ...
// various methods we have

Iterator<T> iterator()
{
// will take snapshot approach MyNiftyArrayStackIterator<T> mnasi= new MyNiftyArrayStackIterator<T>(a.clone(), size);
return mnasi;
}
}

class MyNiftyArrayStackIterator<T> implements Iterator<T>
{
int currElem = 0;
MyNiftyArrayStackIterator(T b[], int size) { save to local vars; }
boolean hasNext() { return currElem < size; }
T next() { return b[currElem++]; }
}

HW: Postfix notation, redux. This time, instead of simply evaluating, we want to build the expression tree.

Homeworks as they are due:
Binary expression tree (part one) -- next Tuesday, Feb 28
Binary expression tree (part two) -- next Thursday, Mar 1
Your stack implements Queue, Mar 6
Array-based Queue, Mar 8

Late Homework Guidelines

Each homework is graded on a scale from 0 to 5.

For each day late, 0.5 is deducted from the total possible score for that homework.

The first few (four) homeworks are due this Thursday.

"It seems like there is a neater way to do this, without all the @supress warnings."


http://stackoverflow.com/questions/1025837/initialize-java-generic-array-of-type-generic

http://stackoverflow.com/questions/529085/java-how-to-generic-array-creation

lecture 3

I described up to postfix using arrays assignment (#4).

int x[] = new int[100];

for (int i = 0; i< x.length; i++)
System.out.println(x[i]);

for (int p : x)
System.out.println(p);

interfaces
Iterable
Iterator

when I implement Iterable, I must provide a
method called iterator()

iterator returns Iterator

anything implementing Iterator must provide
boolean hasNext()

next()

int x[] = new int[100];
Iterator i = x.iterator();
while(i.hasNext())
{
int p = i.next();
System.out.println(p);
}


syntactic sugar

Welcome to CS313

Here is a link to the book on Amazon. It is also available in the QC library.

10% -- Class participation
20% -- Homework
30% -- Minimum of Midterm and Final
40% -- Maximum of Midterm and Final

Blackboard link:  2012 Spring Term (1) Data Structures CSCI 313 11[7767] (Queens College) 

There are some slides up on BlackBoard already.


HW:
1. Get the book (either amazon, library)
2. swap function in Java
3. Stack based on an array