Data Structures and Algorithms (DSA) refer to the study of methods for

organizing and storing data and the design of procedures (algorithms) for
solving problems, which operate on these data structures. DSA is one of
the most important skills that every computer science student must have.
It is often seen that people with good knowledge of these technologies are
better programmers than others and thus, crack the interviews of almost
every tech giant. This DSA tutorial aims to help you learn Data Structures
and Algorithms (DSA) quickly and easily.

DSA Full Form

The term DSA stands for Data Structures and Algorithms, in the context
of Computer Science.
What is DSA?
Data Structures and Algorithms (DSA) refer to the study of methods for
organizing and storing data and the design of procedures (algorithms) for
solving problems, which operate on these data structures.
How to learn DSA?
The first and foremost thing is dividing the total procedure into little pieces
which need to be done sequentially. The complete process to learn DSA
from scratch can be broken into 5 parts:
1. Learn at least one programming language (We leave this to your
choice.)
2. Learn Data Structures
3. Learn Algorithms
4. Learn about Time and Space complexities
5. Practice Problems on DSA
Here comes the most important and the most awaited stage of the
roadmap for learning data structure and algorithm – the stage where you
start learning about DSA. The topic of DSA consists of two parts:
 Data Structures
 Algorithms
Though they are two different things, they are highly interrelated, and it is
very important to follow the right track to learn them most efficiently. If you
are confused about which one to learn first, we recommend you to go
through our detailed analysis on the topic: What should I learn first-
Data Structures or Algorithms?
Here we have followed the flow of learning a data structure and then the
most related and important algorithms used by that data structure.
1. Learn Data Structures
Data structures are essential components that help organize and store
data efficiently in computer memory. They provide a way to manage and
manipulate data effectively, enabling faster access, insertion, and deletion
operations. Common data structures include arrays, linked lists, stacks,
queues, trees, and graphs , each serving specific purposes based on
the requirements of the problem at hand. Understanding data structures is
fundamental for designing efficient algorithms and optimizing software
performance.

Common Data Structures to learn:

1. Array
Array is a linear data structure that stores a collection of elements of the
same data type. Elements are allocated contiguous memory, allowing for
constant-time access. Each element has a unique index number.
 Operations on Array:
o Traversal: Iterating through the elements of an array.
 o Insertion: Adding an element to the array at a specific index.
o Deletion: Removing an element from the array at a specific
index.
o Searching: Finding an element in the array by its value or
index.
 Types of Arrays:
o One-dimensional array: A simple array with a single
dimension.
o Multidimensional array: An array with multiple dimensions,
such as a matrix.
 Applications of Array:
o Storing data in a sequential manner
o Implementing queues, stacks, and other data structures
o Representing matrices and tables

Getting Started with Array Data Structure

Array is a collection of items of the same variable type that are stored at
contiguous memory locations. It is one of the most popular and simple
data structures used in programming. In this article, we have decided to
provide a complete guide for Arrays, which will help you to tackle any
problem based on Arrays.

What is an Array?
Array is a linear data structure that stores a collection of items of same
data type in contiguous memory locations. Each item in an array is
indexed starting with 0. We can directly access an array element by using
its index value.
Basic terminologies of Array
 Array Index: In an array, elements are identified by their indexes.
Array index starts from 0.
 Array element: Elements are items stored in an array and can be
accessed by their index.
 Array Length: The length of an array is determined by the number of
elements it can contain.
Memory representation of Array
In an array, all the elements are stored in contiguous memory locations.
So, if we initialize an array, the elements will be allocated sequentially in
memory. This allows for efficient access and manipulation of elements.

Declaration of Array
Arrays can be declared in various ways in different languages. For better
illustration, below are some language-specific array declarations:

Initialization of Array
Arrays can be initialized in different ways in different languages. Below
are some language-specific array initializations:
Importance of Array
Assume there is a class of five students and if we have to keep records of
their marks in examination then, we can do this by declaring five variables
individual and keeping track of records but what if the number of students
becomes very large, it would be challenging to manipulate and maintain
the data.
What it means is that, we can use normal variables (v1, v2, v3, ..) when
we have a small number of objects. But if we want to store a large number
of instances, it becomes difficult to manage them with normal
variables. The idea of an array is to represent many instances in one
variable.

Types of Arrays
Arrays can be classified in two ways:
 On the basis of Size
 On the basis of Dimensions
