- 12/02/10 - Class on 12/07/10
- Last day of classes.
**The final will be on Wednesday, December 15 from 3:30 to 5:30 in Tuttleman 303AB**. Remember that you can bring a one page, double faced, cheat sheet - Returned and discussed the 12th quiz
- Going over various quizzes
- Review
- 12/01/10 - Class on 12/02/10
- Returned and discussed the twelveth quiz
- Basic definitions for graphs
- Representing a graph using adjacency lists: depth first traversal, breadth first traversal, Breadth first spanning tree
- Some algorithms on graphs, mostly represented by adjacency matrices. Note the use of assertions in testing. JUnit comes handy in such situations.
- The hierarchy of graph types from textbook
- Class evaluation
- pgs 547-572
- 11/23/10 - Class on 11/30/10
- Returned and discussed the eleventh quiz
- Listing files - Anything you can do at the command line, should be doable by program - and vice versa. But efficiency may differ.
- Conditional Compilation: if B is a static final boolean variable then
`if (B) S;`

will generate code for S only if B is true - Twelveth quiz
- pgs 471-472, 541-547
- 11/20/10 - Class on 11/23/10
- Returned and discussed the tenth quiz
- Going again over the partition code of Quicksort
- In the case of MergeSort we saw that it was possible to come up with a non-recursive solution that did not need stack emulation. That iterative solution was twice as fast as the recursive solution. In the case of QuickSort the non-recursive solution requires stack emulation and it is slightly slower than the recursive solution.
- Why is Quicksort, on average, even faster than the non-recursive MergeSort?
- A tree with n nodes can have height n thus searches, insertions, deletions can take O(n) time. But if the tree is "balanced" so that all leaves are at about the same height, then the longest path is ~lg(n) and operations become O(lg(n)). That is the reason why Chapter 9 is dedicated to how to create and keep trees balanced. We do not deal with it in this course. That will be a topic studied in CIS3223.
- N-ary trees: representation as a binary tree; representation with n successors
- In n-ary trees we can still talk of preorder and postorder traversal, but not of inorder
- In n-ary trees we can still talk of depth-first and breadth-first
- Eleventh and Final Homework
- Eleventh quiz
- 11/17/10 - Class on 11/18/10
- For the keys of hash tables, if we have k1.equals(k2) then we must have hash(k1) == hash(k2)
- Of course, when we studied Comparable we should have mentioned that if a.equals(b) should be true if and only iff a.compareTo(b) == 0. Not satisfying this condition can lead to unexpected results.
- Heap Sort: the Textbook version. It sorts a 2000000 element array in 7.1 seconds
- Merge Sort: the Textbook recursive version and my non-recursive version. Sorting a 2000000 element array the recursive version takes 5.7 seconds, the non-recursive one 2.8 seconds. The Arrays.sort routine in the Java API does the sorting in 2.4 seconds....
- Quick Sort: the Textbook version. It sorts 2000000 element array in 2.6 second. Note that quicksort has a bad worst case performance, but on average it is good. In fact it was the best of the handcrafted sort routines we tried. But the Java API version is still the best.
- Tenth quiz
- pgs 441-460
- 11/10/10 - Class on 11/16/10
- Returned and discussed the nineth quiz
- Hashing and collisions
- Open addressing, linear probing[(h(k) + c1*i) % m], quadratic probing [(h(k) + c1*i + c2*i*i) % m], double hashing [(h1(k) + i*h2(k)) % m]
- Hash tables == associative arrays, which are built-in types in many modern programming languages
- Problems with deletions, big problems with resizing
- Why on average we find keys in a hash table in constant time
- Chaining
- The Set and Map interfaces
- The classes HashMap, HashTable, HashSet
- Bloom Filters
- pgs 384-395, 361-372
- 11/10/10 - Class on 11/11/10
- Visit by Avi Friedman: Discussion
- 11/04/10 - Class on 11/09/10
- Heapsort
- Huffman Codes
- Introduction to hashing and hash tables
- Using the Unix word dictionary to see how well the Java builtin method hashCode works.
- Measuring time:

