Credits

We thank Prof. Pattis for this lab. This lab is an adaptation of a portion of his Lab #7 from 15-200 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.

I/O Specification

In solving these problems, please make use of the introExam.ExamIO package. To get this, bounce off of the intro group's Web site and download a sample exam. Final Exam Page This will give you each line represented as an iterator of tokens. From there, make use of StringTokenizer to get at each individual token. This works just like the sample exam question -- and ultimately, the final exam.

Structure of the Solution

This exam 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).

• Create the map while processing the input file using the standard call to ExamIO.readFile() and the StringTokenizer class.
• When printing the map (and later the list, twice) use a single line of Java code each time, calling the standard toString method on the collection being printed (either implicitly or explicitly).
• Build the list using the Map.Entry objects stored in the map.
• To sort the list, either use two anonymous classes (or write two small named classes) specifying the ways to order the Map.Entry objects stored in the list.

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.

• Create the map while processing the input file using the standard call to ExamIO.readLine() and the StringTokenizer class.
• Write a method to sort/print the map; it will be called for the original map and the map for the reversed graph. When printing the set of destination nodes, use a single line of Java code, calling the standard toString method on the set being printed (either implicitly or explicitly).
• To reverse the graph iterate through each of its source nodes; for each source node, iterate through each of its destination nodes; for each source->destination edge in the original graph, put the edge destination->source in the map storing the reverse graph.

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).

• Create the map while processing the input file using the standard call to readAllTokens and the StringTokenizer class.
• When printing the set of destination nodes, use a single line of Java code, calling the standard toString method on the set being printed (either implicitly or explicitly).
• To search the graph, build a set (of reachable nodes) and a queue (of nodes to search from), initializing the later with the user-supplied node. While the queue still has nodes, remove one, put it into the set, and for all its destination nodes THAT ARE NOT ALREADY in the set, put them in the queue.
• When the queue finally becomes empty (can you prove this always happens -there is no infinite looping), print all nodes in the reachable set.

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]