Sunday, January 27, 2008

Project 1

Due Date: Thursday, 14 February

Individual project


Project Description

The starting point for this project is the generic java.util.Map interface. Your job is as follows:
  • (10%) create a Java project in Eclipse
  • (15%) develop a comprehensive JUnit 4 test case for the Map interface
  • (5%) using inheritance, create one specialized version of the test case for each of the following implementations:
    • java.util.HashMap
    • java.util.TreeMap
    • java.util.LinkedHashMap
  • (40%) based on another specialized version of the test case, develop your own implementation, ChainedHashMap, using a fixed-size hash table with chaining
  • (10%) develop a performance evaluation class for the Map interface
  • (10%) apply the the performance evaluation to all four implementations (see details below)
  • (10%) provide sufficient documentation in the form of inline and Javadoc comments

Additional requirements

  • Make sure your project has separate src and test folders and refers to JUnit 4 as a library.
  • Implement the Map interface as a hash table with chaining using java.util.LinkedList.
  • Ignore the three view methods (entrySet, keySet, and values) in the Map interface for the purpose of this project, including testing. Your implementation should throw a java.lang.UnsupportedOperationException in the body of these methods.
  • For each of the remaining 11 interface methods, you need at least two test methods. For example, test isEmpty on an empty and a non-empty map.
  • Unlike the existing Java map implementations, your implementation must provide a constructor that allows you to pass the hash function as an argument when an instance your class is created. The constructor should also take the table size as another argument.
  • Represent hash functions as objects with the following generic interface:
interface ToInteger<T> {
int apply(T arg);
  • Implement the following hash functions for integer keys:
    • last two digits
    • last three digits
    • digit sum (e.g. digitSum.apply(1234) returns 10)
    • modulo some positive number
  • Use System.currentTimeMillis() to calculate running times.
  • Measure the performance as follows:
    • create another JUnit 4 test case for this purpose
    • using the @BeforeClass and @AfterClass annotations, create the following "permanent" fixtures:
      • one (long) LinkedList of random keys to insert (partially) into the map
      • one (not so long) LinkedList of random keys to query the map for
    • write an auxiliary method void doMeasure(String label, Map map, int n, int r) that inserts a specific number, n, of keys (using some dummy value to map to) from the first list, measures the performance for a given large number, r, of retrievals from the second list, and prints the result using the given label
    • for each configuration of map implementation, table size (in the case of your implementation), and hash function (in the case of your implementation), write a @Test method that configures the map instance and performs the measurements for the various numbers of insertions
  • Specifically, measure the following configurations:
    • java.util.HashMap
    • java.util.TreeMap
    • java.util.LinkedHashMap
    • ChainedHashMap, last two digits, size 100
    • ChainedHashMap, last three digits, size 1000
    • ChainedHashMap, digit sum, size 100
    • ChainedHashMap, modulo 101, size 101
    • ChainedHashMap, modulo 1009, size 1009
    • ChainedHashMap, modulo 10007, size 10007
    • ChainedHashMap, modulo 100003, size 100003
  • and the following number of insertions:
    • 100
    • 1000
    • 10000
    • 100000
    • ...
  • choose the number of retrievals, r, globally such that your smallest measurements are at least 100 milliseconds
  • choose the maximum number of insertions such that the longest running times stay around a minute or below


Wednesday, January 23, 2008

Project 0

Due Date: Sunday, 27 January

Mailing List Subscription

The first part of this project requires you to subscribe to the mailing list for this course. Keep in mind that you are responsible for being familiar with any information exchanged on this mailing list.

Linux Account Verification

The second part of this project requires you to verify that your departmental Linux account works. (If you are a new student, you should have received email about your account.) This account is separate from your Loyola account and will allow you to use the lab machines. If you have any problems with your Linux account, please contact our lab manager right away.

Software Installation/Verification

The third part of this project requires you to install and try out the course software. You are encouraged to discuss any issues you encounter in the mailing list for this course.

Verification of Access to Course Examples

Following these instructions, access the repository for the course examples. Then check out (download) the HelloWorld module and run the unit test contained therein.

Creation of Personal CVS Repository

Log into your Linux account and create your repository following the first step in these instructions. We will use Eclipse for the other steps as described in this tutorial.

Group Formation

The last part of this project requires you to form a project work group with exactly one other fellow student. That is, the groups should be of size two. The groups should stay the same throughout the semester. Once you have formed your group, please send me email containing a list of both group members.
Certain projects assigned in this course might be designated as group projects, for which there will be one submission and consequently one grade per group.


No submission is required for this project.

Wednesday, January 16, 2008

Software required for this course

The following software has been installed for you in the CS labs. All of it is either open source or otherwise freely available and runs on the three major platforms (Windows, Linux, Mac OS X).

You are encouraged to install this software on your home and/or work computer as well by following these instructions:

  • If you do not yet have a Java SE Development Kit (JDK) 5.0 or later on your system, you should download the JDK 6 (first item on the page).
  • Download and install the Eclipse Europa package Eclipse IDE for Java Developers from here.
Alternatively, if you are already comfortable with another IDE, such as NetBeans or IntelliJ IDEA, you may continue using that IDE. (A classroom license key for IntelliJ IDEA is available from the Blackboard area for this course).

If you are using Windows, you will also need a Secure Shell (ssh) client for access to your Linux account, for example:

Tentative list of course topics

These topics are listed here in no particular order. The weekly schedule organizes these topics chronologically.

Data Structures

  • Linear vs. nonlinear
  • Indexing vs. nonindexing
  • Position vs. value-oriented

Advanced Java

  • Interfaces
  • Inheritance
  • Object as superclass
  • Annotations
  • Exceptions
  • Enumerations
  • Generics
  • Collections
  • Boxing/Unboxing
  • Array Objects

Object Modeling

  • UML
  • Use Cases and Activity Diagrams
  • Class Diagrams
  • Archetypes
  • Interaction Diagrams


  • Design by Contract
  • Interfaces
  • Refactoring and Generalization
  • Patterns
    • Core Patterns
    • Adapter
    • Decorator
    • Composite
    • Strategy
    • Iterator
    • Abstract Factory
    • Visitor
    • Java's Event Listener
    • Observer/Obervable

Agile Development Process

  • Evolutionary design
  • Test-driven development
    • Unit testing
    • Mock objects
  • Continuous refactoring
  • Continuous integration
  • Automatic Building
    • Managed Ant Projects in Eclipse
    • Managed Maven Projects in Eclipse
    • JAR files and Build Products


  • Eclipse
  • Subversion
  • JUnit
  • JMock or EasyMock
  • EclEmma
  • Ant
  • Java Web Start and JNLP


  • Object Pooling
  • Garbage Collection
  • Performance Profiling (NetBeans)

Tentative weekly course schedule

Week 1

  • overview
  • design with interfaces
  • Java collections
  • test-driven development
  • JUnit
  • reading: online

Week 2

  • update on required software
  • test-driven development
  • JUnit
  • reading: online

Week 3

  • review of methods inherited from Object
  • review of data structures including hashing
  • Java collections
  • Java genericity
  • project discussion
  • reading: Effective Java, items 7-11, 28, 30, 34, 38; online

Week 4

  • quiz 1 (after the lecture)
  • design with composition
  • sorted collections
  • Strategy pattern
  • project discussion
  • reading: Effective Java, items 1-6, 23-27; online

Week 5

  • discussion of quiz 1
  • design patterns
  • Strategy pattern
  • Iterator pattern
  • reading: Effective Java, items 31, 33; online

Week 6

  • quiz 2 (before the lecture)
  • Java enumerations
  • project discussion
  • reading: Effective Java, items 10, 29, 32, 37, 38; online

Week 7

  • quiz 2 discussion
  • project discussion
  • Java inheritance
  • requirements analysis
  • modeling: use cases, class diagrams
  • reading: Effective Java, items 12-18; online

Week 8

  • quiz 3 (after the lecture)
  • project discussion
  • requirements analysis
  • modeling: class diagrams
  • reading: online

Week 9

  • quiz 3 discussion
  • project discussion
  • Java exceptions
  • Composite and Decorator patterns
  • reading: Effective Java, items 39-47; online

Week 10

  • project discussion
  • modeling tools: ArgoUML
  • Composite and Decorator patterns
  • mutability and cloning
  • modeling: use cases, class diagrams, interaction diagrams
  • reading: Effective Java, item 10; online

Course objectives

The primary objective of this course is to take your software development abilities to the next level by building upon your knowledge of data structures. Specifically, you will learn to design and implement more complex programs using good software engineering practices, including:
  • designing with interfaces and composition
  • design patterns
  • refactoring
  • test-driven development