Types of Arrays on the basis of Size:
1. Fixed Sized Arrays:
We cannot alter or update the size of this array. Here only a fixed size (i,e.
the size that is mentioned in square brackets []) of memory will be
allocated for storage. In case, we don’t know the size of the array then if
we declare a larger size and store a lesser number of elements will result
in a wastage of memory or we declare a lesser size than the number of
elements then we won’t get enough memory to store all the elements. In
such cases, static memory allocation is not preferred.

2. Dynamic Sized Arrays:

The size of the array changes as per user requirements during execution
of code so the coders do not have to worry about sizes. They can add and
removed the elements as per the need. The memory is mostly
dynamically allocated and de-allocated in these arrays.

Types of Arrays on the basis of Dimensions:

1. One-dimensional Array(1-D Array): You can imagine a 1d array as a
row, where elements are stored one after another.
2. Multi-dimensional Array: A multi-dimensional array is an array with
more than one dimension. We can use multidimensional array to store
complex data in the form of tables, etc. We can have 2-D arrays, 3-D
arrays, 4-D arrays and so on.
 Two-Dimensional Array(2-D Array or Matrix): 2-D Multidimensional
arrays can be considered as an array of arrays or as a matrix
consisting of rows and columns.

 Three-Dimensional Array(3-D Array): A 3-D Multidimensional

array contains three dimensions, so it can be considered an array of
two-dimensional arrays.
Operations on Array
1. Array Traversal:
Array traversal involves visiting all the elements of the array once. Below
is the implementation of Array traversal in different Languages:

2. Insertion in Array:
We can insert one or multiple elements at any position in the array. Below
is the implementation of Insertion in Array in different languages:

3. Deletion in Array:
We can delete an element at any index in an array. Below is the
implementation of Deletion of element in an array:
4. Searching in Array:
We can traverse over an array and search for an element. Below is the
implementation of Deletion of element in an array:

Complexity Analysis of Operations on Array

Time Complexity:
Operation Best Case Average Case Worst Case

Traversal Ω(N) θ(N) O(N)

Insertion Ω(1) θ(N) O(N)

 Operation Best Case Average Case Worst Case

Deletion Ω(1) θ(N) O(N)

Searching Ω(1) θ(N) O(N)

Space Complexity:
Operation Best Case Average Case Worst Case

Traversal Ω(1) θ(1) O(1)

Insertion Ω(1) θ(N) O(N)

Deletion Ω(1) θ(N) O(N)

Searching Ω(1) θ(1) O(1)

Advantages of Array
 Arrays allow random access to elements. This makes accessing
elements by position faster.
 Arrays have better cache locality which makes a pretty big difference
in performance.
 Arrays represent multiple data items of the same type using a
single name.
 Arrays are used to implement the other data structures like linked lists,
stacks, queues, trees, graphs, etc.
Disadvantages of Array
 As arrays have a fixed size, once the memory is allocated to them, it
cannot be increased or decreased, making it impossible to store extra
data if required. An array of fixed size is referred to as a static array.
 Allocating less memory than required to an array leads to loss of data.
 An array is homogeneous in nature so, a single array cannot store
values of different data types.
 Arrays store data in contiguous memory locations, which makes
deletion and insertion very difficult to implement. This problem is
overcome by implementing linked lists, which allow elements to be
accessed sequentially.
Applications of Array
 They are used in the implementation of other data structures such as
array lists, heaps, hash tables, vectors, and matrices.
 Database records are usually implemented as arrays.
 It is used in lookup tables by computer.

2. String
A string is a sequence of characters, typically used to represent text. It is
considered a data type that allows for the manipulation and processing of
textual data in computer programs.
 Operations on String :
o Concatenation: Joining two strings together.
o Comparison: Comparing two strings lexicographically.
o Substring extraction: Extracting a substring from a string.
o Search: Searching for a substring within a string.
o Modification: Changing or replacing characters within a
string.
 Applications of String :
o Text processing
o Pattern matching
o Data validation
o Database management

Basic String Operations with Implementation

In this post, we will look into some of the basic String operations such as:
 Accessing characters by index in a string.
 Inserting character into a String.
 Modifying character in String
 Deletion of Character in String
 Concatenating strings (combining multiple strings into one).
 Finding the length of a string
 Comparing strings for equality or lexicographical order
Accessing characters by index in a string.
To access any character in a String, we need:
1. A non-empty string (say “str”)
2. A position/index of the character from where it is to be accessed. (say
“k”)
Using these two, the character can be easily accessed using the below
syntax:
OUTPUT:

Inserting Character/String into an String.

