Grades

are now in CUNYFirst

some answers for final

again, link to the final


 2 3 + 4 ×

string Visit(node, priorPrecedence) {
  if node is number
    return number.ToString()
  result = Visit(left, node.precedence) +
           node.Operator +
           Visit(right, node.precedence)
  if node.precedence < priorPrecedence
    result = '(' + result + ')'
  return result
}

// two parts.
//part 1: build the expression tree.

Node buildExpressionTree(string s)
{
Stack<Node> St = new Stack<Node>();
for (char c : s)
{
switch(c)
{
case '+':
case '-':
case 'x':
case '/':
Node rhs = St.pop();
Node lhs = St.pop();
Node n = new Node(c);
n.right = rhs;
n.left = lhs;
St.push(n);
break;
default: // a digit
Node n = new Node(Integer.parse(c.toString()));
St.push(n);
}
}
return St.pop();
}

// part 2
// printing out the expression tree InOrder
void InOrder(Node n)
{
if (n == null)
return;
System.out.print("(");
InOrder(n.left);
System.out.print(" " + n.element + " ");
InOrder(n.right);
System.out.print(")");

}

test time and room

SB-B137 at 8:30 PM

And the winner is...

Cumulative!

data structures in a database

create a table. first define the structure, then i'll put in the actual data.

field - column, cell
record - row

an example of indexes in a database, stored as a tree structure. why would updates take longer now? why would lookup based on an indexed field be faster?


skip list data structure
http://en.wikipedia.org/wiki/Skip_list

Survey for the final

1 2 + 4 * 5 + 3 −

stack: 14

plan for today:
*1) show how to use a stack to evaluate a RPN expression

*2) go over three ways of reversing a singly linked list

*3) discussion of final
// fix TreeNode class so that there is one less in each array
int print_in_order(TreeNode current)
{
if (current == NULL) return 0;
int i;
int sum = 0;
for (i = 0; i < current.num_elements; i++)
{
sum += print_in_order(current.links[i];
// System.out.println(current.key_values[i] + " ");
}
sum += print_in_order(current.links[i];
return current.num_elements +sum ;
}




4) skip list

5) DFS

2)
void iterative_reverse()
{
 Node p, q, r;

 if(head == NULL)
  return;

 p = head;
 q = p.next;

 p.next = NULL;

 while (q != NULL)
 {
  r = q.next;
  q.next = p;
  p = q;
  q = r;
 }

 head = p;
}


void iterative_reverse_2()
{
 Stack s = new Stack();
 Node cur, prev;
 for (cur = head; cur != NULL; cur=cur.next)
 {
  s.push(cur);
 }
 head = s.pop();
 cur = head;
 while (! s.empty())
 {
  prev = cur;
  cur = s.pop();
  prev.next = cur;
 }
 cur.next = NULL;
 tail = cur;
}

public void reverse()
{
 reverse2(NULL, head);
 Node temp = head;
 head = tail;
 tail = temp;
}

private void reverse2(Node prev, Node current)
{
 if (current == NULL) return;
 reverse2(current, current.next);
 current.next = prev;

}

A sample final

https://docs.google.com/Doc?id=ajbqhgmq9qdz_356c8wv4tc6

Here are three reverse methods I came up with

Three methods:
1) simple iteration
void iterative_reverse()
{
Node p, q, r;

if(head == NULL)
return;

p = head;
q = p.next;

p.next = NULL;

while (q != NULL)
{
r = q.next;
q.next = p;
p = q;
q = r;
}

head = p;
}

2) Using a stack data structure
void iterative_reverse_2()
{
Stack s = new Stack();
Node cur, prev;
for (cur = head; cur != NULL; cur=cur.next)
{
s.push(cur);
}
head = s.pop();
cur = head;
while (! s.empty())
{
prev = cur;
cur = s.pop();
prev.next = cur;
}
cur.next = NULL;
tail = cur;
}

3) using the call stack
void reverse()
{
reverse2(NULL, head);
Node temp = head;
head = tail;
tail = temp;
}

void reverse2(Node prev, Node current)
{
if (current == NULL)
return;
reverse(current, current.next);
current.next = prev;
}

class Node
{
    char element;
    int next;
}

class SinglyLinkedList
{
    Node []space = new Node[100];
    int head = -1;
    int tail = -1;
    int size = 0;

    InsertBeginning(char val)
    {
        index = mymalloc(space);
        space[index].element = val;
        space[index].next = -1; // in general

        space[index].next = head;
        head = index;
    }
    etc., etc.
}

