Assignment 2

Task 1 (5 points)

Counting Words The following program can be used to count the words of a text CountWords.java. Download it, compile it, and test it. To test it, here is a book The War in the Air (By H.G. Wells) as a text file. To test it you can do as follows:

java CountWords < warair.txt

1.1 Modify the program so that it also reports the number of different words.

hint: You will need to store the words in a datastructure that allows you to decide whether a word has occured before in the text or not! Think carefully what datastructure you need and find it in the java.util package.

1.2 Modify the program so that it also reports the number of occurrences of each word.

hint: You will need to use a datastructure that allows you to associate with each word that occurrs in the text a number that you can increase on each occurrence of the word. Such a datastructure is called a Map and is described as an interface in the package java.util.

A map (also called a dictionary) is very much like a set, but it can store pairs, where the first element is considered as a key by which to search in the map. In your program you will need an instance of a map where the keys are strings and the values associated with each key are integers. In the package java.util you find the class HashMap that implements a map using a hashtable.
 

Task 2 (5 points)

graphs

the graph

java Graph lectureGraph

2.1 Modify main so that it also outputs the number of edges.

2.2 Add a method that outputs a line for each vertex with all its adjacent vertices. You might want to have a look to the methods that HashMap offers to go through all the elements in the map! (see the java documentation linked from the homepage of the course!)

2.3 The outdegree of a node is the number of edges that leave the node. The indegree of a node is the number of edges that come into the node. Write methods that calculate the outdegree and the indegree of every node. Modify main so that these values are output for every node. For indegree you will need to add a field to the class Vertex that you can increment on detecting a new incomming edge.

2.4 Calculating indegrees is connected to the method Topsort. You can read in the book (in the chapter on graphs, in the second edition section 14.5.1). It is enough that you explain in words how indegrees is connected, but an implementation in code is of course great (not required).