To insert any Character/String in a String, we need:
1. A character/string that is to be inserted in the string (say “ch”)
2. A position/index of the Character/String where it is to be inserted. (say
“k”)
Modifying character in String
To modify any Character in a String, we need:
1. A character that is to replaced in the string (say “ch”)
2. A position/index of the Character where it is to be replaced at. (say “k”)
Below is the implementation of the above approach:
Deletion of character in String
To delete any Character in a String, we need:
 A character that is to deleted in the string (say “ch”) Below is the
implementation of the above approach:
Comparing Strings for Equality
To compare strings, Define a function to compare values with the
following conditions :
1. if (string1 != string2) it returns a False.
2. if both the strings are equal lexicographically (string1 == string2), it
returns True.
Below is the implementation of the above approach:
3. Linked Lists
A linked list is a linear data structure that stores data in nodes, which are
connected by pointers. Unlike arrays, linked lists are not stored in contiguous
memory locations.
 Characteristics of Linked List:
o Dynamic: Linked lists can be easily resized by adding or
removing nodes.
o Non-contiguous: Nodes are stored in random memory
locations and connected by pointers.
o Sequential access: Nodes can only be accessed
sequentially, starting from the head of the list.
 Operations on Linked List:
o Creation: Creating a new linked list or adding a new node to
an existing list.
o Traversal: Iterating through the list and accessing each node.
o Insertion: Adding a new node at a specific position in the list.
o Deletion: Removing a node from the list.
 o Search: Finding a node with a specific value in the list.
 Types of Linked List:
o Singly Linked List: Each node points to the next node in the
list.
o Doubly Linked List: Each node points to both the next and
previous nodes in the list.
o Circular Linked List: The last node points back to the first
node, forming a circular loop.
 Applications of Linked List:
o Linked lists are used in various applications, including:
o Implementing queues and stacks
o Representing graphs and trees
o Maintaining ordered data
o Memory management

Introduction to Singly Linked List

Singly linked list is a linear data structure in which the elements are not
stored in contiguous memory locations and each element is connected
only to its next element using a pointer.

Basic Terminologies of Linked List

Linked List is a linear data structure, in which elements are not stored at
a contiguous location, rather they are linked using pointers. Linked List
forms a series of connected nodes, where each node stores the data and
the address of the next node.

Node Structure: A node in a linked list typically consists of two

components:
1. Data: It holds the actual value or data associated with the node.
2. Next Pointer or Reference : It stores the memory address (reference)
of the next node in the sequence.
Head and Tail: The linked list is accessed through the head node, which
points to the first node in the list. The last node in the list points to NULL
or nullptr, indicating the end of the list. This node is known as the tail
node.

Why linked list data structure needed?

The main cases where we prefer linked list over arrays is due to ease of
insertion and deletion in linked list
Example:
In a system, if we maintain a sorted list of IDs in an array id[] = [1000,
1010, 1050, 2000, 2040].
If we want to insert a new ID 1005, then to maintain the sorted order, we
have to move all the elements after 1000 (excluding 1000).
Deletion is also expensive with arrays until unless some special
techniques are used. For example, to delete 1010 in id[], everything after
1010 has to be moved due to this so much work is being done which
affects the efficiency of the code.

Types of linked lists:

There are mainly three types of linked lists:
1. Single-linked list
2. Double linked list
3. Circular linked list
1. Single-linked list:
In a singly linked list, each node contains a reference to the next node in

Single-linked list

2. Double-linked list:
In a doubly linked list, each node contains references to both the next and
previous nodes. This allows for traversal in both forward and backward
directions, but it requires additional memory for the backward reference.
 Double-linked list

3. Circular linked list:

In a circular linked list, the last node points back to the head node,
creating a circular structure. It can be either singly or doubly linked.

Circular linked list

Operations on Linked Lists

1. Insertion: Adding a new node to a linked list involves adjusting the
pointers of the existing nodes to maintain the proper sequence.
Insertion can be performed at the beginning, end, or any position within
the list
2. Deletion: Removing a node from a linked list requires adjusting the
pointers of the neighbouring nodes to bridge the gap left by the deleted
node. Deletion can be performed at the beginning, end, or any position
within the list.
3. Searching: Searching for a specific value in a linked list involves
traversing the list from the head node until the value is found or the end
of the list is reached.
Matrix/Grid
A matrix is a two-dimensional array of elements, arranged in rows and
columns. It is represented as a rectangular grid, with each element at the
intersection of a row and column.
 Key Concepts:
