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.

Here is a link to the sample midterm.

HW: modify your Stack to make it Iterable.

class MyStack<T> implements Iterable
{
Iterator<T> iterator()
{
return new MyIterator<T>(this);
}

}

class MyIterator<T> implements Iterator
{
// a copy of my Stack array
T arr;
int curEl = -1;
MyIterator(MyStack<T> ms)
{
arr = new T[ms.top]
for loop to copy ms.arr into this.arr
}
T next()
{
return arr[++curEl];
}
boolean hasNext()
{
return curEl == arr.length;
}

}

This code is probably buggy

LLast part of this data structure.

Moving on: Implement Huffman tree encoding
we will need MANY interacting data structures
binary trees, priority queues, interfaces like comparator and comparable, etc.

The slides implement a Stack based on a Singly Linked list by *reimplementing* the necessary subset of methods of the Singly linked list class.

What *I* would suggest:
*Assume* you have a Singly Linked List class already. Make it a private data member. Adapt the Singly Linked to be a SLLStack by wrapping the methods.

class NodeStack<E>
{
protected SLL<E> sll; //
public NodeStack<E>() { // constructs an empty stack
sll = new SLL(); }
public int size() { return sll.size(); }
public boolean isEmpty() {return sll.size()==0;}
public void push(E elem) {
sll.insertFront(elem);
}
public E top() throws EmptyStackException {
     if (sll.isEmpty()) throw new EmptyStackException("empty");
return sll.returnFront(); // find some way to get access to the first elem
}
   public E pop() throws EmptyStackException {   if (sll.isEmpty()) throw new EmptyStackException("empty");       return sll.removeFront();}
}
dequeue (pronounced dee-kyoo) means remove from a queue (kyoo)

deque (pronounced deck) is a certain data structure

What about "my" way of writing a Queue based on a SLL?
class MyQueue<E>
{
protected SLL<E> sll; // reference to the head node  
void enqueue(E elem)
{
sll.insertAtEnd(elem);
}

E dequeue()
{
if (sll.isEmpty())
crashAndBurn();
return sll.removeFront();
}
}

Link to the sample midterm
https://docs.google.com/View?id=ajbqhgmq9qdz_59khz242gh&pli=1

The midterm will be Tuesday, Nov 1, 2011

class DList
{
   DNode prev(DNode current)
   {
return current.prev;
   }
}

main()
{
DNode j;
DList dl;
//...
j.getPrev(); // no! Don't do that!
dl.prev(j);

dl.replace(j, 6);
}



class ArrayBasedStack<T> implements Iterable<T>
{
/// ...
Iterator<T> iterator() { return new ArrayBasedStackIterator<T>();  }
}

class ArrayBasedStackIterator<T> implement Iterator<T>
{
boolean hasNext() { return false; }
Iterator<T> next() { return null; }
}


for (Iterator<T> it = L.iterator(), it.next(); it.hasNext() == true;
it.next())




List<Integer> values;


// ... statements that create a new // values list and int sum = 0;

Iterator<Integer> it = values.iterator();
for (Integer i = it.next(); it.hasNext(); it.next())
{ sum += i; }




class ArrayBasedStack<E> implements java.util.Queue<E>
{
public void push(E o) { A[top++]=o; }
public boolean add(E o)
{
push(o);
}
}

HW: Modify your Stack code to make use of the Queue<T> interface.

Unfortunately, there does not seem to be a Stack<T> interface, just a Stack<T> class. They recommend using the Deque interface and calling the associated stack methods instead of this Stack class. However, I don't want you to have to implement every single method associated with a Deque interface. Instead, implement the superinterface to Deque, which is java.util.Queue<T>.

Certain inherited methods from the superinterface Collection it does not make sense to implement. For example, why get an iterator? The rules for a stack are such that we can only see the top element. The same for the contains method. Therefore, only focus on the ones that are directly mentioned in the documentation for Queue, except, mentally substitute stack for queue:

Method Summary
boolean	add(E e)           Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions, returning true upon success and throwing an IllegalStateException if no space is currently available.
E	element()           Retrieves, but does not remove, the head of this queue.
boolean	offer(E e)           Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions.
E	peek()           Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.
E	poll()           Retrieves and removes the head of this queue, or returns null if this queue is empty.
E	remove()           Retrieves and removes the head of this queue.

In addition, the following from the superinterface Collection makes sense to implement:

Methods inherited from interface java.util.Collection
addAll, clear, equals, isEmpty, size, toArray, toArray

function addToFront(value x): #DLinked List, no 'header'
n = new Node(x)
n.next = head
n.prev = null

head.prev = n
head = n
size++
#actually, have to test for 0 elements to set tail

function addToFront(value x): #DLinked List, with 'header'
n = new Node(x)
n.prev = header
n.next = header.next
header.next = n
n.next.prev = n
size++

HW:
templatize your stack class

