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