Part I
Queue
1 CircularQueue
1.1 Dynamic array (10 marks)
The class CircularQueue implements the interface Queue using two techniques presented in class, circular and dynamic arrays. The first technique allows reusing the empty cells at the beginning of the array once the queue has moved to the end of the array.
The second technique allows a data structure (here a queue) to increase its physical size according to the needs of the application. Modify the implementation of the class CircularQueue so that its array increases by a fixed increment when needed.
* Declare a constant specifying the default increment of the queue (25);
* Add a constructor with the following signature CircularQueue(int minCapacity). The parameter specifies the minimum capacity of the queue, the value must be greater than or equals to zero;
* Add a constructor with the following signature CircularQueue(int minCapacity, int increment). The first parameter specifies the minimum capacity of the queue, the value must be greater than or equals to zero. The second parameter specifies the fixed number of cells that will be added when increasing the size of the array, the value must be greater than zero;
* Make all the necessary changes to ensure that the capacity of the queue increases when needed;
* Add a method void trimToSize() that reduces the physical size of the queue to the maximum of minCapacity and the logical size.
Files
* CircularQueue.java
* Queue.java
* EmptyQueueException.java
Part II
Queue-based algorithms: Web Crawler
Web crawlers (sometimes called Web robots, Web spiders or Wanderers) are programs that automatically traverse the Internet to gather information. Search engines, such as Google, build up their content using such programs; Googlebot, in the case of Google. Simply, a Web crawler starts at an arbitrary Web page, stores all the links that are found in that page, then starts again from a different location, i.e. takes one link from the collection of saved links, gets the content of that page, extracts and stores all the links, and starts over from a different location. In doing so, its collection of links grows and eventually all the available Web pages are visited. In the case of a Web crawler for a search engine, when a page is visited, information about the content of the page is also stored, for example, to build up an index associating words such as “assignment”, “deadline” and “crawlers” with the link that corresponds to this Web page.
Documents on the Web are generally stored in a format called HTML (HyperText Markup Language). Links between the pages are also represented in a standard way. A Uniform Resource Locator (URL) is a standard way to represent the address of a Web page on Internet and this is used to create links between Web pages.
For this assignment, you will be implementing a Web crawler to determine if a path exists in between two Web pages; let’s define a path as an ordered sequence of URLs such that each Web page of the sequence has a link (URL) to the next Web page of the sequence. Your implementation will use the breadth-first search algorithm presented in class and therefore will also find the shortest path!
HTML
The class HTML represents a Web document. Its constructor takes as input the url of the page to be represented in your program.
HTML document;
document = new HTML( "http://www.site.uottawa.ca/~turcotte" );
An HTML document has a method hasMoreURLs() as well as a method nextURL(). The method hasMoreURLs returns true if the page has more links that have not yet been returned by the method nextURL. Each call to the method nextURL returns the next URL found in this page. The method nextURL throws an exception of type NoSuchElementException if there are no next link. Therefore, each call must be preceded by a call to hasMoreURLs. The typical usage is as follows.
HTML document;
document = new HTML( "http://www.site.uottawa.ca/~turcotte" );
int count=0;
while ( document.hasMoreURLs() ) {
String url = document.nextURL();
count++;
}
System.out.println( "This document has " + count + " links." );
2 Path (15 marks)
The breadth-first search algorithm, implemented by the class Crawler, incrementally builds all the valid paths, from the shortest to the longest paths. Each path represents a partial solution to our problem (finding a valid path from page A to page B). An object of the class Path is used to represent a partial solution. Write an implementation of the class Path according to the following specification.
* Singly linked elements are used to store the URLs (strings) of this Path;
* Implement a constructor with the following signature: public Path(Path partial, String url). The constructor inserts all the URLs from partial into this Path in the same order. Then, inserts url at the end of the path. The value of the parameter partial can be null, but not that of url. The partial solution passed as a parameter must remain unchanged;
* public int size(): returns the number of URLs in this path;
* public boolean contains(String url): the method returns true if this path contains an occurrence of the specified url, and false otherwise;
* public String getURL(int pos): returns the URL stored at the specified position of this path;
* public String getLastURL(): returns the last URL of this path;
* public String toString(): returns a String representation of this path with one URL per line (see below).
The following example shows the intended use of this class. An initial solution, designated by a, is created that contains one URL. A second solution is created from a, that extends the path by one URL, then a third solution is created from b, always extending the path of an existing solution by one URL.
Path a = new Path( null, "http://www.w3.org"'>http://www.w3.org" );
Path b = new Path( a, "http://www.sun.com"'>http://www.sun.com" );
Path c = new Path( b, "http://java.sun.com"'>http://java.sun.com" );
System.out.println( c.toString() );
the above statement would print this,
and
System.out.println( c.getLastURL() );
would print this,
3 Crawler
The class Crawler contains three static methods that are used to find a path from a Web page A to a Web page B; it is also possible that no such path exists. The method solve implements the breadth-first search algorithm presented in class.
3.1 private static boolean isValid( String url ) (5 marks)
The method isValid returns true if url is a well formed URL designating an existing and readable Web page, and false otherwise. In order to implement this method, you can use the fact that the constructor of an HTML object i) throws an exception, of type MalformedURLException, if the url is not well formed, and ii) throws an exception, of type IOException, if the content of the page cannot be successfully read.
3.2 private static Path solve( String a, String b ) (10 marks)
You must implement a breadth-first search algorithm for finding a path from a Web page A to a Web page B. The breadth-first search uses a Queue data structure (LinkedQueue).
To briefly summarize what was said in class, “breadth-first search” uses a queue to generate all the sequences in increasing order of length. Each element of the queue is a partial solution (an object of the class Path). The algorithm initializes the queue to contain a partial solution that consists of the Web page A, and repeatedly does the following:
* dequeues a partial solution off the queue;
* extends the partial solution by one URL in all possible ways, and;
* enqueues each of the “valid” extensions.
Your method should return as soon as a solution is found, and it should not put into the queue paths that are not “valid”. A path is not valid if it contains a non-valid URL or it contains cycles (a path that visits the same URL more than once. Hint: this is what contains is for). You can test that a URL is valid by calling the method isValid. If you know that a path is valid you can check if it is a solution by comparing its last URL to the URL of the Web page B.
public static void main( String[] args )
The main method prints the following message unless there are exactly two arguments on the command line, and exists immediately.
Usage: java Crawler source destination
If the command line has two arguments, those arguments are used for calling the method solve. The main method prints the path if it exists, and “no path” if no such path was found.
Test cases
You will find several examples at the following URL:
* http://www.site.uottawa.ca/~turcotte/teaching/iti-1121/assignments/04/html/
Here is an example of a run.
> java Crawler http://www.site.uottawa.ca/~turcotte/teaching/iti-1121/assignments/04/html/1/00.html
http://www.site.uottawa.ca/~turcotte/teaching/iti-1121/assignments/04/html/1/22.html
Solution:
http://www.site.uottawa.ca/~turcotte/teaching/iti-1121/assignments/04/html/1/00.html ->
http://www.site.uottawa.ca/~turcotte/teaching/iti-1121/assignments/04/html/1/10.html ->
http://www.site.uottawa.ca/~turcotte/teaching/iti-1121/assignments/04/html/1/20.html ->
http://www.site.uottawa.ca/~turcotte/teaching/iti-1121/assignments/04/html/1/21.html ->
http://www.site.uottawa.ca/~turcotte/teaching/iti-1121/assignments/04/html/1/22.html
Note. The two URLs should be typed on the same line. Example 1 has a set of Web pages that represent the following Maze.
PIC
the page 00.html represents the upper left corner, it has two links, one to the page 01.html and the other to the page 10.html. As you can see, the name of the page represents the coordinates of the cell within the labyrinth.
PIC
Example 2 also represents a maze, but it contains invalid URLs (represented by the dashed circles). For each example, you can generate several test cases by selecting different starting points (Web pages). You can experiment with these examples using your Web browser. Example 3 represents a maze that has pages on three Web servers:
> java Crawler http://www.site.uottawa.ca/~turcotte/teaching/iti-1121/assignments/04/html/3/alpha.html
Solution:
http://www.site.uottawa.ca/~turcotte/teaching/iti-1121/assignments/04/html/3/alpha.html ->
http://bio.site.uottawa.ca/~turcotte/teaching/iti-1121/assignments/04/html/3/bravo.html ->
http://www.site.uottawa.ca/~turcotte/teaching/iti-1121/assignments/04/html/3/charlie.html ->
Example 4 contains cycles, i.e. certain paths visit the same page more than one.
PIC
> java Crawler http://www.site.uottawa.ca/~turcotte/teaching/iti-1121/assignments/04/html/4/00.html
http://www.site.uottawa.ca/~turcotte/teaching/iti-1121/assignments/04/html/4/12.html
Solution:
http://www.site.uottawa.ca/~turcotte/teaching/iti-1121/assignments/04/html/4/00.html ->
http://www.site.uottawa.ca/~turcotte/teaching/iti-1121/assignments/04/html/4/10.html ->
http://www.site.uottawa.ca/~turcotte/teaching/iti-1121/assignments/04/html/4/11.html ->
http://www.site.uottawa.ca/~turcotte/teaching/iti-1121/assignments/04/html/4/12.html
Resources
* www.w3.org/ — World Wide Web Consortium (W3C) develops Web based technologies;
* www.w3.org/MarkUp/ — information about HTML;
* http://www.w3.org/Addressing/ — information about URL.
Files
* Crawler.java
* HTML.java
* Path.java
* LinkedQueue.java
* Queue.java
* TestPath.java
Part III
Iterator
4 hasPrevious() (2 marks)
In the class LinkedList, implement the instance method hasPrevious() of the iterator. It returns true if the iteration has a previous element, and false otherwise. In other words, it returns true if a call to the method previous would succeed, and false otherwise.
Note: the class LinkedList uses doubly linked nodes to store the elements of the list. The list starts off with a dummy node and the list is circular in both directions. This implementation technique, seen in class, facilitates the implementation of the methods since it eliminates many special cases.
5 previous() (3 marks)
In the class LinkedList, implement the instance method previous() of the iterator. It returns the previous element of the iteration. This method can be called repeatedly to iterate backwards, or interleaved with calls to next() to go back and forth. A call to next() followed by a call to previous() will return the same element. As the other methods of the iterator, the method previous() must be implemented using the technique called “fail-fast” presented in class. Briefly, the technique “fail-fast” uses a modification counter, placed the the header of the list and each iterator, to detect situations where the list has been modified by an iterator, other than the current one.
The following JUnit test cases can be used to validate the methods hasPrevious and previous: TestIteratorPrevious.java. Do not assume that the tests are exhausitive. In particular, do not assume that a method that passes these tests gets a perfect score.
6 remove() (10 marks)
In the class LinkedList, implement the instance method remove of the iterator. It removes from the list the last element that was returned by next(). As the other methods of the iterator, the method remove() must be implemented using the technique called “fail-fast” presented in class. As well, the method throws an IllegalStateException upon a failure to remove an element (for instance, calling the method remove() when the iterator is positioned before the start of the list).
The following JUnit test cases can be used to validate the method remove: TestIteratorRemove.java. Do not assume that the tests are exhausitive. In particular, do not assume that a method that passes these tests gets a perfect score.
Files
* Iterator.java
* LinkedList.java
* TestIteratorPrevious.java
* TestIteratorRemove.java
Part IV
Recursion
7 take (10 marks)
In the class SinglyLinkedList, write a recursive (instance) method that returns a new linked list consisting of the first n elements of this list. This instance must remain unchanged. The method public LinkedList<E> take( int n ) must be implemented following the technique presented in class for implementing recursive methods inside the class, i.e. where a recursive method is made of a public part and a private recursive part. The public method initiates the first call to the recursive method.
The following JUnit test cases can be used to validate the method take: TestTake.java. Do not assume that the tests are exhausitive. In particular, do not assume that a method that passes these tests gets a perfect score.
8 findMax (10 marks)
Create a new class called A4Q8, and implement the method findMax. The method returns the largest value of the Sequence. Its implementation is recusive. The class Sequence is a linked list with additional methods to make it possible to write recursive list processing methods outside of the class. Here are the characteristics of the class Sequence.
* The elements of the Sequence are Comparable;
* The methods of the class Sequence include.
o boolean isEmpty(); returns true if and only if this list is empty;
o E head(); returns a reference to the object stored in the first node of this list;
o Sequence<E> split(); returns the tail of this sequence, this sequence now contains a single element;
o void join( Sequence<E> other ); appends other at the end of this sequence, other is now empty.
The following JUnit test cases can be used to validate the method findMax: TestA4Q8.java. Do not assume that the tests are exhausitive. In particular, do not assume that a method that passes these tests gets a perfect score. In order to use the above test, you will have to be careful to ensure that the method names and signatures are exactly as specified above.
Files
* SinglyLinkedList.java
* TestTake.java
* Sequence.java
* A4Q8.java
* TestA4Q8.java
Part V
Binary search trees
The implementation of the class BinarySearchTree for this assignment differs slightly than that presented in class. Herein, BinarySearchTree implements the interface Associative.
An associative structure defines associations between keys and values. It provides operations for defining an association (update) and retrieving the value associated with a key (get).
The interface Associative has two type parameters. The first type parameter (K) specifies the type of the key objects. Keys must be Comparable one with another. The second type parameter (V) specifies the type of the value objects.
* V get( K key): returns the value associated with the key, or null if the key is not found;
* V update(K key, V value): the method is used to define a new association (key, value), or to update the value associated with an existing key. Further information will be presented in class;
* LinkedList<L> keys(): returns all the keys in order, as defined by the method compareTo of the key objects;
* LinkedList<L> values(): returns all the values in the order defined by the method compareTo of the key objects!
9 keys() and values() (15 marks)
In the class BinarySearchTree implement the methods keys() and values().
The following JUnit test cases can be used to validate the methods keys and values: TestKeysAndValues.java. Do not assume that the tests are exhausitive. In particular, do not assume that a method that passes these tests gets a perfect score.
10 getPathLength (10 marks)
Let the path length of a node be the number of links starting from the root that must be followed to reach that node. The path length of the root is 0. Implement the method int getPathLength( K key ) that returns the path length of the node where key is found or -1 is key if not found in that tree.
The following JUnit test cases can be used to validate the method getPathLength: TestGetPathLength.java. Do not assume that the tests are exhausitive. In particular, do not assume that a method that passes these tests gets a perfect score.
Files
* Associative.java
* BinarySearchTree.java
* TestGetPathLength.java
* TestKeysAndValues.java
Rules and regulation
You preferably do the assignment in teams of two, but you can also do the assignment individually. Follow all the directives available on the assignment directives web page. Assignments must be submitted through the on-line submission system maestro.
Files
You must hand in the following files.
* README.txt
* StudentInfo.java
* TestAll.java
* CircularQueue.java
* EmptyQueueException.java
* Crawler.java
* HTML.java
* Path.java
* LinkedQueue.java
* Queue.java
* TestPath.java
* Iterator.java
* LinkedList.java
* TestIteratorPrevious.java
* TestIteratorRemove.java
* SinglyLinkedList.java
* TestTake.java
* Sequence.java
* A4Q8.java
* TestA4Q8.java
* Associative.java
* BinarySearchTree.java
* TestGetPathLength.java
* TestKeysAndValues.java
All the given files a4.jar.