o Rows: Horizontal lines of elements in a matrix.
o Columns: Vertical lines of elements in a matrix.
o Dimensions: The number of rows and columns in a matrix
(e.g., a 3×4 matrix has 3 rows and 4 columns).
o Element Access: Elements can be accessed using row and
column indices (e.g., M[2][3] refers to the element in row 2,
column 3).
 Applications of Matrix/Grid:
 o Image processing
o Data analysis
o Optimization problems
5. Stack
Stack is a linear data structure that follows a particular order in which the
operations are performed. The order may be LIFO(Last In First
Out) or FILO(First In Last Out). LIFO implies that the element that is
inserted last, comes out first and FILO implies that the element that is
inserted first, comes out last.
 Operation on Stack :
o Push: Adds an element to the top of the stack
o Pop: Removes and returns the element at the top of the stack
o Peek: Returns the element at the top of the stack without
removing it
o Size: Returns the number of elements in the stack
o IsEmpty: Checks if the stack is empty
 Applications of Stack :
o Function calls
o Expression evaluation
o Backtracking
o Undo/redo operations
6. Queue
A Queue Data Structure is a fundamental concept in computer science
used for storing and managing data in a specific order. It follows the
principle of “First in, First out” (FIFO), where the first element added to
the queue is the first one to be removed
 Operation on Queue :
o Enqueue: Adds an element to the rear of the queue
o Dequeue: Removes an element from the front of the queue
o Peek: Retrieves the front element without removing it
o IsEmpty: Checks if the queue is empty
o IsFull: Checks if the queue is full
 Type of Queue:
o Circular Queue: Last element connects to the first element
o Double-Ended Queue (Deque): Operations can be performed
from both ends
o Priority Queue: Elements are arranged based on priority
 Applications of Queue :
o Job scheduling
o Message queuing
o Simulation modeling
o Data buffering
7. Heap
A Heap is a complete binary tree data structure that satisfies the heap
property: for every node, the value of its children is less than or equal to
its own value. Heaps are usually used to implement priority queues,
where the smallest (or largest) element is always at the root of the tree.
 Operations of Heap :
o Insert: Adds a new element to the heap while maintaining
heap properties.
o Extract-Max/Extract-Min: Removes the root element and
restructures the heap.
o Increase/Decrease-Key: Updates the value of a node and
restructures the heap.
 Types of Heap:
o Max-Heap: Root node has the maximum value among its
children.
o Min-Heap: Root node has the minimum value among its
children.
 Applications of Heap :
o Priority queues
o Sorting
o Graph algorithms (e.g., Dijkstra’s algorithm)

. Hash
Hashing is a technique that generates a fixed-size output (hash value)
from an input of variable size using mathematical formulas called hash
functions. Hashing is used to determine an index or location for storing
an item in a data structure, allowing for efficient retrieval and insertion.
 Key Concepts:
o Hash Function: A mathematical function that maps an input to
a hash value.
o Hash Table: A data structure that stores key-value pairs,
where the key is a hash value and the value is the actual data.
o Collision: When two different keys produce the same hash
value.
 Types of Hash Functions :
o Division Method: Divides the input by a constant and uses
the remainder as the hash value.
o Mid Square Method: Squares the input and takes the middle
digits as the hash value.
o Folding Method: Divides the input into equal-sized blocks
and adds them together to get the hash value.
o Multiplication Method: Multiplies the input by a constant and
takes the fractional part as the hash value.
 Collision Resolution Techniques :
 o Separate Chaining (Open Hashing): Stores colliding elements
in a linked list at the corresponding hash value.
o Open Addressing (Closed Hashing): Uses various strategies
to find an alternative location for colliding elements within the
hash table.
 Applications of Hashing:
o Efficiently storing and retrieving data in databases and file
systems.
o Verifying passwords and digital signatures.
o Distributing requests across multiple servers.
o Generating secure hashes for data integrity and
authentication.

9. Tree
A tree is a non-linear hierarchical data structure consisting of nodes connected by
edges, with a top node called the root and nodes having child nodes. It is used in
computer science for organizing data efficiently.
 Traversal of Tree: Tree traversal methods are used to visit and process nodes
in a tree data structure. The three common traversal methods are:
o In-Order: Visit left subtree, current node, then right subtree.
o Pre-Order: Visit current node, left subtree, then right subtree.
o Post-Order: Visit left subtree, right subtree, then current node.
 Classifications of Trees:
o Classifications of Trees refer to grouping trees based on certain
characteristics or criteria. This can involve categorizing trees based
on their balance factor, degree of nodes, ordering properties, etc.
Below are some important classification of Tree.
Classification Description
Type Description

