Design and Analysis of Algorithms (DAA) – Exam Theory Notes (Concept + What to
Write in Exam)
1. Binary Search
Concept: Binary Search is an efficient method to find an element in a sorted array. It uses a divide-and-
conquer approach by repeatedly dividing the search interval in half.
Theory to Write: Binary Search is used to search an element in a sorted array. It compares the target
value with the middle element of the array. If they are not equal, the half in which the target cannot lie
is eliminated, and the search continues on the remaining half.
Time Complexity: Best - O(1), Worst - O(log n)
Use Case: Searching in dictionaries, sorted databases.
2. Merge Sort
Concept: A divide-and-conquer sorting algorithm that splits the array into halves, recursively sorts
them, and merges the sorted halves.
Theory to Write: Merge Sort divides the array into two halves and recursively sorts them. Then it
merges the two sorted halves into a final sorted array. It is a stable and efficient sorting algorithm.
Time Complexity: O(n log n)
Use Case: External sorting (sorting large files).
3. Quick Sort
Concept: A divide-and-conquer algorithm that selects a pivot and partitions the array into two halves
such that one half has elements less than the pivot and the other has elements greater.
Theory to Write: Quick Sort picks a pivot element and partitions the array. It then recursively applies
the same to the left and right subarrays. Though worst case is O(n^2), it's fast in practice.
Time Complexity: Average - O(n log n), Worst - O(n²)
Use Case: In-place sorting of large datasets.
4. Hamiltonian Cycle
Concept: A cycle that visits each vertex of a graph exactly once and returns to the starting point.
1
Theory to Write: Hamiltonian Cycle is a backtracking algorithm that checks whether such a cycle exists
in the given graph. It is an NP-complete problem.
Time Complexity: O(n!)
Use Case: Traveling and routing problems.
5. Minimum Spanning Tree (MST)
Concept: A spanning tree of a graph with minimum total edge weight.
Theory to Write: MST is a subset of edges connecting all vertices with minimum cost and no cycles.
Two main algorithms: - Prim’s: Grows MST one vertex at a time. - Kruskal’s: Adds smallest edge avoiding
cycles using Union-Find.
Time Complexity: Prim's - O(V²), Kruskal's - O(E log E)
Use Case: Network design, circuit layout.
6. Dijkstra’s Algorithm
Concept: Finds shortest path from a source to all other nodes in a graph with non-negative weights.
Theory to Write: Dijkstra’s algorithm initializes distances to all nodes as infinity and source as 0. It uses
a priority queue to pick the node with the shortest distance and updates its neighbors.
Time Complexity: O(V²) or O((V + E) log V)
Use Case: GPS navigation, routing.
7. Bellman-Ford Algorithm
Concept: Finds shortest path from source to all vertices even with negative edge weights.
Theory to Write: It works by relaxing all edges V-1 times. After that, it checks for negative-weight
cycles. It is slower than Dijkstra but handles negative weights.
Time Complexity: O(VE)
Use Case: Currency arbitrage detection.
8. Floyd-Warshall Algorithm
Concept: Finds shortest paths between all pairs of vertices.
2
Theory to Write: Floyd-Warshall uses dynamic programming. It updates distance[i][j] with the
minimum of current value or the value through an intermediate vertex.
Time Complexity: O(V³)
Use Case: All-pairs shortest path in dense graphs.
9. Strassen’s Matrix Multiplication
Concept: A fast matrix multiplication algorithm using divide and conquer.
Theory to Write: Strassen’s algorithm divides matrices into 4 submatrices and performs 7
multiplications instead of 8. This reduces the overall complexity compared to standard matrix
multiplication.
Time Complexity: O(n^2.81)
Use Case: Fast matrix operations in graphics and ML.
10. N-Queens Problem
Concept: Place N queens on an N×N chessboard such that no two queens attack each other.
Theory to Write: It uses backtracking to try placing a queen in each row, checking for safe positions in
columns and diagonals. If a conflict occurs, it backtracks and tries the next possibility.
Time Complexity: O(N!)
Use Case: Puzzle-solving, AI problems.
11. Sum of Subsets
Concept: Find all subsets of numbers that sum to a given target value.
Theory to Write: It uses backtracking to explore all subsets. At each step, we either include or exclude
the current element and check if the target sum is achieved.
Time Complexity: O(2^n)
Use Case: Knapsack-like problems.
12. Graph Coloring
Concept: Assign colors to vertices such that no two adjacent vertices share the same color.
3
Theory to Write: It uses backtracking to assign colors to each vertex. If the current color assignment is
not valid, it backtracks and tries another color.
Time Complexity: O(m^n)
Use Case: Scheduling, map coloring.
13. Travelling Salesperson Problem (TSP - Branch & Bound)
Concept: Find the shortest possible route that visits every city once and returns to the origin.
Theory to Write: TSP is solved using Branch and Bound or Dynamic Programming. B&B keeps track of
lower bound costs and prunes paths that exceed the best solution.
Time Complexity: O(n!)
Use Case: Logistics, route planning.
14. 15-Puzzle Problem
Concept: Solve a 4×4 sliding puzzle to reach a goal configuration.
Theory to Write: Uses Branch and Bound or A* with a heuristic (like Manhattan distance). The
algorithm finds the least cost path to the goal state.
Time Complexity: Depends on heuristic, exponential in worst case.
Use Case: Game development, AI search.
15. Huffman Coding
Concept: A compression technique using variable-length binary codes for characters.
Theory to Write: Build a min-heap of character frequencies. Construct a binary tree where each
character gets a code: left = 0, right = 1. Most frequent characters get shortest codes.
Time Complexity: O(n log n)
Use Case: File compression (ZIP, JPEG).
16. Knapsack Problem
Concept: Select items with max total value under a weight limit.
4
Theory to Write: - 0/1 Knapsack: Use Dynamic Programming to solve by building a table of max value
for weight limits. - Fractional Knapsack: Use greedy approach by choosing items with max value/weight
ratio.
Time Complexity: DP - O(nW), Greedy - O(n log n)
Use Case: Resource allocation, budgeting.
17. Activity Selection Problem
Concept: Select max number of activities that don’t overlap.
Theory to Write: Sort activities by finish time. Select the activity that finishes first and is compatible
with the last selected one. Repeat.
Time Complexity: O(n log n)
Use Case: Scheduling tasks or meetings.
18. Job Sequencing Problem
Concept: Schedule jobs to maximize profit within deadlines.
Theory to Write: Sort jobs by decreasing profit. Assign each job to the latest available slot before its
deadline.
Time Complexity: O(n log n)
Use Case: Task scheduling, manufacturing.
19. Longest Common Subsequence (LCS)
Concept: Find the longest sequence present in both strings in the same order.
Theory to Write: Use Dynamic Programming to build a 2D table where each entry represents the LCS
length of substrings.
Time Complexity: O(m × n)
Use Case: Diff tools, DNA sequence matching.
5
20. NP Problems
Concept: - P: Problems solvable in polynomial time. - NP: Problems verifiable in polynomial time. - NP-
Complete: Hardest problems in NP; if one is solved, all NP problems can be solved in P. - NP-Hard: As
hard as NP-Complete, but not necessarily verifiable in polynomial time.
Example: TSP is NP-Complete.
Use Case: Complexity analysis, cryptography.
End of Notes
