2008/05/07 – CS235

Prayer, spiritual thought

Announcements

•	Grades posted on:  http://byuspring.blackboard.com
•	Note from TAs:
o	About extra credit and grading, I assume we are following the previous semester's guidelines: 103 for 3 or more days early, 102 for 2 days, 101 for one day, 100 on the day that it is due, 80 for up to one week late, 60 for up to 2 weeks late, 0 after that. Also, announce that we do not use timestamps. The projects must be submitted and the passed off before the last TA leaves on the day that it is due.

Items to correct and clarify

•	Java: final (unchangeable), C++: const (Sterling was right)
•	When is the best time to find a bug in your code?
o	Development,  testing, or production sage
o	Before you compile or at runtime?

•	What is the purpose of a Generic?  
•	GenericsDemo.java
o	what types of objects can be added  to Collection c?
o	show:  old school method
o	show:  new school method (using generics)
o	Using Generics makes errors previously reported at runtime at compile-time
o	Generic classes are converted by the compiler to non-generic classes by a process known as type erasure

•	Show Comparable Examples 
•	Factory method – a method that creates new concrete instances but returns them using a reference to an abstract class

Interactive

Pass-out paper with problems, break into 4+ groups
Present solutions, teach concepts

Collection
Interfaces and Implementations

Sets – A set is a collection that cannot contain duplicates

The Java platform contains three general-purpose Set implementations: HashSet, TreeSet, and LinkedHashSet. 

HashSet, which stores its elements in a hash table, is the best-performing implementation; however it makes no guarantees concerning the order of iteration. 
TreeSet, which stores its elements in a red-black tree, orders its elements based on their values; it is substantially slower than HashSet. LinkedHashSet, which is implemented as a hash table with a linked list running through it, orders its elements based on the order in which they were inserted into the set (insertion-order). 
LinkedHashSet spares its clients from the unspecified, generally chaotic ordering provided by HashSet at a cost that is only slightly higher.

SetDemo.java – create set from list using the Collection accepting constructor
SetOperations.java - 
FindDups.java – 

Lists

Group 1

1. Consider the four core interfaces, Set, List, Queue, and Map. For each of the following four assignments, specify which of the four core interfaces is best suited, and explain how to use it to implement the assignment.

•	Whimsical Toys Inc (WTI) needs to record the names of all its employees. Every month, an employee will be chosen at random from these records to receive a free toy.
•	WTI has decided that each new product will be named after an employee — but only first names will be used, and each name will be used only once. Prepare a list of unique first names.
•	WTI decides that it only wants to use the most popular names for its toys. Count the number of employees who have each first name.
•	WTI acquires season tickets for the local lacrosse team, to be shared by employees. Create a waiting list for this popular sport.

2. What are the differences between ArrayList and LinkedList?

3. If you need a Set implementation that provides value-ordered iteration, which class should you use?

4. You plan to write a program that uses several basic collection interfaces: Set, List, Queue, and Map. You're not sure which implementations will work best, so you decide to use general-purpose implementations until you get a better idea how your program will work in the real world. Which implementations are these?

Group 2

1. Consider the four core interfaces, Set, List, Queue, and Map. For each of the following four assignments, specify which of the four core interfaces is best suited, and explain how to use it to implement the assignment.

•	Whimsical Toys Inc (WTI) needs to record the names of all its employees. Every month, an employee will be chosen at random from these records to receive a free toy.
•	WTI has decided that each new product will be named after an employee — but only first names will be used, and each name will be used only once. Prepare a list of unique first names.
•	WTI decides that it only wants to use the most popular names for its toys. Count the number of employees who have each first name.
•	WTI acquires season tickets for the local lacrosse team, to be shared by employees. Create a waiting list for this popular sport.

2.  What are differences between HashSet and TreeSet? 

3. If you frequently need to insert data in various places throughout a list which implementation should you use? 

4. Write a method (call it ListTrim) that takes a List<String> and applies String.trim to each element. To do this, you'll need to pick one of the three iteration idioms (i.e., enhanced for loop, Iterator, or ListIterator). Two of these will not give the result you want, so be sure to write a program that demonstrates that the method actually works!

Group 3

1. Consider the four core interfaces, Set, List, Queue, and Map. For each of the following four assignments, specify which of the four core interfaces is best suited, and explain how to use it to implement the assignment.

•	Whimsical Toys Inc (WTI) needs to record the names of all its employees. Every month, an employee will be chosen at random from these records to receive a free toy.
•	WTI has decided that each new product will be named after an employee — but only first names will be used, and each name will be used only once. Prepare a list of unique first names.
•	WTI decides that it only wants to use the most popular names for its toys. Count the number of employees who have each first name.
•	WTI acquires season tickets for the local lacrosse team, to be shared by employees. Create a waiting list for this popular sport.

2. What are the differences between Iterator and ListIterator?

3. When would you use a TreeSet instead of a HashSet? 

4. Take the FindDups example (provided) and modify it to use a SortedSet instead of a Set. Specify a Comparator so that case is ignored when sorting and identifying set elements.

Group 4

1. Consider the four core interfaces, Set, List, Queue, and Map. For each of the following four assignments, specify which of the four core interfaces is best suited, and explain how to use it to implement the assignment.

•	Whimsical Toys Inc (WTI) needs to record the names of all its employees. Every month, an employee will be chosen at random from these records to receive a free toy.
•	WTI has decided that each new product will be named after an employee — but only first names will be used, and each name will be used only once. Prepare a list of unique first names.
•	WTI decides that it only wants to use the most popular names for its toys. Count the number of employees who have each first name.
•	WTI acquires season tickets for the local lacrosse team, to be shared by employees. Create a waiting list for this popular sport.

2.  What are three different ways to traverse a list?

3.  When would you extend AbstractList rather than extending ArrayList?

4. Write a program that reads a text file, specified by the first command line argument, into a List. The program should then print random lines from the file, the number of lines printed to be specified by the second command line argument. Write the program so that a correctly-sized collection is allocated all at once, instead of being gradually expanded as the file is read in. Hint: To determine the number of lines in the file, use java.io.File.length to obtain the size of the file, then divide by an assumed size of an average line.