Each node has at most

Binary Tree
two children.
Trees can be classified
based on the maximum Each node has at most
By Degree Ternary Tree
number of children three children.
each node can have.
Each node has at most N
N-ary Tree
children.

By Ordering Trees can be classified Binary Left child < parent < right
based on the ordering Search Tree child for every node.
of nodes and subtrees (BST)
Classification Description
Type Description

Specialized binary tree

Heap
with the heap property.

Heights of subtrees differ

Balanced by at most one. Examples
Tree include AVL trees and
Red-Black trees.
Trees can be classified
By Balance based on how well-
balanced they are. Heights of subtrees can
differ significantly,
Unbalanced
affecting performance in
Tree
operations like search and
insertion.

 Applications of Trees:
o File systems
o Databases
o XML documents
o Artificial intelligence

10. Graph
A Graph is a non-linear data structure consisting of a finite set of
vertices(or nodes) and a set of edges that connect a pair of nodes.
 Traversals of Graph:
o Breadth-First Search (BFS): Visits nodes level by level.
o Depth-First Search (DFS): Visits nodes recursively, exploring
one branch at a time.
 Applications of Graphs :
o Social networks
o Maps and navigation
o Scheduling
o Data mining
 Related posts:
o Graph Representation
o Types of graphs
o Graph Tutorial
o Practice problems on Graph
Learn Algorithms
Once you have cleared the concepts of Data Structures, now its time to
start your journey through the Algorithms. Based on the type of nature
and usage, the Algorithms are grouped together into several categories,
as shown below:
1. Searching Algorithm
Searching algorithms are used to locate specific data within a larger set
of data. It helps find the presence of a target value within the data. There
are various types of searching algorithms, each with its own approach and
efficiency.
 Most common searching algorithms:
o Linear Search: Iterative search from one end to the other.
o Binary Search: Divide-and-conquer search on a sorted array,
halving the search space at each iteration.
o Ternary Search: Divide-and-conquer search on a sorted array,
dividing the search space into three parts at each iteration.
 Other searching algorithms:
o Jump Search
o Interpolation Search
o Exponential Search
 Related Topics:
o Practice problems on Searching algorithm
2. Sorting Algorithm
Sorting algorithms are used to arranging the elements of a list in a
specific order, such as numerical or alphabetical. It organizes the items in
a systematic way, making it easier to search for and access specific
elements.
There are a lot of different types of sorting algorithms. Some widely used
algorithms are:
Sorting
Algorithm Description

Iteratively compares adjacent elements and swaps them if

Bubble Sort they are out of order. The largest element “bubbles” to the
end of the list with each pass.

Finds the minimum element in the unsorted portion of the list

Selection
and swaps it with the first element. Repeats this process until
Sort
the entire list is sorted.

Builds the sorted list one element at a time by inserting each

Insertion
unsorted element into its correct position in the sorted
Sort
portion.
 Sorting
Algorithm Description

A divide-and-conquer algorithm that selects a pivot element,

Quick Sort partitions the list into two sublists based on the pivot, and
recursively applies the same process to the sublists.

Another divide-and-conquer algorithm that recursively divides

Merge Sort the list into smaller sublists, sorts them, and then merges
them back together to obtain the sorted list.

Related Topics:
 Sorting Algorithm Tutorial
 Top Sorting Interview Questions and Problems
 Practice problems on Sorting algorithm
3. Divide and Conquer Algorithm
Divide and conquer algorithms follow a recursive strategy to solve
problems by dividing them into smaller subproblems, solving those
subproblems, and combining the solutions to obtain the final solution.
Steps:
1. Divide: Partition the problem into smaller, independent subproblems.
2. Conquer: Recursively solve each subproblem.
3. Combine: Merge the solutions of the subproblems to obtain the final
solution.
Examples:
 Merge Sort: Divides the array into two halves, sorts each half
recursively, and merges the sorted halves.
 Quick Sort: Selects a pivot element, partitions the array into two
subarrays based on the pivot, and recursively sorts each subarray.
 Binary Search: Divides the search space in half repeatedly until the
target element is found or the search space is exhausted.
Related Articles:
 Divide and Conquer Tutorial
 Practice problems on Divide And Conquer algorithm
4. Greedy Algorithms
As the name suggests, this algorithm builds up the solution one piece at a
time and chooses the next piece which gives the most obvious and
immediate benefit i.e., which is the most optimal choice at that moment.
So the problems where choosing locally optimal also leads to the global
solutions are best fit for Greedy.
Some Important Problem of Greedy Algorithms are:
 Algorithm Description