how do we allocate this memory from the array?

i gave an example, using a linked list, where each node had a start position and a length property.

but however you do it, malloc


summary of data structure: using xor, we can use a single link field to navigate a linked list in either direction. we need a history of the previous element, xor it with link field, that yields address of 'next' / 'prev' element.

Related to a midterm question. *Print* a singly linked list in reverse order.

main()
{
    print_reverse(head);
}
void print_reverse(Node *current)
{
    if (current == NULL)
        return;
    else
        print_reverse(current->next);
    cout << current->value << " ";
}

note to self: still need to see recursive reverse


"unrolled linked list"
http://en.wikipedia.org/wiki/Unrolled_linked_list

class Node
{
Node next;
int element;
}

class SinglyLinkedList
{
Node head, tail;
int size;
// methods go here
}

Node remove(int value)
{
Node cur = head;
while (cur != null && cur.next != null &&  cur.next.value != value)
cur = cur.next;

cur.next = cur.next.next;
}

void swap(Node x, Node y)
{
int temp;
temp = x.value;
x.value = y.value;
y.value = temp;
}

Date and Time for the Final

Monday, May 23, 8:30 PM- 10:30 PM

they had messed up AM and PM.

All the midterms are graded

However, there is a pile of graded midterms I still need to locate. So check BlackBoard, and you may see your grade there. If not, sorry -- I'll post them just as soon as I have opportunity to search.

The grades are out of 5. Multiply that by 20 to get your score. This is uncurved. Any curve, assuming there is one, will be applied at the end of the semester.

Open House Tomorrow - Master's Degrees in Information Systems and Web & Multimedia Design

Touro College 
Graduate School of Technology 
Master’s Programs in: 

• Information Systems
  Concentrations in:
  • Database Systems
  • Data Communications
  • Technology Leadership
• Web & Multimedia Design

OPEN HOUSE 
Wednesday, April 6 
6:30pm 
43 West 23rd St, 2nd fl. 
(bet. 5th & 6th Ave.) 
New York City 
Light dinner served 

Please RSVP 
http://www.touro.edu/gst/ 

212.463.0400 x 5462 
info.gst@touro.edu 

Why Choose the Graduate School of Technology? 
- 33 Credit Program 
- Weekend and Evening Classes 
- Scholarships Available 
- Job Placement Assistance 
- Retool Your Skills 
- Gain a Competitive Edge 
- Retrain for a Field in High Demand 
- Find New Career Opportunities 

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

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

HW Goal: eventually is a specific implementation of a Huffman encoding.

we got frequency array

#2.2 Priority Queue
push operation to put an element into the queue
pop operation to return the *smallest* element in the priority queue
internal representation, at this point, up to you. priority queue of ints

how to fill a byte array from a file
http://www.exampledepot.com/egs/java.io/file2bytearray.html

Do you speak Tajik?

If so, please contact me. This is for Natural Language Processing (computer science) work.

Thanks,
Josh

lecture

HW 2
2.1: Open a ASCII text file, count the frequency of each symbol. Store those frequencies in an array freq. Print out that array.

a cab am i.

a, b = b, a

def foo():
return 1, 3

def main():
x, y = foo()

System.nanoTime()

Read all about it at StackOverflow. I suppose that, if it works with enough accuracy, we could use it to time even much fewer pushes.

Homework #1.4

Modify your code from 1.3 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

A sample chart

based on one student's output. I used an X Y Scatter chart with smooth lines:

Another one, inserting even more data:

Generics in Java

Here are a few good websites which discuss them, especially as they interact with interfaces:

1. At Wikipedia
2. At Oracle
3. At Java2s

See also the comment thread on the previous post.

lecture #4

// array-based stack
class JArrayStack
{
int capacity = 100;
int a[] = new int [100];
int i = 0;

public void push(int x) { a[i++] = x; }
public void pop() { i++; }
public int top() { return a[i-1]; }
public boolean isFull() { return i == capacity; }
public boolean isEmpty() { return i == 0; }
public int size() { return i; }
}

int [] temp = new int [capacity * 2];
copy from a into temp using for loop or memcopy
a = temp
capacity *= 2

debugger
you shouldn't use venus if you have a bug in your program
printf debugging

*setting breakpoints
*stepping thru code
*using the watch window

hw 1.3:
Templatize it! Use generics.
also, modify your driver to insert varying sizes, 0, 100, 200, 300, 400, 500 all the way to 20000. Plot the results in Excel.
Tell me, is it O(1)? O(n)? O(n^2)?

My very simple Array-based Stack

