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.
This project idea handles text manipulation and offers suitable
features to improve the experience. The key functionalities of text
editors include deleting, inserting, and viewing text. Other features
needed to compare with other text editors are copy/cut and paste,
find and replace, sentence highlighting, text formatting, etc.
This project idea’s functioning depends on the data structures you
determined to use for your operations.
Spatial indexing with quadtrees
The quadtree 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.
QuadTrees are techniques for indexing spatial data. The root node
signifies the whole area and every internal node signifies an area
called a quadrant which is obtained by dividing the area enclosed
into half across both axes. These basics are important to
understand QuadTrees-related data structures topics.
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
One of the leading applications of QuadTrees in the data structure
is finding the nearest neighbor. For example, you are dealing with
several points in a space in one of the data structures topics. Suppose
somebody asks you what’s the nearest point to an arbitrary point.
You can search in a quadtree to answer this question. If there is no
nearest neighbor, you can specify that there is no point in this
quadrant to be the nearest neighbor to an arbitrary point.
Consequently, you can save time otherwise spent on comparisons.
Spatial indexing with Quadtrees is also used in image compression
wherein every node holds the average color of each child. You get
a more detailed image if you dive deeper into the tree. This project
idea is also used in searching for the nods in a 2D area. For
example, you can use quadtrees to find the nearest point to the
given coordinates.
Follow these steps to build a quadtree from a two-dimensional
area:
1. Divide the existing two-dimensional space into four boxes.
2. Create a child object if a box holds one or more points within. This object
stores the box’s 2D space.
3. Don’t create a child for a box that doesn’t include any points.
4. Repeat these steps for each of the children.
5. You can follow these steps while working on one of the file structure mini
project topics.
Social Media Network
If you want to create a social meda network project or something similar to this, then
the best approach would be to use graphs. Each person would represent
a node (vertex) and the relationships between them would be represented
as edges. This relationship between them can be friendships, follows, likes, or
comments.
Project title: Social Media Network
Algorithms/DS involved: graph
GitHub link: [Link]
Difficulty rating: 4
Web Crawler
Web crawlers explore the internet and gather information from websites. It starts
with a URL then it follows the links from the page to visit other pages. Here, we can
use a queue data structure to store the visited websites. The easiest algorithm to
use would be breadth-first search so that the crawler visits all the links from
the current website first before moving on to other websites.
Project title: Web Crawler
Algorithms/DS involved: queue, breadth-first search (BFS)
GitHub link: [Link]
Difficulty rating: 5
[Link]