Fractional Find the maximum total value of items that can be placed in
Knapsack the knapsack, allowing fractional inclusion of items.

Dijkstra’s Finds the shortest path from a source vertex to all other
Algorithm vertices in a weighted graph.

Kruskal’s
Finds the minimum spanning tree of a weighted graph.
Algorithm

Huffman Creates an optimal prefix code for a set of symbols,

Coding minimizing the total encoding length.

Related Articles:
 Greedy Algorithm Tutorial
 Practice problems on Greedy algorithm
5. Recursion
Recursion is a programming technique where a function calls itself within
its own definition. It is usually used to solve problems that can be broken
down into smaller instances of the same problem. For Example: Towers
of Hanoi (TOH), Factorial Calculation and Fibonacci Sequence etc.
Steps:
 Base Case: Define a condition that stops the recursive calls and
provides a solution.
 Recursive Case: Define the steps to break down the problem into
smaller instances and make recursive calls.
 Return: Return the solution from the recursive calls and combine them
to solve the original problem.
The point which makes Recursion one of the most used algorithms is that
it forms the base for many other algorithms such as Tree
traversals, Graph traversals, Divide and Conquers
Algorithms and Backtracking algorithms.
Related Topics:
 Recursion Tutorial
 Recursive Functions
 Tail Recursion
 Top 50 Problems on Recursion Algorithm for Interview
 Practice problems on Recursion algorithm
6. Backtracking Algorithm
As mentioned earlier, the Backtracking algorithm is derived from the
Recursion algorithm, with the option to revert if a recursive solution fails,
i.e. in case a solution fails, the program traces back to the moment where
it failed and builds on another solution. So basically it tries out all the
possible solutions and finds the correct one.
Some important and most common problems of backtracking algorithms,
that you must solve before moving ahead, are:
Problem Description

Knight’s tour Finding a sequence of moves by a knight on a chessboard

problem such that it visits every square exactly once.

Rat in a Finding a path from the starting position to the exit in a maze,
Maze with obstacles represented as walls.

N-Queen Placing N queens on an N×N chessboard such that no two

Problem queens attack each other.

Subset Sum Determining whether there exists a subset of the given set
Problem with a given sum.

Solving a 9×9 grid puzzle with numbers from 1 to 9 such that

Sudoku each row, column, and 3×3 subgrid contains all the digits
without repetition.

Related Article:
 Backtracking Tutorial
 Practice problems on Backtracking algorithm
7. Dynamic Programming
Dynamic Programming is a method used in mathematics and computer
science to solve complex problems by breaking them down into simpler
subproblems. By solving each subproblem only once and storing the
results, it avoids redundant computations, leading to more efficient
solutions for a wide range of problems.
Key Concepts:
 Optimal Substructure: The optimal solution to a problem can be
constructed from the optimal solutions to its subproblems.
 Overlapping Subproblems: Subproblems are often repeated in the
larger problem, leading to redundant computations.
 Memoization / Tabulation: Storing the solutions to subproblems to
avoid recomputation.
Some important and most common problems of dynamic programming
algorithms, that you must solve before moving ahead, are:
Problem Description

Fibonacci Generating Fibonacci numbers using dynamic

Sequence programming to avoid redundant calculations.

Longest Common Finding the longest subsequence common to two

Subsequence sequences.

Longest Increasing Finding the longest subsequence of a given sequence

Subsequence in which the elements are sorted in increasing order.

Determining the maximum value that can be obtained

0/1 Knapsack
by selecting items with given weights and values,
Problem
while not exceeding a specified weight limit.

Rod Cutting Maximizing the profit by cutting a rod of given length

Problem into pieces and selling them according to given prices.

Coin Change Determining the number of ways to make change for a

Problem given amount using a given set of coin denominations.

Finding the minimum number of operations (insertion,

Edit Distance deletion, substitution) required to convert one string
into another.

Subset Sum Determining whether there exists a subset of a given

Problem set with a given sum.

Longest Finding the longest subsequence of a given sequence

Palindromic
 Problem Description

Subsequence that is a palindrome.

Maximum Subarray Finding the contiguous subarray with the largest sum
Sum within a given one-dimensional array.

Partition Equal Determining whether it is possible to partition a given

Subset Sum set into two subsets with equal sum.

Finding the minimum cost path from the top-left corner

Minimum Cost Path
to the bottom-right corner of a given grid.

Maximum Product Finding the contiguous subarray with the largest

Subarray product within a given one-dimensional array.

