Back to lab index

15-111
Lab 10 - Collection Class Practice

Due: Monday, April 27th, 2009

Credits

We thank Prof. Pattis for this lab. This lab is an adaptation of a portion of his Lab #7 from 15-111 Fall 2005.

Overview

This programming assignment is designed to ensure that you know how to use combinations of collection classes to model and solve a wide variety of different programming problems. The kind of abstract thinking that goes into modeling solutions to these programming problems with collection classes is critical to your development as computer scientists. Collection classes are important and useful themselves, and they also rely on almost everything powerful that we have learned about Java: interfaces, classes in an inheritence hierarchy, casting, and general pupose iterators.

For problems in this suite, you must be familiar with the Java interfaces for Queue, Set, Map, List, Iterator, and Comparable. In addition, you must understand the use of the classes SimpleQueue, HashSet, HashMap, ArrayList, and LinkedList, which implement these collections. You must also understand the use of the static sort method defined in the Arrays and/or Collections classes, which use these interfaces, especially Comparable. If you need to use the Arrays class, you must be able to convert between collections and arrays. Finally, you should be familiar with the casting of generic (Object)/(Comparable) references, when necessary, and be able to read/use/write small classes with public instance variables that store compound data.

Reading the Input Data

You'll probably want to make use of the Scanner class and possibly the StringTokenizer. One possible strategy is to use the Scanner class to read in an entire -line- and then to parse this line using StirngTokenizer.

Structure of the Solution

This lab is designed to quickly give you a feel for the collection classes used as the will be on the final exam. It is not intended to be a "design of software" exercise. You can solve each problem within the static context of the main method, if you'd like.

Please create one class per question, naming the class as shown.

Problem #1: WordFrequency

Read a file of words, building a map (Map[String] -> Integer) from each word to its frequency (the number of times that it occurs in the file), and print the map. Then build a list (List[Map.Entry*]) consisting of the word/frequency pairs in the map. Sort and print this list twice: first with the word/frequency pairs ordered alphabetically; second with the word/frequency pairs ordered from highest to lowest frequency (words with equal frequency can appear in any order; the built-in sort method will take care of these details).

Sample Input:

  w x y z
  w x y
  w x w a c
  a b
  c
  

Sample Output:

  Enter name of file of words: input1.txt

  Map:
  {b=1, x=3, a=2, w=4, z=1, c=2, y=2}

  List (sorted alphabetically):
  [a=2, b=1, c=2, w=4, x=3, y=2, z=1]

  List (sorted by frequency):
  [w=4, x=3, a=2, c=2, y=2, b=1, z=1]
  

ReverseGraph

Read a file of pairs of node names representing a edges in a directed graph, building a map (Map[String] -> Set[String]) from the first node (source) to a set of the second nodes (destinations). Print all these edges, one source node per line (and all its edges), sorted alphabetically by source node. Build a second map (again Map[String] -> Set[String]) that represents a graph that is the reverse of the first one: if the first graph has and edge a->b then the second one has an edge b->a. Print all these edges, one source node per line (and all its edges), sorted alphabetically by source node. Note that there are multiple data files for this program.

Sample Input:

  a b    a c
  b d
  c e    c f
  d g
  e d
  f d    f g
  

Sample Output:

  Enter name of file with graph: graph1.txt

  Graph: source -> {destination} edges
  a -> [b, c]
  b -> [d]
  c -> [f, e]
  d -> [g]
  e -> [d]
  f -> [g, d]

  Reverse Graph: source -> {destination} edges
  b -> [a]
  c -> [a]
  d -> [b, f, e]
  e -> [c]
  f -> [c]
  g -> [f, d]
  

Sample Graphs

The sample input:

The reversed graph:

Reachable

Read a file of pairs of node names representing a edges in a directed graph, building a map (Map[String] -> Set[String]) from the first node (source) to a set of the second nodes (destinations). Print all these edges, one source node per line (and all its edges), sorted alphabetically by source node. Prompt the user for the name of a node. Build a set (Set[String]) into which you we will put all nodes reachable from the first, by searching outward from a user-supplied node. Print all the reachable nodes. Note that there are multiple data files for this program; some of them describe circular graphs, which must be correctly processed (avoiding infinite loops in your algorithms).

Sample Input:

  
  a b    a c
  b d
  c e    c f
  d g
  e d
  f d    f g
  

Sample Output:

  Enter name of file with graph: graph1.txt

  Graph: source -> {destination} edges
  a -> [b, c]
  b -> [d]
  c -> [f, e]
  d -> [g]
  e -> [d]
  f -> [g, d]

  Enter node to start from: c
  Reachable: [g, f, e, d, c]