lecture

function removeLast(): # DLinkedList with trailer
if size = 0:
error!
lastElem = tail.prev

lastElem.prev.next = lastElem.next # or, tail
lastElem.next.prev = lastElem.prev
size--


function removeLast(): # DLinkedList without trailer
if size = 0:
error!
else if size = 1:
head = tail = null
size--
else:
tail = tail.prev
tail.next = null
size--


function insertFront(elem x): # DLinkedList with header
n = new Node(x)
oldFirstNode = head.next

head.next = n
n.prev = head

oldFirstNode.prev = n
n.next = oldFirstNode
size++
/*
# their way, v being the new node n
w = head.next
v.next = w
v.prev = head
w.prev = v
head.next = v
size++
*/

function insertFront(elem x): # DLinkedList without header and trailer
n = new Node(x)

if size = 0:
head = tail = n
else:
n.next = head
head = n
n.prev = null
n.next.prev = n
size++


An "interesting" situation. We have DNodes and Dlists.
DNodes have getNext() and getPrev()
DLists have getNext(DNode n) and getPrev(DNode n)

procedure based
DNode getPrev(Dnode n)
{

}

object oriented programming
n.getPrev()

lecture

HW: modify the stack class, such that when you reach the capacity, it increases in size.

time the pushing of elements.
start by inserting, say 50.
100
200
300
400
500

until 1000.
play around to find a good magnitude

based on this, push is O(what)?

________________________

how do i traverse the linked list?
for (Node current = head; current != null; current = current.next)
;// do something with the current node


function printFirstToLast(Node here):
if here = null:
return
else:
# do something
print here.element
printFirstToLast(here.next)

HW: 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.


How do we insert at the start?

function insertAtStart(value x):
n = new Node()
n.element = x
n.next = head
head = n
size++

function insertAtEnd(value x):
# first, create the new node
n = new Node()
n.element = x
n.next = null

# then, find the last node in the list
for(current = head; current.next != null; current = current.next)
; # do nothing

# now, current in the end of the list
current.next = n
size++

function insertAtEnd(value x): # this time, with a tail
# first, create the new node
n = new Node()
n.element = x
n.next = null

# then, add to the end of the list
tail.next = n

# then, update the tail
tail = n
size++


function insertBefore(element x, Node v):
# find the node immediately before v
for (curr=head; curr.next!=v; curr=curr.next)
; # do nothing

# create a node
n = new Node()
n.element = x

# put it in the list in proper place
# recall that curr in the node before v
curr.next = n
n.next = v


function insertBeforeValue(element x, value v):
for (curr=head; curr.element!=v; prev=curr, curr=curr.next):
; # do nothing
# now, curr is the node with element v in it

# new node
n = new Node()
n.element = x

#put n in its proper place
n.next = curr
prev.next = n

hw: into the string data type, add a method
called insert(string s, int pos)
which will insert s into position pos in your
MyString type.

hw:
write a string class
based on an array of chars
methods:
len
get
set
append

some notes

class MutableString
{
private String data;
String toString() { return data; }
setValue(String x) { data = x; }
String getValue() { return data; }
}


Swap(MutableString a, MutableString b)
{
MutableString t = new MutableString;
t.setValue(a.getValue()); // c = a
a.setValue(b.getValue()); // a = b
b.setValue(t.getValue()); // b = t
}

String a = "hello";
String b = "hi";
if (a.equals(b))
{

}
String s = "";
for (int i = 0; i < 100; i++)
{
s += i;
s += "\n";
}


String s = new String("");
for (int i = 0; i < 100; i++)
{
s += new Integer(i).toString();
}

more hw

HW #2:

Adapt your C++ stack class into a Java class.

class Stack
{
int A[] = new int[100];
//...

Due: next Thurs


HW:3
Show that 2n - 5 is O(n)
Due: next Thurs

Slides now up

on Blackboard, under course documents.

lecture 2 notes

HW #1: Make a C++ Stack class. It should hold ints. We should have the following methods: empty, full, push, pop, top. It should be based on an array.

class Stack
{
int A[100];
int Top;
public:
Stack() { }
void push(int x) { A[Top++] = x; }
int pop() { return A[--Top]; }
int top() { return A[Top-1]; }
bool isEmpty() { ... }
bool isFull() { ... }
}

main()
{
Stack a;
a.push(6);
...
return 0;
}

Person p   =   new Person("John");
// is the same as
Person p;
p   =   new Person("John");

Welcome to Data Structures for Queens College

Course material will go here!

Midterm -- 30%
Final -- 40%
Homeworks -- 30%
Approximately 10 homework projects

The book:
Data Structures and Algorithms in Java, 5th Edition 
by Michael Goodrich
ISBN-13: 978-0-470-38326-1

Tentative syllabus:
We will follow the order of the book. See the PowerPoint slides.


The book's website.