Suggested Mini Projects in Data Structures using C++

Mini Project Specification

1. Write a program that uses a hashing algorithm to create a list of inventory parts and their quantities sold in the past month. After creating the hashed list , write a simple menu driven user interface that allows the user to select from the following options:

a. Search for an inventory item and report its quantity sold

b. Print the inventory parts and their quantities sold

c. Analyze the efficiency of the hashing algorithm

 The parts data are contained in a text file, as shown in the following table. The key is the three digit part number. The quantity represents the units sold during the past month.

Part Number	Quantity
121	12
123	11
190	43
112	90

2. 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.

3. Construct at least five heaps of size varying from 100 to 2000 filling with random numbers. Measure efficiency as the number of data moves in order to build the heap. Analyze the performance of the heaps while construction and produce a comparison report in the form of graph.

4. Consider a binary search tree to store data entities. Randomly generate the data entities and analyze the performance of the tree (insertion, deletion, searching) at various sizes of the tree (Use at least five different sizes of the tree). Produce report in the form of graph

5. Consider a height balanced tree (AVL) to store data entities. Randomly generate the data entities and analyze the performance of the tree (insertion, deletion, searching) at various sizes of the tree (Use at least five different sizes of the tree). Produce report in the form of graph.

6. Construct a linear list to store randomly generated numbers in ascending order. Analyze the performance of the list in terms of insertion at various sizes of the list.

7. Perform quick sort and shell sort for a randomly generated set of elements of sizes 100,200,500 and 800. Calculate the number of moves and comparisons for each sorting. Generate the report as a graph.

8. 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, or print the entire phone list. Produce the results as a text file.

9. Design a simple search engine to display the possible websites upon entering a search query. Use suitable data structure for storage and retrieval.

10. Write a program that uses the radix sort to sort 1000 random digits. Print the data before and after the sort. Each sort bucket should be a linked list. At the end of the sort, the data should be in the original array

11. An electronics goods dealer has 50 different types of item and for each item he has a maximum of 5 branded company products for sale. Read and store the monthly sales (day wise) of the shop in a multi list and produce the following reports.

List the day wise total sales amount of all goods

List the monthly sale details of refrigerator.

List the monthly sale details of all LG brand electronic goods

12. Construct the splay tree for storing N students Roll No (primary key), name and department then perform delete, modify and search operations on it. Determine the activity count of each node, where activity count is the number of times the node has been visited.

13. Design a stack and queue test driver. A test driver is a program created to test functions that are to be placed in a library. Its primary purpose is to completely test functions

a. Input Stack: used to store all user input

b. Input Queue: used to store all user input

c. Output Stack: used to store data deleted from input queue

d. Output Queue: used to store data deleted from input stack

Use a menu-driven interface that prompts the user to select either to insert or delete. If an insert is requested, the system should prompt the user for the integer to be inserted. The data are then inserted into the input stack and input queue. If a delete is requested , the data are deleted from both structures ; the data popped from the input stack are enqueued in the output queue, and the data dequeued from the input queue are pushed into the output stack

14. Create the index for a text book of at least 100 pages using alphabets.

Hints: Ignore the list following words such as the, there, these, those etc., what, which, where etc., is, are, to, too, also, if, must, can, may, should, so, hence, therefore, because, before, after and commonly used verbs.

15. Construct the Huffman Tree for the given text then, read a line of text and do text compression using the Huffman code. The Huffman code for each letter is derived from a full binary tree called the Huffman tree. Each leaf of the tree corresponds to a letter. The goal is to build a tree such that a letter with high frequency should have low depth. Use Priority queue to maintain the frequencies of each letter. Compute compression ratio for various ASCII text files

16. The details of employees (Emp.Id, Name, Department and Total Years of experience) of a company are to be maintained. The list indicates both alphabetical ordering of names, ascending order of Emp.Id Number and alphabetical ordering of department names .

Perform the following,

·         Insert a new employee detail in the appropriate position

·         Remove an employee detail where Emp.Id is given

·         Find an employee detail whose ID is given.

·         Find employee information whose name in a particular department is given.

·         List all employee detail in order of their name.

17. Our study of tree algorithmic has shown that most tree structures are quite efficient. Let’s examine the efficiency of Binary search tree, AVL tree and B-Tree. Compare the time complexities of the tree data structures (Binary search tree, AVL tree, B-Tree) for various operations (Insertion, deletion and searching). To determine a pattern run your program with arrays filed with random numbers... Prepare a short report of your findings with appropriate tables and graphs.

18. Develop an application that will implement all basic trees related concepts and operations and will show the trees graphically.

19. Develop an application that will implement and trace recursive functions graphically.

20. Design a Student Prerequisite Subjects Management System requires the use of linked list or tree to store different courses and their prerequisites and based on this list it will allow any student to take any course or not.