Assignment Set 9 (Uploaded on October 22, 2014)
Clarification deadline date: October 28, 2014
Submission deadline date:  October 30, 2014


Problem 1 [Trie and spell checker]: 
Write C code for the following problem: 

(a) Generate a trie structure T with all the words of the file: 
/usr/share/dict/words. 

First, one should carefully look at the content of the file as 
there are some special characters other than the English alphabets. 
Your implementation of T should be able to handle those characters. 
Measure the time needed to create T.

(b) Now, take a word (the word is denoted as 'w') from the user as input 
and check whether 'w' is present in the Trie. The searching should be 
case-insensitive; i.e., if there is a word 'action' present in the file 
and the user types in 'Action', the search should be successful. If 'w' 
is found in T, report that the word is a dictionary word. Otherwise, 
generate spell-correcting suggestions from the dictionary. There are four 
groups of words that are suggested from the dictionary.

Group 1: words obtained from T by delete any one letter from 'w';
Group 2: words obtained from T by adding one letter at any 
         position of 'w';
Group 3: words obtained from T by changing any single letter of 'w';
Group 4: words obtained from T by swapping any two letters of 'w'.

Report all the suggested words that are present in the dictionary. 
Measure the searching time.

[Marks: 60 (a) + 80{(b); 20x4 (20 marks each for 4 groups)} 
+ 20 {Good programming habits} = 150]

---------------------------------------------------------------
Naming conventions for program files. xx is your roll number: 

For Problem 1: 
The name of the src file for problem 1 of assignment 8 should be  
``cs14xx-assign9-src-prog1.c''. 

The name of the app file for problem 1 of assignment 8 should be  
``cs14xx-assign9-prog1.c''. 

The name of the include file for problem 1 of assignment 8 should be  
``cs14xx-assign9-prog1.h''. 

-----------------------------------------------------------------------

At the top of each of your program files, add the following. If you are 
writing multi-file programs, then each file should have it. 

/*------------------------------------------------------------------
Name: 
Roll Number:
Date of Submission:
Deadline date:  
Program description:
Acknowledgements: 
--------------------------------------------------------------------*/