// array-based stack
class JArrayStack
{
int capacity = 100;
int a[] = new int [100];
int i = 0;

public void push(int x) { a[i++] = x; }
public void pop() { i--; }
public int top() { return a[i-1]; }
public boolean isFull() { return i == capacity; }
public boolean isEmpty() { return i == 0; }
public int size() { return i; }
}

int [] temp = new int [capacity * 2];
copy from a into temp using for loop or memcopy
a = temp
capacity *= 2

some additional material from lecture #3

discussion of hw due tonight

void clear()
{
count = 0;
}
void pop()
{
count--;
}

discussion of next hw; due wed night
hw 1.2
instead of a max capacity of 100, it
will start at 100. if hits it, double it.
this, every time it hits the current capacity


Shape arr[] = new Shape[30];
i = 0;
arr[i] = new Rectangle(10, 10, 45, 56, "blue");
i++;

arr[i] = new Circle(40, 45, 56, "red");
i++;

for (int j = 0; j < i; j++)
arr[j].draw();

Stack<Shape> s = new Stack<Shape>();
s.push(new Rectangle(10, 10, 45, 56, "blue"));


exceptions

A clarification regarding the first stack homework

You don't want to just use the existing stack class, which Java already has. You want to write your OWN stack class, and then demonstrate it using your driver program.

Don't forget -- the first homework is due on Monday night!

Midnight, after class on Monday. So far, only two people have submitted their work. This is just homework 1.1, which is an array-based stack of fixed size.

Depth-first search vs. Breadth-first search

From xkcd:

lecture #2

http://www.cs.qc.edu/tutors.html

not yet updated

class A
{
public static void main(String args[])
{
Integer x = new Integer(6);
Integer y = 5;
int h[] = new int[1];
int j[] = new int[1];
swap(h, j);
swap(x, y);
System.out.println("" + x + " " + y);
}
// cannot do this; no pointers!
public static void swap(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
// alas, I am copying these references by value
public static void swap(Integer a, Integer b)
{
int temp;
temp = a;
a = new Integer(b.value);
b = new Integer(temp);
}
public static void swap(const int **a, const int **b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}

}

class MutableInteger
{
int value;
}

int retval;
retval = foo(x, y, &g);
if(retval == -1)
{

}
else if (retval == -2)
{


}
else if (retval < 0)
{


}
retval = bar(6, 4, k);
if(retval == -1)
{
cout << "file couldn't open";
exit(1);
}
else if (retval == -2)
{


}
else if (retval < 0)
{


}

foo(x, y, &g);
bar(6, 4, k);


try
{
foo(x, y, &g);
bar(6, 4, k);
}
catch(int i)
{
}
catch(double p)
{

}
catch(...)
{

}

Exception

class Shape
{
public:
virtual void draw() {}
}

class Triangle : public Shape
{
public:
draw() {}
}

class Square : public Shape
{
public:
draw() {}
}

foo(Shape *s)
{
s->draw();
}

main()
{
Shape *s[10];
s[0] = new Triangle();
s[1] = new Square();

}


class F
{
int y;
void foo() {}
public static void main(String args[])
{
F f = new F;
f.y;
f.foo();
}
}

First four lectures slides; homework

The first four PowerPoints have been added to Blackboard.

Also, homework assignment 1.1 added to Blackboard

lecture #1

Josh Waxman
Cs 313 - Data Structures using Java

qccs313.blogspot.com

Data Structure?
Array -- dense list

Stack: what methods?
push, pop, top, empty, full
interface to the stack

what guts?
array of size 100 of int

interface is a contract
JStack

interface Stack {....}

class JStack implents Stack
{
...
}

foo(Stack<T> s)
{
    s.pop();
}

Try this:
write a Java method swap that takes
in two ints (or, Integers) and swaps them.

void swap(int a, int b)
void swap(Integer a, Integer b)

one hint as to why Java stinks.

deprecate a feature


C++:
if (x = 56)
{

}


?: operator

if (x == 6)
    7;
else
    6;

z = (x==6 ? 7 : 6);

x==6? y = 7: p = 67;
switch case
switch(x)
{
    case 1:

        break;
    case 2:
        ...
        ...
        ...
    case 9:
        ...
        ...
        ...
        break;
    default:
        ...
        ...
        ...
}

auto fall-through disallowed

HW #1

Step 1: Make a stack of integers based a dense list with a maximum capacity of 100.

Step 2: Let it grow.

Step 3: Templatize it.

Step 4: Make it implement the appropriate interfaces.

Syllabus

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 for a