Design and Analysis of Algorithms
Assignment 3, 4 & 5 - Solutions
Assignment 3
1) The state space tree for the Four Queens problem involves placing queens row by row, avoiding
attacks. It is a tree with branches at each level representing choices of queen positions. (Detailed
diagram provided in full answer)
2) Apply Branch and Bound: Solve TSP using cost matrix and apply bounding functions. (Matrix and
tree solution in full answer)
3) Graph Coloring: Assign colors to vertices such that adjacent ones differ. Eg: Triangle graph needs
3 colors.
4/9/12/17) Same as Q1: Solved using backtracking with state space tree.
5) Duplicate of Q3.
8) Elements of Greedy Strategy: Greedy-choice property and optimal substructure. Steps: Select
best, check feasibility, repeat.
10) Sum of Subsets using backtracking: Given weights and target M=30, find subsets summing to
M.
11) Solve 15-puzzle using heuristic (like A*) approach.
13) Branch and Bound explained with example of TSP or 0/1 Knapsack.
14) Strassen's Matrix Multiplication: Divide matrices and recursively compute subproducts.
15) Merge Sort: Best and worst-case complexities are O(n log n). Apply on given array.
16) Divide & Conquer vs Dynamic Programming: D&C solves independently; DP stores intermediate
results.
18) Solve TSP using Branch and Bound (similar to Q2).
Assignment 4
1) Fractional Knapsack: Sort by value/weight ratio, pick greedily. Max profit calculated.
2/5/9) Huffman Coding: Build binary tree using frequencies, assign codes based on path.
3/8) Job Sequencing: Sort by profit and deadlines, fill latest available slots.
4) Greedy method: Make locally optimal choice hoping for global optimum.
6) 0/1 Knapsack: Use Dynamic Programming for optimal solution.
7) Minimum Cost Spanning Tree: Kruskals or Prims algorithm builds tree with min total edge weight.
10) Same as Q1 with different values.
11) Dijkstra's Algorithm: Calculates shortest path from source to all nodes.
Assignment 5
1/17) Floyd-Warshall Algorithm: Dynamic Programming for all-pairs shortest paths.
2/4/8/18) Longest Common Subsequence: Use 2D DP table to compute length and sequence.
3/16) DP vs Greedy: DP stores results; Greedy picks best immediate option.
5) Compare: Greedy (fast, not always optimal), DP (slower, optimal), D&C (split & combine).
6/10/15/19) Complexity Classes: P, NP, NP-Complete defined with examples.
7/12) Red-Black Tree: Balanced BST with coloring rules. Insert/delete may change structure.
9) Bellman-Ford: For graphs with negative weights, relax edges |V|-1 times.
11) B-Tree: Multi-way tree with ordered nodes; insertions shown step-by-step.
13) Polynomial time reduction: Transform one problem to another in polynomial time.
14) Floyd-Warshall complexity: O(V^3), DP table updated iteratively.