Related Articles:
 Tabulation vs Memoization
 How to solve a Dynamic Programming Problem?
 Dynamic Programming Tutorial
 Top 50 Dynamic Programming Coding Problems for Interviews
 Practice problems on Dynamic Programming algorithm
8. Graph Algorithms:
Graph algorithms in data structures and algorithms (DSA) are a set of
techniques and methods used to solve problems related to graphs, which
are a collection of nodes and edges. These algorithms are designed to
perform various operations on graphs, such as searching, traversing,
finding the shortest path, and determining connectivity. They are
essential for solving a wide range of real-world problems, including
network routing, social network analysis, and resource allocation.
Algorithm’s
Topic’s
Topic Algorithm Description
Description

Graph Techniques for visiting Depth-First Explores as far as

Traversal all vertices in a graph. Search possible along each
(DFS) branch before
backtracking.
 Algorithm’s
Topic’s
Topic Algorithm Description
Description

Explores neighbor
Breadth-
vertices before
First Search
moving to the next
(BFS)
level of vertices.

It finds a minimum
spanning tree for a
connected weighted
Kruskal’s
graph. It adds the
Algorithm
Minimum Spanning smallest weight
Trees are the smallest edge that does not
trees that connect all form a cycle.
Minimum
nodes in a graph
Spanning
without forming It also finds a
Trees
cycles, achieved by minimum spanning
adding the shortest tree for a
edges possible. Prim’s connected weighted
Algorithm graph. It adds the
smallest weight
edge that connects
two trees.

Kahn’s Algorithm
finds a topological
Kahn’s
ordering of a
Algorithm
Topological sorting is directed acyclic
a linear ordering of the graph (DAG).
vertices in a directed
Topological acyclic graph (DAG)
Sorting such that for every DFS-based
directed edge from Algorithm use
vertex u to vertex v, u Depth-First Search
comes before v in the DFS-based
to perform
ordering. Algorithm
topological sorting
in a directed acyclic
graph (DAG).

Shortest Path A shortest path in a Dijkstra’s Greedy algorithm to

 Algorithm’s
Topic’s
Topic Algorithm Description
Description

find the shortest

path between all
Algorithm
nodes in O(E * V
logV) time.

Finds the shortest

Floyd-
graph is the path path between all
Warshall
between two vertices pairs of nodes in
Algorithm
in a graph that has the O(V^3) time.
minimum sum of
weights along its Finds the shortest
edges compared to all Bellman
path from a single
other paths between Ford
source in O(V * E)
the same two vertices. Algorithm
time.

Finds the shortest

paths between all
Johnson
pairs of vertices in
Algorithm
O(V^2 logV + V * E)
time.

Kosaraju’s
Algorithm is a two-
pass algorithm that
A strongly connected Kosaraju’s efficiently finds the
component (SCC) of a Algorithm strongly connected
directed graph is a components
Strongly maximal set of (SCCs) of a
Connected vertices such that directed graph.
Components there is a path from
every vertex in the set
to every other vertex Tarjan’s Algorithm
in the set. is another efficient
Tarjan’s
algorithm for finding
Algorithm
SCCs in a directed
graph

9. Pattern Searching
Pattern searching is a fundamental technique in DSA used to find
occurrences of a specific pattern within a given text.
Below are some some standard pattern searching algorithms:
 Time
Algorithm Description Complexity

It compares the pattern with every

Brute-Force O(mn)
substring of the text

Knuth- It uses a precomputed failure function to

O(m + n)
Morris-Pratt skip unnecessary comparisons

It compares the pattern from right to left,

Boyer-Moore skipping characters based on the last O(mn)
mismatch

It uses hashing to quickly check for

Rabin-Karp O(m + n)
potential matches

Related Topics:
 Pattern Searching Tutorial
 Practice Problem on Pattern Searching
10. Mathematical Algorithms
Mathematical algorithms are a class of algorithms that solve problems
related to mathematical concepts. They are widely used in various fields,
including Computer graphics, Numerical analysis, Optimization and
Cryptography.
Algorithm Description

Find the greatest common divisor and least

GCD and LCM
common multiple of two numbers.

Prime Factorization Decompose a number into its prime factors.

Generate the Fibonacci sequence, where each

Fibonacci Numbers
number is the sum of the two preceding ones.

Catalan Numbers Count the number of valid expressions with a given

 Algorithm Description

number of pairs of parentheses.

Perform arithmetic operations on numbers modulo a

Modular Arithmetic
given value.

Count the number of positive integers less than a

