1.
Depth First Search (DFS)
Definition: Depth First Search (DFS) is a graph traversal algorithm that starts from a
selected node (called the source) and explores as far as possible along each branch before
backtracking. It uses a stack-based approach, typically through recursion, to visit each
vertex and explore deeper into the graph.
Example: Consider a graph with vertices A, B, C, D, and E.
If A is connected to B and C, B is connected to D, and C is connected to E, then a DFS
traversal starting from A might look like:
A→B→D→C→E
Applications:
• Finding connected components in a graph
• Topological sorting of Directed Acyclic Graphs (DAGs)
• Solving puzzles and Detecting cycles in graphs
• Network analysis and pathfinding
Time Complexity:O(V + E) where V is the number of vertices and E is the number of
edges in the graph.
Space Complexity:O(V) to store visited nodes and recursive stack (or an explicit stack if
implemented iteratively)
Advantages:
• Requires less memory compared to Breadth First Search (BFS)
• Suitable for problems that require exploring depth-wise first
• Simple to implement using recursion
Disadvantages:
• Does not guarantee the shortest path in unweighted graphs
• May enter deep recursion, leading to stack overflow in large or cyclic graphs
• Can revisit nodes unless visited tracking is done carefully
Real-World Applications:
• Web crawlers to traverse web pages
• Solving puzzles like Sudoku or mazes
• Generating mazes and procedural maps in games
1
2
2. Breadth First Search (BFS)
Definition: Breadth First Search (BFS) is a graph traversal algorithm that explores all the
neighbor nodes at the present depth before moving on to nodes at the next depth level. It
uses a queue-based approach to ensure that the closest nodes are explored first.
Example: Consider a graph with vertices A, B, C, D, and E. If A is connected to B and C,
B is connected to D, and C is connected to E, then a BFS traversal starting from A might
look like:A → B → C → D → E
Applications:
• Finding the shortest path in unweighted graphs
• Crawling social networks or web pages
• Peer-to-peer (P2P) networks like BitTorrent
• GPS-based route finding
Time Complexity: O(V + E) where V is the number of vertices and E is the number of
edges in the graph.
Space Complexity: O(V) for storing visited nodes and the queue used for traversal.
Advantages:
• Guarantees the shortest path in unweighted graphs
• Works well for closer/shallower solutions
• Can be used to detect bipartite graphs
Disadvantages:
• Consumes more memory than DFS due to the use of a queue
• Can be slower than DFS for deep graphs
• Not suitable for scenarios requiring depth-based exploration
Real-World Applications:
• GPS systems for finding shortest paths
• Social media friend suggestions
3
4
3. 0/1 Knapsack Problem
Definition: The 0/1 Knapsack Problem is a classic dynamic programming problem where we are
given a set of items, each with a weight and a value, and a knapsack with a weight capacity. The
goal is to determine the maximum value that can be obtained by selecting a subset of items such that
the total weight does not exceed the knapsack's capacity. Each item can either be included (1) or
excluded (0) — hence the name 0/1
Example: Suppose we have 3 items with the following weights and values:(Knapsack Capacity = 5)
• Item 1: Weight = 2, Value = 10
• Item 2: Weight = 3, Value = 20
• Item 3: Weight = 4, Value = 30
The optimal selection is Item 2 only (Weight = 3, Value = 20), or Items 1 and 2 (Weight = 5, Value =
30) depending on value and capacity combinations.
Applications:
• Resource allocation in project planning
• Cargo loading problems
• Investment decisions under constraints
Time Complexity: O(n × W) where n is the number of items and W is the capacity of the knapsack.
Space Complexity: O(n × W) for the dynamic programming table (Optimized to O(W) using 1D
array in some implementations)
Advantages:
• Solves optimization problems efficiently with dynamic programming
• Provides exact maximum value for limited capacity
• Can be applied to many real-world constrained selection problems
Disadvantages:
• Not suitable for large capacity values due to high space/time complexity
• Only applicable where items are indivisible
• Requires dynamic programming, which can be complex to implement for beginners
Real-World Applications:
• Resource scheduling in cloud computing
• Portfolio optimization in finance
• Data storage selection problems
5
6
4. Dijkstra's Algorithm
Definition: Dijkstra’s Algorithm is a greedy algorithm used to find the shortest path from
a single source vertex to all other vertices in a weighted graph with non-negative edge
weights. It works by always selecting the vertex with the smallest known distance and
updating the distances of its adjacent vertices.
Example: Consider a graph with vertices A, B, C, and D, where:
• A–B has weight 1
• A–C has weight 4
• B–C has weight 2
• C–D has weight 1
Starting from A, the shortest path to D would be: A → B → C → D with total weight
1+2+1 = 4.
Applications:
• GPS and navigation systems for shortest route calculations
• Flight itinerary system
Time Complexity: Using a simple array: O(V²) .Using a binary heap with adjacency list:
O((V + E) log V)
Space Complexity: O(V) for the distance and visited arrays, and possibly more for
priority queues or heaps.
Advantages:
• Guarantees shortest path in graphs with non-negative weights
• Works efficiently for sparse graphs with binary heaps
• Widely applicable in real-time systems
Disadvantages:
• Cannot handle graphs with negative weight edges
• Slower on very large graphs with dense connections
Real-World Applications:
• Google Maps and GPS-based shortest route estimation
• Internet routing (like in OSPF protocol)
7
8
5. Floyd-Warshall Algorithm
Definition: The Floyd-Warshall Algorithm is a dynamic programming algorithm used to
find the shortest paths between all pairs of vertices in a weighted graph. It works for
both directed and undirected graphs and can handle positive and negative edge weights
(but no negative weight cycles).
Example: Given a graph with 4 vertices and the following edge weights:
• A–B = 3
• B–C = 1
• A–C = 10
• C–D = 2
The Floyd-Warshall algorithm will update the shortest distance between every pair of
vertices by considering each vertex as an intermediate [Link] shortest distance from
A to D: A → B → C → D = 3 + 1 + 2 = 6
Applications:
• Computing shortest paths in dense graphs
• Network routing and traffic analysis
• Game development for navigation between all points
Time Complexity: O(V³) where V is the number of vertices
Space Complexity: O(V²) for storing the distance matrix
Advantages:
• Simple and elegant dynamic programming solution
• Works for graphs with negative weights (no negative cycles)
• Provides shortest path between all pairs of nodes
Disadvantages:
• High time complexity makes it inefficient for large graphs
• Cannot detect negative weight cycles unless modified
• Not suitable for sparse graphs compared to Dijkstra's for single-source
Real-World Applications:
• Urban traffic systems with all-route shortest path planning
• Airline flight planning between multiple cities
9
10
6. N-Queens Problem
Definition: The N-Queens Problem is a classic backtracking problem where the goal is to
place N queens on an N×N chessboard such that no two queens threaten each other.
That means no two queens share the same row, column, or diagonal.
Example: For N = 4, one possible solution is placing queens at positions:
• (1,2), (2,4), (3,1), (4,3)
Each queen is placed such that none attack each other, satisfying the constraints of
the problem.
Applications:
• Testing and demonstrating backtracking algorithms
• Constraint satisfaction problems
• AI techniques like game tree search
• Scheduling problems with constraints
• Parallel and distributed computing concepts
Time Complexity: O(N!) in the worst case, due to factorial growth in the number of
possible arrangements
Space Complexity: O(N) for the recursion stack and placement tracking array
Advantages:
• Excellent problem to understand backtracking and recursion
• Helps improve algorithmic thinking
• Can be optimized using techniques like pruning and bit masking
Disadvantages:
• Becomes computationally expensive as N increases
• Requires careful handling of recursive calls and constraints
• Limited direct real-world applications (used more for educational purposes)
Real-World Applications:
• Solving Sudoku and other constraint-based puzzles
• Register allocation in compilers
• Placing antennas or sensors without interference
• Testing AI logic in games and simulations
• Allocating non-overlapping resources in grids
11
12
7. Travelling Salesman Problem (TSP)
Definition: The Travelling Salesman Problem (TSP) is a well-known optimization
problem in which a salesman is given a set of cities and must determine the shortest
possible route that allows him to visit each city once and return to the origin city. The
goal is to minimize the total distance travelled.
Example: Consider a set of 4 cities: A, B, C, and D, with the following distance matrix:
The task is to find the shortest route that visits all cities once and returns to the starting
city. One such route could be: A → B → D → C → A, with a total distance of 10 + 25 +
30 + 15 = 80.
Applications:
• Logistics and route planning (e.g., delivery optimization)
• DNA sequencing in bioinformatics
• Aircraft flight planning for multiple destinations
Time Complexity: O(n!) in the brute-force approach, as the problem explores all
possible permutations of cities
For approximate algorithms (e.g., Genetic Algorithms, Simulated Annealing), the
complexity depends on the specific method used
Space Complexity: O(n) for storing distances and current routes
Advantages:
• Provides valuable insights for real-world optimization problems
• Applicable to various fields, including logistics, and network optimization
• Can be solved exactly for small instances, providing an optimal solution
Disadvantages:
• Computationally expensive, making it infeasible for large numbers of cities
• Requires approximations or heuristics for large-scale problems
Real-World Applications:
• Delivery route optimization for companies like FedEx and UPS
• Airline flight scheduling and network routing
• Drone delivery route planning
13
14