21CS42 Dayananda Sagar University • Computer Science & Engineering (Semester 4)

Design and Analysis of Algorithms

💡 DSU Exam Strategy & Guidance

Master Theorem for recurrences, Divide-and-Conquer (Merge/Quick sort), Dynamic Programming (0/1 Knapsack, LCS), and Greedy strategies (Huffman Coding, Kruskal/Prim).

High-Yield Passing Strategy: Always provide Pseudocode + Recurrence relation + Time Complexity proof.
Most Repeated Question Topics:
Master Theorem Recurrences0/1 Knapsack Problem (DP vs Greedy)Longest Common Subsequence (LCS)Kruskal and Prim Minimum Spanning TreesNP-Complete vs NP-Hard Definitions

🔥 Most Predictable Exam Questions (2)

Guaranteed Every Year 8 Marks Module 3: Dynamic Programming

Q1. Solve the 0/1 Knapsack Problem using Dynamic Programming for capacity W = 5 and items: Item 1 (weight 2, value 12), Item 2 (weight 1, value 10), Item 3 (weight 3, value 20), Item 4 (weight 2, value 15). Build the complete DP table and find selected items.

Key Points: Recurrence: V[i, w] = max(V[i-1, w], V[i-1, w - w_i] + v_i). Build (4+1) x (5+1) matrix. Max value = 37 (Items 2, 4, 3).

95% Probability 8 Marks Module 1: Asymptotic Analysis

Q2. State Master Theorem for divide-and-conquer recurrences T(n) = a T(n/b) + f(n). Solve: (i) T(n) = 4T(n/2) + n, (ii) T(n) = 2T(n/2) + n log n, (iii) T(n) = 3T(n/4) + n^2.

Key Points: Compare f(n) with n^(log_b a). (i) a=4, b=2 => n^(log_2 4) = n^2. f(n)=n => Case 1 => Theta(n^2). (ii) a=2, b=2 => n^1. f(n) = n log n => Extended Case 2 => Theta(n log^2 n). (iii) a=3, b=4 => n^(log_4 3) ~ n^0.79. f(n)=n^2 => Case 3 => Theta(n^2).

🎓 Open Source Courses & Video Playlists (3)

MIT OpenCourseWare

MIT 6.046J: Design and Analysis of Algorithms

Watch Course ↗
YouTube (Abdul Bari)

Abdul Bari: Algorithms Full Playlists

Watch Course ↗
Stanford Online

Stanford CS161: Design and Analysis of Algorithms

Watch Course ↗

📄 Previous Year Question Papers (2)

END_SEM • 2024

End Semester Exam 2024

View PDF ↗
END_SEM • 2023

End Semester Exam 2023

View PDF ↗

Turn 21CS42 Notes into AI Flashcards

Upload your Design and Analysis of Algorithms lecture slides to generate spaced repetition study cards in seconds.

Start Free →
MindFlow
DSU Hub Sign In

Structured Active Recall for Complex Coursework.

Turn your lecture PDFs into flashcards, adaptive quizzes, and spaced repetition reviews in seconds.

Start Free Sprint →