long before = System.nanoTime(); -- what we measure -- long after = System.nanoTime();

after-before gives us the elapsed time in nanoseconds - Tenth Homework
- Nineth quiz
- pgs 372-382
- 11/02/10 - Class on 11/04/10
- Returned and discussed the eight quiz
- More on heaps and priority queues
- Encoding the paths of binary trees
- pgs 332-352
- 10/28/10 - Class on 11/02/10
- Returned and discussed second midterm
- Heaps and priority queues
- Nineth Homework
- Eight quiz
- 10/26/10 - Class on 10/28/10
- Second Midterm
- 10/21/10 - Class on 10/26/10
- Height of a binary tree
- Height of a general tree represented as a binary tree
- Definition of Binary Search Trees
- Implementation of binary search trees
- Looking at properties of random binary search trees
- pgs 315-332
- Eight Homework
- Seventh quiz
**On Thursday Second Midterm**- 10/19/10 - Class on 10/21/10
- Returned and discussed the sixth quiz
- Various recursive algorithms: printing leaves, finding maximum, summing values, ..
- Depth-First vs Breadth-First traversal of a tree
- General trees
- 10/14/10 - Class on 10/19/10
- Implementing an iterator with remove for single linked lists
- Factory methods: creating objects with methods instead of constructors. Using interfaces instead of classes to avoid commitment to early class implementation.
- "I think I shall never see a poem lovely as a tree" -- Indeed, CS loves trees
- Definitions of trees
- Full, Perfect, Complete trees
- Traversal of a tree, preorder, inorder, postorder
- BinaryTree as an iterable collection
- A binary tree class
- Another implementation for binary trees and the JUnit test file created in NetBeans for it
- pgs 295-315
- Sixth quiz
- 10/12/10 - Class on 10/14/10
- Returned and discussed fifth quiz
- More discussion of homework and discrete event simulation
- Priority queues implemented as single linked lists
- We have completed chapters 1 through 5 of the textbook. We will keep on reviewing this material the rest of the semester
- Command Line Parameters - Redirection '<' and '>'
- We can read from an URL. For example
URL url = new URL(args[0]); Scanner in = new Scanner(url.openStream()); while (in.hasNext()) { String token = in.next(); System.out.println(token); // or whatever you want to do to tokens }

- We have seen a permutation program. We can look at all the calls to the function printPermute.
- Pages 295-306
- 10/07/10 - Class on 10/12/10
- Infix, prefix, postfix expressions
- Evaluating a postfix expression
- Infix to Postfix
- Stacks can be implemented using single linked lists, using arrays, using arraylists. In all cases the push, pop, peek, empty operations take constant time
- Can you write a clone operation for stacks that works no matter the implementation of the stack?
- Stacks implement the Collection interface. Can you write an iterator when using the list implementation? when using the array implementation?
- Discrete Event Simulation: Seventh Homework
- Fifth quiz
- 10/05/10 - Class on 10/07/10
- Implementing queues with an array [circular buffer]
- Unbounded queue as a "unbounded" circular buffer
- Stacks 5A
- Pages 149-194
- 09/30/10 - Class on 10/05/10
- Returned and discussed the
**first Midterm** - Reading and writing from binary and object files. Read on this topic on the CIS1068 textbook [or search the web!]. A trivial example
- Starting with Queues. Uses of queues. Basic functionality
- Implementing queues with single linked lists
- Pages 193-242
- No quiz
- Sixth homework
- 09/28/10 - Class on 09/30/10
**First Midterm**- 09/23/10 - Class on 09/28/10
- Adding to a single linked list
- Reversing a single linked list
- Using single linked lists to implement priority queues
- Questions about LinkedList and some answers
- Back to recursion. Permutations. Auxiliary methods, tail-recursion. In time we will see mutual recursion
- Fifth Homework
- Fourth quiz
- On Thursday we have the first Midterm: collections, recursion, generics, graphics
- 09/21/10 - Class on 09/23/10
- Returned and discussed the third quiz
- Complexity of Tower of Hanoi program
- The Koch curve fractal - Turtle Graphics
- Sun's tutorial on creating a GUI using Swing in NetBeans
- Be particularly conscious of Iterable, Iterator, ListIterator
- Appendix B, pages 685-692, 719-727
- 09/17/10 - Class on 09/21/10
- In a listener, identify the source of the event: getSource, getActionCommand
- The Model-View-Controller Architecture
- Big-O Notation: say that the complexity of an algorithm on n elements is T(n), then if there is a function f(n) and there are constants c and m such that for all n>m T(n)<=c*f(n), we say that the Big-O complexity of the algorithm is f(n).
- The Single Linked list
- A minimal single linked list with iterator
- Declaring a generic method
- The class LinkedList and the interface ListIterator
- Starting on Recursion. Factorial. Tower of Hanoi
- Pages 88-99, 112-124, 243-266
- Fourth Homework
- Third quiz
- 09/15/10 - Class on 09/16/10
- Returned and discussed the second quiz
- A minimalist's UML notation
- Building the UML diagram for the CircleDemo
- The Collection framework: The Iterable, Iterator, Collection interfaces
- Implementation of ArrayLists - Amortized Analysis
- Big-O Notation: say that the complexity of an algorithm on n elements is T(n), then if there is a function f(n) and there are constants c and m such that for all n>m T(n)<=c*f(n), we say that the Big-O complexity of the algorithm is f(n).
- Pages 99-112
- 09/09/10 - Class on 09/14/10
- An example using both an action and a mouse listener
- An example with the Graphics object: Drawing ellipses
- Using the Graphics and Graphics2D classes - check the Java API to see what is in them
- See the Sanders-VanDam code on Blackboard, in particular Chapter 7 and 8. The BouncingBall example and the Fish example are interesting.
- A drawing package from Princeton with the code and its use in the Bouncing Ball example.
- A bare version of the bouncing ball example, and a better Bouncing Ball program
- A minimal snowman
- A moving snowman similar to the moving bouncing ball.
- Generic vs raw types. Beware: At runtime exist only raw types. Also, though Integer is a subclass of Number, ArrayList<Integer> is not a subclass of ArrayList<Number>
- More about generics: wildcards and bounded wildcards. An example.
- Third Homework
- Second quiz
- 09/08/10 - Class on 09/09/10
- Returnded and discussed first quiz
- Dr.Lakaemper ButtonDemo, BearButtonTest (minor edits)
- A button that beeps, then seen as an applet and its code
- Keeping time with a Timer
- Layouts: BorderLayout, GridLayout
- The CircleDemo
- A grid of buttons and a grid of labels counting hits on the buttons
- An example of jumping array of buttons
- 09/02/10 - Class on 09/07/10
- Review: Visibility, scope, access control
- Review: Interfaces - Comparable, Iterable, Iterator
- Review: Shallow and deep copy and comparison
- GUIs and Event Oriented programming
- Some uses of JOptionPane
- Hello World with a JFrame
- Events and GUIs: See Dr Lakaemper's slides
- Appendix C: Pages 695-718
- Homework 2
- First Quiz
- 09/01/10 - Class on 09/02/10
- Review: Compile tyme and run time types: polymorphism
- Review: Abstract classes
- Review: Exceptions - checked, unchecked
- Review: Files and I/O
- Read Chapter 1 and Appendix A
- 08/09/10 - Class on 08/31/10
- We go over the syllabus in its various aspects, objectives of the course, people involved, text book, grading, etc.
- We review and extend concepts from CIS1068: object-oriented programming, classes, inheritance.
- Our first lab is Thursday September 2, from 12:30 to 2:20 in CC 200. You do not need a separate account to use our computers. Your Temple Id and password should work. We will see how to use the NetBeans Interactive Development Environment (IDE).
- We will have weekly quizzes starting next Tuesday.
- An example with instance data members
- An example with static data members
- Read Chapter 1, pages 1-34
- Homework 1
- 08/09/10 - Before Class on 08/31/2010
- This is hard to do, since probably you will not look here until after the first day of class. But if you can, try to review what you learned in the previous programming classes. Start reading Chapter 1 of the textbook.