Project 1: Simulate a simple dictionary. Assume each character contains at least 10 vocabularies. Create an index page for all characters. Retrieve the word using index value. Assume that the index characters from A to Z.

Project 2: Generate a computerized telephone directory for a cellular service consisting of name and cell phone number. Present the user with a menu that allows the user to search the directory for a specified record, insert a new record, delete an existing record, sort the record, or display the entire phone list.

Project 3: The details of SOIT in KINGS COLLEGE students such as Student Id, Name, Program, and CGPA to be managed. The list indicates both alphabetical ordering of names, ascending order of Student Id Number and alphabetical ordering of department names . Perform the following, Insert a new student detail in the appropriate position Remove a student detail where Student Id is given Find a student detail whose ID is given. Find student information whose name in a particular program is given. List all student detail in order of their name.

Project 4: Write a simulation program of the lines at a grocery store. The program will have multiple queues instead of one. You might use a vector of queues to simulate the lines. Assumes that there are five cashier lines at the grocery store. Customer enter randomly to check out, and then enter the shortest line. If the line are equal, then the first available line is chosen. Each transaction takes a random amount of time to complete. For additional work, expand the grocery line program to allow shoppers to:

Avoid a line if all lines are a certain length

Leave a line if they have waited beyond a certain time

Check if another line is shorter at specified time intervals

Switch line if another line is shorter

Project 5: This project deals with a simple kind of expression tree, where there are two kinds of nodes:

a) Leaf nodes, which contain a real number as their entry.

b) Nonleaf nodes, which contain either the character + or the character * as their entry, and have exactly two children. For this project, implement a class for expression trees, including operations for building expression trees. Also include a recursive function to "evaluate" a non-empty expression tree using these rules :

a) If the tree has only one node (which must be a leaf), then the evaluation of the tree returns the real number that is the node's entry;

b) If the tree has more than one node, and the root contains +, then the first evaluate the left subtree, then evaluate the right subtree, and add the results. If the root contains *, then evaluate the two subtrees and multiply the results.

For example , consider the small expression tree shown to the right. The left subtree evaluates to 3 + 7, which is 10. The right subtree evaluates to 14. So the entire tree evaluates to 10 * 14 , which is 140.

Project 6: Design and implement a concordance program, that stores a library of book records. Create a book class with name, ISBN, author, and publication date. Use a binary search tree to store the records, where the author name is the search key. Revise the binary search tree to be able to store and retrieve duplicate search keys.

Project 7: Implement a dictionary program using a table. The user inputs a word, and the word's definition is displayed. You will need to revise one of the table implementations to use a string as the search key. Hint : Use a hash function. You can also add and remove words from your dictionary.

Project 8: Rewrite the quicksort partition function so that the pivot is chosen by selecting the median of three random values from the array. Next, write a version using five random values. This may reduce the running time. Test both of these version with sorted arrays, random arrays, and reverse order arrays and display your results.

Project 9: One of the advantages of mergesort is that it can easily be adapted to sort a linked list of values. This is because the algorithm retrieves the values from the two lists being merged in the order that they occur in the lists. If the lists are linked lists, then that algorithm can simply move down the list node after node. With heapsort or quicksort the algorithm needs to move values from random location in the array, so they do not adapt as well to sorting a linked list. Write a program that sorts a linked list of integers using mergesort. This will require additional linked lists, but you should use linked lists, not arrays, for all your list storage.

Project 10: Work out an algorithm that uses a radix sort to sort strings of characters. Please take note that each Project Title CANNOT be more than FIVE member per-group. Submission: Each group need to complete all the tasks given and submit the outcome based on the following date: No Task Week Date 1 Project Report and Product 13 2 Presentation 14 The project report must include:

design issues, what are the problems and how you solve them

data structures you use, the decision behind selecting them

algorithms you employ, again with a justification of your decision

particular emphasis should be placed on the running time of your algorithm

optimization issues: what could you do to further optimize your algorithm

the report will also include results you obtained

any other remarks about your design and implementation You will have to send in a fully working program, written in C, that you can provide with a query, and obtain the list of documents. It is mandatory that you include a README file, as detailed as possible, including compilation and running instructions. Is it also mandatory that your programs are fully documented, that is they should include detailed comments on what is included in each file and what each method does. Submit your programs, presentation slide, reports, and all the materials you use which will be included in the folder name as PROJECTNUMBER_GROUPNAME, but make sure that your programs compile and run properly.