Recitation Material

November 18, 2005

Problem:

This recitation is a big one (you have two classes for it). It'll be done in four parts. We've done the first part for you :-)

Part 1: Building a Tree
This part will involve modifying the code from the previous recitation (which parses multiple domain names) to build a tree out of the domain names. The input to the program will consist of multiple strings, each of which is a domain name (just as in the previous recitation).

Tree Construction Steps
Given a parsed domain name object and a tree, reverse the components of the domain name (eg. cs.unc.edu becomes edu.unc.cs). Compare the first domain name component (reversed) with the children of the root node. If there is a match, move down to that node and compare the next domain name component with all children of the matched node and so on... If there is no match at a node, then create a new node at that level and continue.

Here's a picture of a tree that must be generated if the following domain names are given: cs.unc.edu, med.unc.edu, yahoo.com, google.com, maps.google.com, cs.unc.edu

Note: From the tree construction steps, it can easily be seen that if a domain name is entered twice, no action is taken the second time (eg. cs.unc.edu in the example above)

Here's the code where you'll be starting from. This is the solution for Part 1.
ADomainToken.java
AToken.java
ADotToken.java

TokenEnumeration.java
ATokenEnumeration.java

DomainName.java
Parser.java
ParserReturnObject.java
ParserException.java
ScannerException.java
ParserDriver.java
TreeNodeInterface.java
TreeNode.java

Part 2: Recursively Getting Descendants
To the tree node class, add a function numDescendantsComputed() that returns the number of nodes in the subtree rooted at that particular node. This function must be recursive (it should call this function on all its children).

Part 3: Updating through Observers
In Part 2, to get the number of children for a node, the function numDescendantsComputed() had to be called every time. Now, have a variable numChildren at each node of the tree, which stores the number of children at that node. Define a new function numDescendantsStored which returns this value. Every time a new node is added to the tree, an update function for its parent is called (let's say updateDescendants), which will update the number of children the node has. This update has to be propagated up the tree, to ensure that all nodes in the tree have the latest information. Note that the update function is called through the Observer/Observable pattern (as discussed in the class). Thus every parent is an observer of all its immediate children.

Part 4: Assertions (Using Visitor Patterns)
In this part you have to use assertions (as discussed in class) to "assert" that the values you computed in part 2 and 3, that is the results of numDescendantsComputed() and numDescendantsStored(), are indeed the same. After the tree is constructed, encode a universal quantified assertion to assert that this condition is true for every node in the tree.
Note that you need to use the assertion library. Linky

November 04 and November 11, 2005

Problem:

This recitation focuses on recursion. So you'll be writing a recursive parser, and you'll do it in two steps. Part 1 has to be completed on 4th November, while Part 2 can be turned in by the end of next recitation (11th November). For simplicity, we will consider ONLY domain-names as input strings.

Part 1
Given below is an interative solution to parse through a domain name (of the form "maps.yahoo.com"). Change the iterative parsing method (iterativeParseSimple) so that it parses through the input string recursively. Here's the signature of the recursive parse method that you must use:

private static DomainName recursiveParseSimple(ATokenEnumeration, DomainName) throws ParserException, ScannerException

Files for the iterative solution:
ADomainToken.java
AToken.java
ADotToken.java

TokenEnumeration.java
ATokenEnumeration.java

DomainName.java
Parser.java - This is file which has the iterative parsing method (you need to change this method)

ParserException.java
ScannerException.java
ParserDriver.java

Note than we have added a 'ADotToken' class and the enumerator (scanner) now returns the dot(.) tokens also. Although this is not required for this part, the parser in part 2 will need to differentiate between strings separated by spaces (different domain names), and strings separated by a dot (same domain name). Here are all the files for the iterative solution:

Part 2
In Part 2, write a recursive parser to parse multiple domain names on a single line, i.e. for input of the form "maps.yahoo.com maps.google.com" -- NOTE this is a SINGLE argument, and not multiple arguments as in previous recitations. Since this is non-trivial to implement, you can finish it in the next recitation.

If you think about it, you'll find that one of the conditions in the parser above is when to start parsing a new domain name. For this and other boundary cases, you'll need to pass both the current list of parsed domain names as well as the look-ahead token. For this we provide a composite structure as following:

ParserReturnInterface.java - An interface for the composite object
ParserReturnObject.java - The actual composite object

The code will have a single level of recursion. The main function will call a function, which recursively parses through domain names. Note that individual domain names are parsed iteratively. There is a sublte point though. The recursive function needs to know when to stop parsing a domain name. When the parser sees two non-dot tokens consecutively it knows that the current domain name is over. It'll then return the domain name scanned and also the next token that it has already eaten up. Here is the method signature of this recursive parsing routine:

	private static ParserReturnObject recursiveParse(ATokenEnumeration, ParserReturnObject) throws ParserException, ScannerException

Note: The remaining files remain the same as they were for Part 1. Moreover, DomainName is a list of lists , and not just a simple list as in the previous recitation.

October 28, 2005

Problem:

In this recitation, you'll be adding exceptions (throwing and handling) to the code written in the previous recitation (You're free to start from our code for the previous recitation).
There can be two types of errors in input strings: Scanning errors (note that the type of a token is determined by its first character) and Parsing errors. In the previous recitation, in case of an error, the program printed a message and quit. Now, you must define two checked exception classes (say ParsingException and ScanningException).
In case of an error, you must throw an exception of the appropriate type. The actual exception handling (try catch) must be done in the main function. The above implementation can be performed in two stages:

