Heap insertion time Data Structures and Algorithams project

Data Structures Project Ideas 1. Obscure binary search trees Items, such as names, numbers, etc. can be stored in memory in a sorted order

called Binary Search Trees or BSTs. And some of these data structures can

automatically balance their height when arbitrary items are inserted or deleted.

Therefore, they are known as self-balancing BSTs. Further, there can be different

implementations of this type, like the BTrees, AVL trees, and red-black trees. But

there are many other lesser-known executions that you can learn about. Some

examples include AA trees, 2-3 trees, splay trees, and scapegoat trees.

You can base your project on these alternatives and explore how they can

outperform other widely-used BSTs in different scenarios. For instance, splay trees

can prove faster than red-black trees under the conditions of serious temporal

locality.

2. Phone directory application using doubly-linked lists 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.

3. BSTs following the memoization algorithm Memoization related to dynamic programming. In reduction-memoizing BSTs,

each node can memoize a function of its subtrees. Consider the example of a BST

of persons ordered by their ages. Now, let the child nodes store the maximum

income of each individual. With this structure, you can answer queries like, “What

is the maximum income of people aged between 18.3 and 25.3?” It can also handle

updates in logarithmic time.

Moreover, such data structures are easy to accomplish in Python language. You can

also attempt to bind it with Ruby and a convenient API. Go for an interface that

allows you to specify ‘lambda’ as your ordering function and your subtree

memoizing function. All in all, you can expect reduction-memoizing BSTs to be

self-balancing BSTs with a dash of additional book-keeping.

4. Heap insertion time When looking for data structure projects, you want to encounter distinct problems

being solved with creative approaches. One such unique research question concerns

the average case insertion time for binary heap data structures. According to some

online sources, it is constant time, while others imply that it is log(n) time.

But Bollobas and Simon give a numerically-backed answer in their paper entitled,

“Repeated random insertion into a priority queue.” First, they assume a scenario

where you want to insert n elements into an empty heap. There can be ‘n!’ possible

orders for the same. Then, they adopt the average cost approach to prove that the

insertion time is bound by a constant of 1.7645.

5. Optimal treaps with priority-changing parameters 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.

6. Research project on k-d trees K-dimensional trees or k-d trees organize and represent spatial data. These data

structures have several applications, particularly in multi-dimensional key searches

like nearest neighbor and range searches. Here is how k-d trees operate:

 Every leaf node of the binary tree is a k-dimensional point

 Every non-leaf node splits the hyperplane (which is perpendicular to that

dimension) into two half-spaces

 The left subtree of a particular node represents the points to the left of the

hyperplane. Similarly, the right subtree of that node denotes the points in the right

half.

You can probe one step further and construct a self-balanced k-d tree where each

leaf node would have the same distance from the root. Also, you can test it to find

whether such balanced trees would prove optimal for a particular kind of

application.

With this, we have covered five interesting ideas that you can study, investigate,

and try out.

7. Knight’s travails In this project, we will understand two algorithms in action – BFS and DFS. BFS

stands for Breadth-First Search and utilizes the Queue data structure to find the

shortest path. Whereas, DFS refers to Depth-First Search and traverses Stack data

structures.

For starters, you will need a data structure similar to binary trees. Now, suppose

that you have a standard 8 X 8 chessboard, and you want to show the knight’s

movements in a game. As you may know, a knight’s basic move in chess is two

forward steps and one sidestep. Facing in any direction and given enough turns, it

can move from any square on the board to any other square.

If you want to know the simplest way your knight can move from one square (or

node) to another in a two-dimensional setup, you will first have to build a function

like the one below.

 knight_plays([0,0], [1,2]) == [[0,0], [1,2]]

 knight_plays([0,0], [3,3]) == [[0,0], [1,2], [3,3]]

 knight_plays([3,3], [0,0]) == [[3,3], [1,2], [0,0]]

Furthermore, this project would require the following tasks:

 Creating a script for a board game and a night

 Treating all possible moves of the knight as children in the tree structure

 Ensuring that any move does not go off the board

 Choosing a search algorithm for finding the shortest path in this case

 Applying the appropriate search algorithm to find the best possible move from the

starting square to the ending square.

8. Spatial indexing with quadtrees The quadtrees data structure is a special type of tree structure, which can

recursively divide a flat 2-D space into four quadrants. Each hierarchical node in

this tree structure has either zero or four children. It can be used for various

purposes like sparse data storage, image processing, and spatial indexing.

Spatial indexing is all about the efficient execution of select geometric queries,

forming an essential part of geo-spatial application design. For example, ride-

sharing applications like Ola and Uber process geo-queries to track the location of

cabs and provide updates to users. Facebook’s Nearby Friends feature also has

similar functionality. Here, the associated meta-data is stored in the form of tables,

and a spatial index is created separately with the object coordinates. The problem

objective is to find the nearest point to a given one.

You can pursue quadtree data structure projects in a wide range of fields, from

mapping, urban planning, and transportation planning to disaster management and

mitigation. We have provided a brief outline to fuel your problem-solving and

analytical skills.

Objective: Creating a data structure that enables the following operations

 Insert a location or geometric space

 Search for the coordinates of a specific location

 Count the number of locations in the data structure in a particular contiguous area



9. Graph-based projects on data structures 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



10. Numerical representations with random access lists In the representations we have seen in the past, numerical elements are generally

held in Binomial Heaps. But these patterns can also be implemented in other data

structures. Okasaki has come up with a numerical representation technique using

binary random access lists. These lists have many advantages:

 They enable insertion at and removal from the beginning

 They allow access and update at a particular index

11. Stack-based text editor Your regular text editor has the functionality of editing and storing text while it is

being written or edited. So, there are multiple changes in the cursor position. To

achieve high efficiency, we require a fast data structure for insertion and

modification. And the ordinary character arrays take time for storing strings.

You can experiment with other data structures like gap buffers and ropes to solve

these issues. Your end objective will be to attain faster concatenation than the usual

strings by occupying smaller contiguous memory space.

Conclusion Leading companies hire for various lucrative job positions in the data structure and

algorithm domain. And in interviews, recruiters test not only your theoretical

knowledge but also your practical skills. So, practice the above data structure

projects to get your foot in the door and earn the mark you deserve!

References:

1- https://www.w3resource.com/projects/python/python-projects.php 2- https://www.geeksforgeeks.org/10-projects-that-every-developer-

should-lay-their-hands-on/

3- Agarwal, B., & Baka, B. (2018). Hands-On Data Structures and Algorithms with Python: Write complex and powerful code using the

latest features of Python 3.7. Packt Publishing Ltd.

4- https://www.upgrad.com/blog/data-structure-project-ideas-beginners/ 5- https://en.m.wikipedia.org/wiki/Persistent_data_structure