Euler Totient Function
given number that are relatively prime to it.

Calculate the binomial coefficient, which represents

nCr Computations the number of ways to choose r elements from a set
of n elements.

Prime Numbers and Determine whether a given number is prime and

Primality Tests find prime numbers efficiently.

Sieve Algorithms Find all prime numbers up to a given limit.

Related Topics:
 Practice Problem on Mathmatical Algorithm
11. Geometric Algorithms
Geometric algorithms are a class of algorithms that solve problems
related to geometry. Geometric algorithms are essential for solving a wide
range of problems in computer science, such as:
Algorithm Description

Finds the smallest convex polygon that contains a set of

Convex Hull
points.

Closest Pair of Finds the two points in a set that are closest to each
Points other.

Line Intersection Determines whether two lines intersect and, if so, finds
 Algorithm Description

the point of intersection.

Determines whether a given point is inside or outside a

Point in Polygon
polygon.

Related Topics:
 Practice Problem on Geometric Algorithms
12. Bitwise Algorithms
Bitwise algorithms are algorithms that operate on individual bits of
numbers. These algorithms manipulate the binary representation of
numbers to perform tasks such as bit manipulation, bitwise logical
operations (AND, OR, XOR), shifting bits, and setting or clearing
specific bits within a number. Bitwise algorithms are commonly used
in low-level programming, cryptography, and optimization
tasks where efficient manipulation of individual bits is required.
Topic Description

Shifts bits to the left or right by a specified number of

Bit Shifting
positions.

Shifts bits to the left, effectively multiplying the number by

Left shift (<<)
2.

Shifts bits to the right, effectively dividing the number by

Right shift (>>)
2.

Extract bits Using masks to extract specific bits from an integer.

Setting bits Using masks to set specific bits to 1 in an integer.

Clearing bits Using masks to set specific bits to 0 in an integer.

Toggling bits Using XOR (^) to toggle specific bits in an integer.

 Topic Description

Counting Set
Counting the number of set bits (1s) in an integer.
bits

Related Topics:
 Bitwise Algorithms Tutorial
 Practice Problem on Bitwise Algorithms
13. Randomized Algorithms
Randomized algorithms are algorithms that use randomness to solve
problems. They make use of random input to achieve their goals, often
leading to simpler or more efficient solutions.
Types of Randomized Algorithms:
 Las Vegas: Always produces a correct result, but the running time is
random.
 Monte Carlo: May produce an incorrect result with a small probability,
but the running time is usually faster.
Important Algorithms that uses Randomization Algorithms:
Algorithm Description

A randomized sorting algorithm with an average-case time

QuickSort
complexity of O(n log n).

A randomized data structure that provides fast search and

Skip List
insertion operations.

Bloom A probabilistic data structure for efficient set membership

Filter testing.

14. Branch and Bound Algorithm

The Branch and Bound Algorithm is a method used in combinatorial
optimization problems to systematically search for the best solution. It
works by dividing the problem into smaller subproblems, or branches, and
then eliminating certain branches based on bounds on the optimal
solution. This process continues until the best solution is found or all
branches have been explored.
Standard Problems on Branch and Bound Algorithm:
 Unique Problem Description

0/1 Knapsack using Implementation details of the branch and bound

Branch and Bound approach for solving the 0/1 Knapsack problem.

0/1 Knapsack using Least Solving the 0/1 Knapsack problem using the
Cost Branch and Bound least cost branch and bound technique.

8 puzzle Problem using Application of branch and bound to solve the 8

Branch and Bound puzzle problem, a popular sliding puzzle game.

Utilizing branch and bound to find solutions to

N Queen Problem using
the N Queens problem, a classic chess
Branch and Bound
problem.

Related Topics:
 Branch and Bound Algorithm Tutorial
Learn about Complexities
In Data Structures and Algorithms (DSA), the main goal is to solve
problems effectively and efficiently. To determine the efficiency of a
program, we look at two types of complexities:
1. Time Complexity: This tells us how much time our code takes to run.
2. Space Complexity: This tells us how much memory our code uses.
Asymptotic Notation:
To compare efficiencies of algorithms, we use asymptotic notation, a
mathematical tool that estimates time based on input size without
running the code. It focuses on the number of basic operations in the
program.
Notation Description

Describes the worst-case scenario, providing an upper time

Big-O (Ο)
bound of algorithm.

Omega Describes the best-case scenario, offering a lower time bound

(Ω) of algorithm.
Notation Description

Theta (θ) Represents the average complexity of an algorithm of algorithm.