First implement exception handling for parsing errors. This is easy as only one level of exception propagation is required.
Then implement exception handling for scanning errors. In this case two levels of exception propagation is required.

Sample Inputs and corresponding outputs:
Input: maps.433.com
Output: "Exception: Parsing Error at token 433"
Input: maps.4me.com
Output: "Exception: Scanning Error at token m"
Note: You may quit the program on catching the first exception.

Solutions:
Starting from the code for the last recitaion, two new exception classes have been defined and three other files (Parser, Enumerator and the ParserDriver) have been changed. Here are the changed/new files:
Parser.java - Modified parser, which throws exceptions
ParserDriver.java - Contains the main function (which handles the exceptions)
ATokenEnumeration.java - Modified enumerator, which throws exceptions
ParserException.java - Exception class for a parser exception
ScannerException.java - Exception class for a scanner exception

October 14, 2005

Problem:

This recitation involves parsing. The program will be given a series of IP addresses (which is of the form <number>.<number>.<number>.<number>) and domain names as arguments. You need to parse each of these and find the maximum number of components that match with the hardcoded values in the main program ('hardCodedDomain' and 'hardCodedIPAddress'). The matching is to be performed from left to right (i.e find the longest common prefix). Create a separate class for the parser and use the keyword 'instanceof' to identify the type of the token returned by the scanner.

You are given a scanner class ATokenEnumeration.java (with interface) TokenEnumeration.java and the classes for the token hierarchy: AnIPToken.java and ADomainToken.java are subclasses of AToken.java. Here's a skeleton of the main file: ParserDriver.java.

