Pass by Value or Reference
• Link 1
• Link 2
• Link 3

• Review Topics: Matt: Heaps
• Tree Traversal: Peter
• Classes/interfaces(abstract): Richies
• iterators,listerators and how to loop over various data structures: Andrew
• Grid World Solutions Parts 1-5 from the college board

• READ: bit string flicking is on the next Computer Science Contest: Here's a good page that serves as an introduction
• if you're interested in bitwise operators (bit shifting), here's a well known article (at least in gaming comunity) of how bitwise operators work. The author used these techniques in games and was asked to explain his code, hence the web page.
• Collision detection in Flash games discussed in terms of Big-Oh
• cross site scripting attacks: be careful making your php aps!
  • thought might be interesting after our php/mysql project last year

• All non-linear data structures: Maps, Trees, sets, (hash and binary versions), heaps . There will be an open response on one of the data structures (link to Matt's Heap PowerPoint)
• Big-oh of all sorting algorithms (here's the link to Peter's Powerpoint)
  • Big-Oh of various topics (most of which you need to know)

Grid World
• Grid World install, download
  • Download Grid World Code
• 1) Write a class called printOutBug2 that
  • extends Bug
  • prints out all empty Locations in the grid
• 2) Write a class called BugCategorizer that extends Bug
  • the constructor should take a a String Parameter that represents one of the following classes: Rock,Critter, or Bug
  • add a method called int categorize() that is called by the act() method
    • based on the constructor's parameter , categorize() should return count up the number of instances of a given class
    • For instance, if the red bug in the picture below was a BugCategorizer('Rock') then its categorize() would return 1;
    
• 3) Write a class called ShyBug that extends BoxBug. This class should
  • determine how many other Actors(critters or bugs ) are within 3 spaces of itself.
    • if there is n or more Actors (critters or bugs ) within 3 spaces the Shy bug's color darkens, and it does not move at all.
    • otherwise, the shy Bug's color lightens and the bug behaves like a normal bug.
    • The constructor should take a paramater that represents N
    • ie ShyBug(5) means that if there are at least 5 critters/actors within 3 spaces, the ShyBug darkens .
• 4) Do the SparseBoundedGrid assignment from part 5

Everybody has a review topic that they will present to the class. You should provide a powerpoint covering the main points of each topic, as discussed in our class. We will have a test mid-march after the projects have been presented and we have reviewed.

• Inheritance, Abstract Classes and Interfaces: Richie
• HashSet, HashTable, HashCode: Andrew
• All the sorts:Peter
  • Big-Oh (best,worst, average cases)
  • When you should use varous sorts. i.e. what conditions lead to the best case and or worst cases of the various sorts.
• BinarySearchTrees, : Matt

Heaps and HeapSorrt
• Add a removeRoot method to the HeapOfCharacters in Listing 10.7 and use it to implement a heapsort. Write a driver program testing your sort.

Two Dimensional Arrays

•   
  public class DoubleArrays {
  
  	
  	public static void main(String[] args){
  		int[][] table = new int[3][5];
  		
  		System.out.println(table[0].length) ;
  		
  		System.out.println(table.length) ;
  			
  		for(int row= 0; row < table.length; row++)
  			for(int col=0; col < table[row].length ; col++)
  				table[row][col] = row*10 +col;
  		
  		for(int row= 0; row < table.length; row++){
  			for(int col=0; col < table[row].length ; col++) 
  				System.out.print(table[row][col] +"\t");
  				System.out.println();
  				 
  			}
  
  		
  		
  		
  	}
  	
  	
  }
  
    

• Implement a SeatingChart program that a teacher could use to assign student names to a two dimensional grid, Each spot in the grid represents where a student sits.
  • You should create a two dimensional array to keep track of where students sit in the classroom
    • the class should be able to
      • get a student's name based on the location in the two dimensional array
      • calculate the sum of students in seats (there could be empty seats)
      • calculate the sum of extra seats (there might be more seats than studetns
      • switch two students's locations
• Project 2) Create a MazeGenerator Class that creates Maze objects
  • the Maze class should be implemented using a two dimensional array and should use an X to symbolize a wall and a minus sign to symbolize a clear passage. Below is an example of what a maze object would like, graphically. Every maze should have a starting and ending point (feel free to implement starting and ending points any way that you want-- I used a red S and a red F to symbolize start and finish)

    S	-	x	-	-
    -	x	-	x	x
    -	x	-	x	-
    -	x	-	x	-
    -	-	-	-	F

  • Create a MazeSolver class that
    • calculates how many moves could be used to get to the end.
    • returns a String represent the path taken by the solution (in the maze above it would be "down,down,down,down,right,right,right"
  • To get full credit (an A) on this assignment, implement a method called shortestRoute() that returns a String representing the shortest route between the start and finish. This method should be able to work for complicated mazes that have multiple possible routes.

Trees Sets and Tree Maps
• 1) Use a TreeSet<Integer> with the following methods
  • void add(int x)
  • void remove(int x)
  • void print() to print all elements in the set
  • boolean find(int x) to test whether x is present
  • IntSet union(IntSet other)
  • IntSet intersection(IntSet other)
    • to computer the union and intersection of two sets.
• 2) Implement a BinaryTreeSet class that uses a TreeSet to store its elements. You will need to implement an interator that iterates through the nodes n sorted order. This iterators is somewhat complex because sometimes you need to backtrack. You can either add a reference to the parent node in each Node object, or have your iterator store a stack of the visited nodes.

