CSL-201 : Data Structure. II Semester, 2009-2010
Assignment- 1
Due: 11:55PM, 31th January 2010


WAP to implement a Dictionary of integers which consists of following methods: 
1.	SortedArray(int a)	: is a constrcutor which creates a dictionary of size a.
2.	void insert(int x)	: Inserts element x at  its proper position. 
				  a.	Raise exception Dictionary_Full when dictionary is already full (in case of SortedArray)
				  b.	If x already exists, then raise exception Duplicate_Element_Found
3.	boolean delete(int x)	: Deletes element x and returns true if x existed otherwise false. 
				  a.	If x does not exists, the operation raises the exception Element_not_Found, which handles the exception by returning the 
					predecessor and successor of x if x would have existed in the dictionary.
				  b.	If the dictionary is empty, it raises the Dictionary_Empty exception which handles it by returning a message "Dictionary Empty"
4.	boolean find(int x)	: Returns true if x exists otherwise false and raises the exception Element_not_Found.
5.	void display()		: Displays the dictionary's elements in order.

The input for the program must be from the file input.txt. For example, the input.txt might contain the following sequence of operations
I(5) 	// I for insert
I(7)
I(5)
R(7)    // R is used for delete
F(12)   // F for find
D       // D is used for display

The output should be written in a file output.txt. For example, for the above sequence of inputs, the Dictionary will generate the following output
Element 5 Inserted
Element 7 Inserted
Duplicate Element
Element 7 Deleted
5
5

The assignment is divided into following parts:

PART-A : Implement the dictionary using a sorted array. Here you will be required to implement find operation using linear and binary search. 
	 The class name should be SortedArray
PART-B : Implement the dictionary using a sorted linked list. Here you will be required to implement find operation using only linear search.
	 The class name should be SortedList.

Guidelines
1.	You can refer the following links
	  a. For Java language reference, follow http://java.sun.com/docs/books/tutorial/java/index.html   
	  b. For Exception handling and File I/O, refer http://java.sun.com/docs/books/tutorial/essential/index.html
2.	You can only use simple array for both part of the implementations
3.	You have to only use Java compiler i.e. javac (available in both platforms, Linux and Windows). Usage of any other Java Editor will be awarded 0.
4.	You have to submit a single file called assignment1.zip -- which will be your assignment directory zipped. The directory should contain 
	all your .java files and a makefile and nothing else.