Note: Your program must also perform error checking. For example: 'maps.23.com' is an incorrect input. So is '34.google.243.212'. The decision on the type of input (whether it's an IP address or a domain name) is made by the first token of the input.

Sample Arguments :


	"maps.google" "216.239.34.232" "12.23.45.56" "cs.unc.edu" "maps.yahoo.com" "216.12.67.78"

Screenshot:
Sample Output

Sample output with error

Solutions:
Here are all the files required. The names are self explanatory.

AToken.java - Top level token type
AnIPToken.java - Implements AToken
ADomainToken.java - Implements AToken

DomainName.java - Object to store a domain name
IPAddress.java - Object to store IP Address

Parser.java - Has the parser
ParserDriver.java - Has the main function

TokenEnumeration.java - Scanner interface
ATokenEnumeration.java - Actual scanner

October 7, 2005

Those of you that haven't finished Part 2 of the recitation on September 30th, please do that first. The others can do the following problem.

Problem:
For this recitation, extend the Decimal class to create a function with the following signature:

public Decimal addTo(Decimal)

(i.e. it allows us to add two decimal numbers by passing a Decimal object to another Decimal object)

We have provided the following helper functions:

public double getDoubleValue(): Get the double value, given a Decimal object
public Decimal(double): A constructor which creates a Decimal object, given a double value

Here are the updated Decimal object files:
ADecimal.java
Decimal.java
DecimalDriver.java

September 30, 2005

Problem:
For this week's recitation, there are two parts. Complete part one this Friday and part two by next Friday.

Part 1:

Use the general scanner (from last week's solution) and extend it to be a date scanner. The scanner should accept exactly 3 tokens, separated by the character '/'. If there are any other tokens in the input, the program should quit with an error message. Here are some correct and incorrect inputs:

Correct Inputs and Corresponding Outputs:
Input:
10/23/98
Output:
10
23
98
Input:
05/07/99
Output:
05
07
99

Incorrect Inputs:
10/ 12/99 (Incorrect Input: Illegal separator: )(no spaces should be present)
10/.12/99 (Incorrect Input: Illegal separator: ) (no other characters either)
10/12 (not enough tokens present - exit program)
10//76 (Incorrect Input: Null digit Sequence !)

There must be a global variable in the scanner, which stores the number of tokens the scanner expects (in this case 3). The hasMoreElements() function should keep track of the number of tokens it has scanned, and return false both when input reaches end of string or when number of tokens reaches the max limit (3 in this case).

E.g.: If the scanner object is ADateEnumerator then the code in the Main class should be as follows:

String date[3];
int i = 0;
while (ADateEnumerator.hasMoreElements()) {
	date[i] = ADateEnumerator.getNextElement();
	i++;
}

Hint: Modify hasMoreElements() and skipInvalidTokens()
Extra Credit: Constrain the input to DD/DD/DD format

Part 2:

The functionality of the program remains the same as Part 1. But this time, refactor the code for ADateEnumerator so that it is a subclass of the scanner written in the recitation of September 23rd. You may also refactor the code for the scanner written on September 23rd (without changing any functionality). Here are all the files from part 1:
DigitEnumeration.java
ADateEnumeration.java
DateDriver.java

September 23, 2005

Problem:
As usual, this recitation builds on top of the previous one. Last time a constructor was added to the decimal class, which scanned the input (using a couple ofhelper functions). This time, an enumerator class is to be implemented (similar to what was discussed in the class), which is given the input string as its 'stream argument'.
The enumerator implements the following two functions: hasMoreElements, which returns a boolean value and getNextToken, which returns the next token (which is a sequence of digits in this case). This enumerator is instantiated in the constructor of the decimal class and is used to perform scanning, after which the integer and fractional parts of the decimal class are set.

Note: The main program just instantiates the decimal class and calls appropriate getter functions to print the integer, fractional and the rounded value.
Solution:
The file defines the interface for the ADecimal object (the getter, setter and rounded value functions). ADecimal.java implements the interface defined in Decimal.java. And ADecimalDriver.java has the main function, which instantiates the 'ADecimal' (by passing the input argument to it's constructor) and uses a getter function of 'ADecimal' object to get the rounded value. DigitEnumeration.java defines the enumeration interface for the scanner and ADigitEnumeration implements this interface. Note that 'ADigitEnumeration' is instantiated in the constructor of the 'ADecimal' class.

September 16, 2005

Problem:
This recitation involves refactoring the program developed in the previous recitation. You may use the code given in the 'Solutions' section of previous recitation. No additional user-interface features are to be added. The code is to be refactored in the following way:

Add a constructor to the 'Decimal' object which takes in a string argument. The constructor scans the argument (using helper functions which were previously defined) and sets the integer and fractional parts of the 'Decimal' object.
The main function will instantiate the 'Decimal' object by passing the input string to its constructor and will then call the getter methods of 'Decimal' object to get the integer, fractional and rounded values.

Note: The scanning code (used to scan the decimal number) needs to be moved from the main program to the 'Decimal' object.

September 9, 2005

Problem:
Write a program in Java, which on being given a decimal number (as an argument), scans through it to get the integer and fractional part, then rounds it off to the nearest integer. You can use the functions 'getDigitSequence' and 'getDot' from last week's 'Decimal.java', postel below. You should also define an interface for your class, and get ObjectEditor to work with it for getting and setting the object's properties. The program should print all the properties of the object (integer value, fractional value and the rounded value).

Sample Input:
34.32

Output:
Integer Part: 34
Fractional Part: 32
Rounded Value: 34

Solution:
The file Decimal.java defines the interface for the ADecimal object (it names the getter functions, setter functions and a function to round the decimal number). ADecimal.java implements the interface defined in Decimal.java. And ADecimalDriver.java has the main function, which scans through the input using a couple of helper functions (getDigitSequence() and getDot()), which were defined in recitation 1 (Link), calls the setter functions to set values in the ADecimal class and uses ObjectEditor to display the integer, fractional and rounded values.

September 2, 2005

Problem:
Write a program in Java, which on being given a decimal number (as an argument), scans through it to get the integer and decimal part and prints them in two different lines.

Sample Input:
34.32

Output:
34
32

Solution(s):
There are multiple ways to solve this problem. We preset two different solutions. The first one doesn't make use of any methods. Although the code is short, it is not very re-usable. The second solution makes use of methods to get the digits and the decimal point. These methods can easily be re-used. This is demonstrated in the third program, which scans through an IP (Internet Protocol) Address and prints out the four parts.

First Program - Doesn't make use of methods
Second Program - Makes use of methods
Third Program - Extension of the second program to scan through an IP Address