• Binary Search Trees

• In-order Traversal: Print (or traverse) left side of tree, print/traverse node, print traverse right side
• Pre-order Traversal: Print node, left side, then right side
• Post-order Traversal: Print left side, print right side, then node
  • Great web page on Binary Search
  • a follow page with a great explanation of removing nodes from a binary search tree
  • Exercise 1)In the BinarySearchTree class, modify the remove method so that a node with two children is replaced by the largest child of the left subtree.
  • project 1) Design an IntTree class that stores only integers, not objects. Support the same methods as teh BinarySearchTree class from the book
  • project 2) Write a methodof the BinarySearchTree class
    • Comparable smallest()
    That returns the smallest element of a tree.
  • project 3) Add a method to the BinarSearchTree class printLeaves(). This should only print out...the leaves!
  • Project 4) Change the BinarSearchTree.print method to print the tree as a tree shape. You can print the tree sideways. Extra credit if you instead display the tree with the root node centered on the top.
  • project 5) Suppose an interface Visitor has a signle method void visit(Object obj). Supply
    • void inOrder(Visitor v)
    • void preOrder(Visitor v)
    • void postOrder(visitor v)
    to the BinarySearchTree class . These methods should visit the tree nodes in the specified traversal order and apply the visit method to the data of the visited node.
  • Project 6) Use the prior project to compute the average value of the elements in a binary search tree filled with Integer objects.

Maps
• Run the code on this page to see a HashMap in action
• Project 1) Implement a Map to store information about countries and their capitol cities. Use the name of the country as the key. Write a program that demonstrates the usage of this map. Include one method that prints out all pairs of countries and capitols.
• Project 2) Sometimes it is necessary to store more than one object at a particular key. Consider a mailbox. Items in the mailbox are in no particular order. Implement a Mail object that is able to store the name of the sender as well as the receiver of the mail. A map can be used by a post office to track the mail that comes through the system. Each mailbox has a unique key (its postal address). However, each must store multiple pieces of mail. Implement a program uses a map with postal addresses for keys, that stores a set of mail current in the mailbox. Use the Java.util.Hashmap implement of a map. Below is quick reminder of how to declare a hashmap.
  • HashMap<String,String> s = new HashMap();
s.put("the key","a value ")
• Project 3) Write a program that keeps a map in which both keys and values are strings- the names of students and their course grades. Prompt the user of the program to add or remove students, to modify grades, or to print all grades. The printout should be printed out as follows
  • Karl: A
  • Jen: B+
  • Tim: C-
• Project 4) Reimplement the prior project so that the keys of the map are objects of class Student. A student should have a first name, a last name, and a unique integer ID. For grade changes and removals, lookup should be by ID. the printout should be sorted by last name. If two students have the same last name, then use the first name as a tie breaker. If the first are are also identical, then use the integer ID. Hint: use two maps.

• download Source code
• run HashSetDemo
• Programming Exercise 1) Add a debug method to the HashSet implemention from 16.3 that prints the nonempty buckets of the hash table. Run the test program at the end of Section 16.3. Call the debug method after all additions and removals and verify that Figure 6 accurately represents the state of the hash table.
• Programming Exercise 2) The java.util.HashSet class implements a hash table for the actual elements in the set. Write a program that implement a HashSet for a GuestList program. This program should have a list of Guests and should be able to determine if a given name is or is not on the list. You should also be able to add or remove guests from the list.
• Programmign Exercise 3) Implement the sieve of Eratosthenes: a method for computing prime number, known to the ancient Greeks. Choose an N. This method will compute all prime numbers up to n. First insert all numbers from 2 to n into a HashSet. Then erase all multiples of 2(except 2): that is 4,6,8,10,12,...Erase all multiples of 3...Go up to the square root of n. Then print the set.
  • Set declaration: Set<Integer> s = new HashSet<Integer>();
• Programming Exercise 4) The java.util.HashMap class implements a hash table for the keys, HashMap<k,v>. Make up a program with at least two classes that should be store in a HashMap
• Programming Exercise 5) : Implement a HashMap<k,v> to create a a user login system. Usernames should be unique, passwords need not be. Add functionality that many web based programs do by producing a sha1 hash of the username. Use the sha1 class here .

• Stacks
• queues
• priorityqueue
• linkedLists (yes, you should expect a question or two on old topics)
• Big-Oh

• Queues
  • PriorityQueue
• Stacks
  • Below is a (mostly) functional Stack implementation of a Palindrome Tester. Note that the code only uses one stack. This code works perfectly well for all words with an even number of letters. Your job is to make it work for all words. Code for the class.

− Array
• Arrays in Java
• Practice AP Exam questions on Arrays

− Object Oriented Programming (OOP)
• Introduction to Creating Objects using BlueJ
• Writing Classes Tutorial
• Your First BlueJ Project
• Your First Objects
• Constructors
• Polymorphism
• abstract classes
• how-to-and-when-to-cast
OOP on the AP exam
• overloading, overriding, polmorphism

• Iterators(You'll need to use iteratos for the folder tree program)
• Recursively process all files and folders on hard drive
• Pascal's Triangle Recursion Project

• Linked Lists
• Programming Assignment involving a priority queue
• Demonstration of a Stack
• Stack Assignment

(Some of these are under construction)
• Sets, HashSets and TreeSets