Design and Analysis of Algorithms (DAA) – Exam Theory Notes (What to Write in

Exam)

✅ 1. What is Algorithm? Explain criteria of Algorithms.

An algorithm is a step-by-step finite set of instructions used to solve a specific problem. It must be clear,
unambiguous, and terminate after a finite number of steps.

Criteria of a good algorithm: 1. Input: Must have zero or more inputs. 2. Output: Must produce at
least one output. 3. Finiteness: Algorithm must terminate after a finite number of steps. 4.
Effectiveness: Each step must be simple and feasible. 5. Definiteness: Every step should be precisely
defined.

✅ 2. Asymptotic Notations (Big-O, Big-Theta, Big-Omega)

Asymptotic notations are mathematical tools used to describe the time and space complexity of an
algorithm in terms of input size (n).

• Big-O (O): Upper bound (worst-case scenario). Example: O(n²)

✅ 3. Max and Min Heap + Insertion Algorithm

• Max Heap: A complete binary tree where each parent node is greater than or equal to its
children.
• Min Heap: A complete binary tree where each parent node is less than or equal to its children.

Insertion Algorithm: 1. Insert the new element at the end (last position). 2. Compare it with its parent.
3. If it violates heap property, swap and repeat (heapify up).

✅ 4. Binary Search + Time Complexity

Binary search is used to search a key in a sorted array. It divides the search space into half in each step.

Algorithm Steps: 1. Find the middle element. 2. If key = mid element → found. 3. If key < mid → search
in left half. 4. If key > mid → search in right half.

Time Complexity: Best - O(1), Worst - O(log n)

✅ 5. Quick Sort + Performance

Quick Sort is a sorting technique based on divide-and-conquer.

1
Steps: 1. Choose a pivot. 2. Partition the array: elements < pivot on left, > pivot on right. 3. Recursively
apply to sub-arrays.

Time Complexity: - Best/Average: O(n log n) - Worst: O(n²) (if pivot is smallest/largest repeatedly)

✅ 6. Strassen’s Matrix Multiplication

Strassen’s algorithm is a fast matrix multiplication method using divide and conquer.

• Reduces number of multiplications from 8 to 7.

Advantages: Faster for large matrices. Limitations: More complex, not practical for small matrices.

✅ 7. Four Queens Problem – State Space Tree

It is a backtracking problem where we place 4 queens on a 4×4 chessboard such that no two queens
attack each other.

Steps: - Place queens row by row. - For each row, try placing in safe columns. - If no safe position,
backtrack.

Draw a tree showing placements and backtracking.

✅ 8. Graph Coloring Problem

Graph coloring assigns colors to graph vertices such that no adjacent vertices share the same color.

Backtracking Algorithm: 1. Assign color to vertex. 2. Check for conflicts. 3. If valid, go to next vertex. 4.
Else, backtrack.

✅ 9. Branch and Bound (TSP/15 Puzzle)

It is used to find the optimal solution in decision problems.

Steps: - Generate tree of all possible solutions. - Use bound function to eliminate subtrees. - Continue
until best solution is found.

Used in TSP, 15-puzzle, and 0/1 knapsack.

2
✅ 10. 0/1 Knapsack (Given instance solved)

Use Dynamic Programming to build a table for max profit for weights from 0 to W.

• Fill table using: dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i]] + val[i])

✅ 11. Minimum Spanning Tree (MST)

A tree that connects all vertices with the minimum total edge weight and no cycles.

Prim’s Algorithm: - Start with one node. - Add smallest edge connecting visited to unvisited.

Kruskal’s Algorithm: - Sort all edges by weight. - Add edge if it doesn’t form a cycle (use union-find).

✅ 12. Job Sequencing with Deadlines

Schedule jobs with deadlines and profits to maximize total profit.

Steps: 1. Sort jobs by descending profit. 2. For each job, schedule it in the latest available time slot
before its deadline. 3. Track filled slots and calculate total profit.

✅ 13. Floyd-Warshall (DP)

Used for finding all-pairs shortest path in a weighted graph.

Algorithm Steps: - Initialize distance matrix. - For every vertex k: - For every pair (i, j): dist[i][j] =
min(dist[i][j], dist[i][k] + dist[k][j])

✅ 14. Complexity Class P vs NP

• P: Problems solvable in polynomial time.

✅ 15. DP vs Greedy

Feature Dynamic Programming Greedy Algorithm

Optimal Global Local

Use Overlapping subproblems Best immediate option

Examples 0/1 Knapsack, LCS Activity Selection, Fractional Knapsack

3
✅ 16. Merge Sort Dry Run

• Divide array into halves recursively.

Example: [13, 4, 22, 1,16, 9,0,2] → Sorted output: [0,1,2,4,9,13,16,22]

✅ 17. Master Theorem Solutions

Use formula: T(n) = aT(n/b) + f(n) - Compare f(n) with n^log_b a - Apply one of the 3 cases: 1. f(n) <
n^log_b a → O(n^log_b a) 2. f(n) = n^log_b a → O(n^log_b a log n) 3. f(n) > n^log_b a → O(f(n)) if
regularity holds

✅ 18. Greedy Activity Selection (Given 10 activities)

Steps: 1. Sort activities by finish time. 2. Select the first activity. 3. For each activity, if start ≥ finish of
last selected, add it.

Result: Maximum number of non-overlapping activities.

✅ 19. Dijkstra vs Bellman-Ford

Feature Dijkstra Bellman-Ford

Edge Weights Only positive Can be negative

Complexity O(V log V + E) O(VE)

Negative Cycles Not detected Detected

✅ 20. LCS (Longest Common Subsequence)

Given X and Y, construct a DP table: - If X[i] = Y[j] → dp[i][j] = dp[i-1][j-1] + 1 - Else dp[i][j] = max(dp[i-1][j],
dp[i][j-1])

Result = value at dp[m][n]

✅ 21. Huffman Coding (Given data)

Steps: 1. Build min heap of frequencies. 2. Repeat until one tree remains: - Remove 2 smallest nodes. -
Merge them into new node. 3. Assign 0 to left, 1 to right.

Result: Binary codes for each character.

4
✅ 22. Fractional Knapsack (Greedy)

Steps: 1. Calculate value/weight for each item. 2. Sort by value/weight. 3. Take full items until capacity
full. 4. Take fraction if needed.

Result = Total profit

✅ 23. 4-Queens Problem – Backtracking

Place 4 queens row by row ensuring no conflicts in column or diagonals. Draw state space tree to show
decisions and backtracking.

✅ 24. Backtracking vs Branch and Bound

Feature Backtracking Branch and Bound

Goal Feasibility Optimality

Pruning Constraint-based Cost-based bound

Use Cases N-Queens, Graph Coloring TSP, 15-Puzzle, Knapsack

End of Theory Notes