Case-Study or Student Projects on Data Structures
1. Game-based Learning for Data Structures – (Roll No.01-05) –Group-I
A case study on using a computer game for teaching data structures on stacks and queues. The computer game is developed to help students visualize the data structures and data access operations on stacks and queues. This game-based learning is engaging, fun and, more importantly, abstract concepts in data structures can be visualized and learnt through game playing.
2. Optimal treaps with priority-changing parameters (Roll No.07-10)- Group-II
Treaps are a combination of BSTs and heaps. These randomized data structures involve assigning specific priorities to the nodes. You can go for a project that optimizes a set of parameters under different settings. For instance, you can set higher preferences for nodes that are accessed more frequently than others. Here, each access will set off a two-fold process:
· Choosing a random number
· Replacing the node’s priority with that number if it is found to be higher than the previous priority
As a result of this modification, the tree will lose its random shape. It is likely that the frequently-accessed nodes would now be near the tree’s root, hence delivering faster searches. So, experiment with this data structure and try to base your argument on evidence. At the end of the project, you can either make an original discovery or even conclude that changing the priority of the node does not deliver much speed. It will be a relevant and useful exercise, nevertheless.
This project can demonstrate the working of contact book applications and also teach you about data structures like arrays, linked lists, stacks, and queues. Typically, phone book management encompasses searching, sorting, and deleting operations. A distinctive feature of the search queries here is that the user sees suggestions from the contact list after entering each character. You can read the source-code of freely available projects and replicate the same to develop your skills.
4. Graph-based projects on data structures (Roll No.15-18)- Group-IV
You can take up a project on topological sorting of a graph. For this, you will need prior knowledge of the DFS algorithm. Here is the primary difference between the two approaches:
· We print a vertex & then recursively call the algorithm for adjacent vertices in DFS.
· In topological sorting, we recursively first call the algorithm for adjacent vertices. And then, we push the content into a stack for printing.
Therefore, the topological sort algorithm takes a directed acyclic graph or DAG to return an array of nodes.
Let us consider the simple example of ordering a pancake recipe. To make pancakes, you need a specific set of ingredients, such as eggs, milk, flour or pancake mix, oil, syrup, etc. This information, along with the quantity and portions, can be easily represented in a graph.
But it is equally important to know the precise order of using these ingredients. This is where you can implement topological ordering. Other examples include making precedence charts for optimizing database queries and schedules for software projects. Here is an overview of the process for your reference:
· Call the DFS algorithm for the graph data structure to compute the finish times for the vertices
· Store the vertices in a list with a descending finish time order
· Execute the topological sort to return the ordered list.
5. User interface based shortest distance based city searching (Roll No.19-22)- Group-V
User gives two city names as inputs, one is source city and other is destination city. Your job is to predefine and store some city names and their inter-distances (km) in the form of graph by giving initial user inputs and then use Dijkstra’s shortest path and graph traversal algorithms to find the shortest path between two given cities.
6. Stack-based text editor (Roll No.23-26)- Group-VI
7. Word frequency analysis (Roll No.27-29)- Group-VII
Write a program that reads a file, breaks each line into words, strips whitespace and punctuation from the words, and converts them to lowercase.
Hint: The string module provides strings named whitespace, which contains space, tab, newline, etc., and punctuation which contains the punctuation characters. Let’s see if we can make Python swear:
>>> import string
>>> print string.punctuation
!"#$%&'()*+,-./:;<=>?@[\]^_`{|}~
Also, you might consider using the string methods strip, replace and translate. You can use any data structure to implement these operations.
The software aims to automate and speed up the choice of data structures for a given API. This project not only demonstrates novel ways of representing different data structures but also optimizes a set of functions to equip inference on them. We have compiled its summary below.
· The data structure search engine project requires knowledge about data structures and the relationships between different methods.
· Your search engine will advise which data structures are suitable for a specific kind of input data
· It computes the time taken by each possible composite data structure for all the methods on that data.
· Finally, it selects the best data structures for a particular case.