In this module we take a look at Java's Collections library discussing sets, maps, queues, and other commonly used data structures. We discuss our previous implementations, and look at the JDK's implementations.

We introduce big-O notation, and evaluate some of our previous programs in terms of their runtime performance. We then use JUnit tests to validate our results from our runtime performance analysis.

  1. Given a custom Map implementation, refactor the code to use the JDK standard Map.
  2. Given a custom Queue implementation, refactor the code to use the JDK standard Queue.
  3. Given a custom Set implementation, refactor the code to use the JDK standard Set.
  4. Given a Collection, use the JDK Comparator to sort the elements.
  5. Given a sorting specification, order a collection of data by using the Java standard library.
  6. Given a Java class, write down the time complexity for a specific method using big-O notation.
  7. Given a Java class, write down the time complexity for a specific method using big-Omega notation.
  8. Given the complexity analysis of a method, interpret the performance.
  9. Given a Java class with a method whose implementation uses recursion, write down the recurrence relation.
  10. Given a set of Java classes, evaluate their performance by writing performance tests.
  11. Given a Java class, use JUnit to write performance tests.
  12. Given a set of Java classes with performance tests, plot their performance results.
  • DUE DATE: Thursday 14th of July @ 12:00pm (NOON)

Submission Criteria

Problems and/or problem parts marked with the symbol ‡ are to be attempted by teams of 2 people only.

Repository Contents

Your repositories must contain only the following

  1. pom.xml file and
  2. src folder with appropriate sub-folders with your code and test code only.

Code Criteria

  1. Your solution for each problem should be in its own package. The package names should follow this naming convention edu.neu.ccs.cs5004.assignmentN.problemM where you replace N with the assignment number and M with the problem number, e.g., all your code for problem 1 for this assignment must be in a package named edu.neu.ccs.cs5004.assignment7.problem1.
  2. Your project should successfully build using maven generating all the default reports.
  3. Your Javadoc generation should complete with no errors or warnings.
  4. Your Checkstyle report must have no violations.
  5. Your JaCoCo report must indicate 75% code coverage per package for "Branches" and "Instructions" or more.
  6. Your FindBugs report must have no violations (except for violations categorized as PERFORMANCE or SECURITY, you can ignore those).
  7. Your PMD report should have no violations.

Iterators

For this question you are allowed to reuse code from previous assignment. If you do reuse your code from previous assignments make sure you update your old solutions to address any issues pointed out by the graders. You can also design and implement a new solution from scratch.

From assignment 5, problem 3, you designed an integer binary search tree (ibst). Develop the following features/operations for your ibst.

  1. Develop an iterator that iterates over your ibst using a pre-order tree walk.
  2. ‡ Develop an iterator that iterates over your ibst using a post-order tree walk.
  3. ‡ Develop an iterator that iterates over your ibst using a in-order tree walk.
  4. A map-like operation over your ibst. Provide at least 3 example uses of your map-like operation.
  5. A fold-like operation over you ibst. Provide at least 3 example uses of your fold-like operation.

Iterable and for-each

For this question you are allowed to reuse code from previous assignment. If you do reuse your code from previous assignments make sure you update your old solutions to address any issues pointed out by the graders. You can also design and implement a new solution from scratch.

Design implementations of Iterable interface for the following

  1. Your implementation of Set from assignment 4, problem 1. There is no specific order of iteration over a set, select an order and implement that.
  2. ‡ Your implementation of Queue from assignment 4, problem 2. Your iteration should follow the FIFO policy of the queue.
  3. Your implementation of PriorityQueue from assignment 5, problem 3. Your iteration should mimic the priority ordering inside your queue.

Graphs

A gaming company is researching a new game that allows players to design their own maps. A map is made up of villages and roads. A village is represented on a map with a unique name--no two villages on the same map have the same name. A road on a map connects two villages together and has one direction--roads are like one-way streets.

The company would like to check maps before they are accepted in the game. To that end they are trying to figure out which criteria they should impose on maps generated by gamers. Here are some of the criteria that they are thinking of exploring.

  • The roads in the map should not form a cycle.
  • Gamers should be able to define a path to designate how to move from one city to another by using the roads in the map. A path can be provided in two different ways:
    1. a path is a sequence of cities, or,
    2. a path is a sequence of roads.
    Given a path and a map we should be able to check if the path is valid for the given map. A valid path on a map means that we can follow roads in their designated direction to reach the last village on the path.
  • A terminal village is a village that has roads incoming roads but no outgoing roads.
  • A started village is a village that has outgoing roads but no incoming roads.
  • A dead village is a village that has no incoming roads and no outgoing roads.

You are asked to design two different solutions of capturing maps with villages and roads. For each design solution the game company would like you to provide the following operations.

  1. an operation that checks if there are any cycles in the map
  2. an operation that checks if there are any starter villages in the map
  3. an operation that checks if there are any terminal villages in the map
  4. an operation that checks if there are any dead villages in the map
  5. given a path check if that path is valid for this map
  6. ‡ an operation that transposes the map.

We did cover 2 alternative ways to represent graphs in class. You are allowed to use one of those if you prefer as one of your solutions, or, create 2 new ones. Make sure that your 2 designs vary in their approach of capturing information significantly.