Computer Science 15-111 (Sections A & B), Spring 2007

Class Notes: 11-Apr-2007

Logistics:

1. Quiz 7 is Today! J
Covers Trees, Binary Trees, Binary Search Trees, Expression Trees, Maps, HashMaps, TreeMaps, Sets, HashSets, TreeSets,

2. Test 2 is Wednesday April 18^th (9 days from today). It is comprehensive.

3. Reading:
Wikipedia page on Heaps
Note: you are responsible for insert and remove operations, not for increaseKey or merge, nor for heap variants.

4. Important Notes on hw8:

1. You can write "disjoint" using the following simpler signature if you prefer:

public static <T> boolean disjoint(Collection<T> c1, Collection<T> c2);

This requires the collections to be of the same parameterized type, and gives you that type "T" to work with in your body.

2. If you must create an array, it cannot be a parameterized array of unknown type ("generic array creation"), so you may either:

a) create a parameterized arraylist, or

b) create an unparameterized Object array, Object[], and turn off checking just for that method by placing the following just before the method (rather than before the entire class):

@SuppressWarnings({"unchecked"})

3. Finally, if you just cannot get parameterized types working, you may do the assignment using unchecked types (no parameterized types) for a penalty of 1 point per nonparameterized method (with an overall max penalty of 5 points). If you elect this option, please be sure to note that you did so in your file header, and preface your entire class with:

@SuppressWarnings({"unchecked"})

Thus, for example, you can take a 1-point penalty and write "disjoint" with the following simpler signature:

public static boolean disjoint(Collection c1, Collection c2);

Topics:

1. Heap Applications

a. HeapSort Using a java.util.PriorityQueue
HeapSortWithPriorityQueue.java

b. HeapSort using a custom Heap
InPlaceHeapSort.java

c. Best-First Search
BestFirstSearch.java

2. Quiz…