DAA Exam Preparation
1. Dynamic Programming
What is Dynamic Programming?
Dynamic Programming (DP) is a technique to solve problems by breaking them into smaller parts and remembering the answers. Instead of solving the same small problem many times, we solve it once and save the answer.
Key Ideas
1. Overlapping Subproblems: Same small problems appear many times
2. Optimal Substructure: Big problem = small problems combined
3. Memoization: Remember answers to avoid recalculating
Example: Fibonacci Numbers
Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13...
function fib(n) {
if (n <= 1) return n;
return fib(n-1) + fib(n-2); // Recalculates many times!
}
// With DP (FAST - remembers answers)
function fibDP(n) {
let memo = {};
if (n in memo) return memo[n];
if (n <= 1) return n;
memo[n] = fibDP(n-1) + fibDP(n-2);
return memo[n];
}
2. 0-1 Knapsack Problem
What is the Knapsack Problem?
You have a backpack with limited space. You have items with different weights and values. You want to pick items to get maximum value without exceeding the weight limit. Each item can be taken or not taken (0 or 1).
- Laptop (2kg, worth $1000)
- Book (1kg, worth $50)
- Phone (0.5kg, worth $500)
How to Solve It
Create a table where each cell shows: "What's the best value using these items and this weight limit?" For each item, decide: Take it or skip it? Choose whichever gives more value.
items = [
{weight: 2, value: 1000}, // Laptop
{weight: 1, value: 50}, // Book
{weight: 0.5, value: 500} // Phone
];
maxWeight = 10;
// Create table to remember best values
table = new Array(items.length + 1)
.fill(0)
.map(() => new Array(maxWeight + 1).fill(0));
// Fill the table
for (let i = 1; i <= items.length; i++) {
for (let w = 1; w <= maxWeight; w++) {
if (items[i-1].weight <= w) {
// Take item or skip it - choose better option
table[i][w] = Math.max(
table[i-1][w], // Skip item
items[i-1].value + table[i-1][w - items[i-1].weight] // Take item
);
} else {
table[i][w] = table[i-1][w]; // Can't fit, skip
}
}
}
5. Graph Basics
What is a Graph?
A graph is a way to show connections between things. It has:
Nodes (Vertices): The things (like cities, people, computers)
Edges: The connections between things (like roads, friendships, cables)
- Nodes = People
- Edges = Friendships
Types of Graphs
Directed Graph: Edges have direction (one-way roads)
Undirected Graph: Edges have no direction (two-way roads)
Weighted Graph: Edges have values/costs
Unweighted Graph: All edges are equal
6. Breadth-First Search (BFS)
What is BFS?
BFS is a way to explore a graph layer by layer. Start from one node, visit all neighbors, then visit their neighbors, and so on. It's like ripples in water!
- Start at your location
- Check all nearby places (1 step away)
- Check places 2 steps away
- Keep expanding until you find your destination
How BFS Works
1. Start with a node and mark it as visited
2. Add it to a queue (like a waiting line)
3. While queue is not empty: Remove first node, visit its neighbors
4. Add unvisited neighbors to queue
5. Repeat until queue is empty
function bfs(graph, start) {
let visited = new Set();
let queue = [start];
visited.add(start);
while (queue.length > 0) {
let node = queue.shift(); // Remove from front
console.log(node);
// Visit all neighbors
for (let neighbor of graph[node]) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor); // Add to back
}
}
}
}
// Example graph
let graph = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'E'],
'D': ['B'],
'E': ['C']
};
bfs(graph, 'A'); // Output: A, B, C, D, E
7. Depth-First Search (DFS)
What is DFS?
DFS goes deep into a graph before going wide. Start from one node and keep going deeper along one path until you hit a dead end, then backtrack and try another path.
- Go down one path as far as possible
- When you hit a wall, go back
- Try a different path
- Keep exploring until you find the exit
How DFS Works
1. Start with a node and mark it as visited
2. Add it to a stack
3. While stack is not empty: Remove top node, visit its neighbors
4. Add unvisited neighbors to stack
5. Repeat until stack is empty
function dfs(graph, start) {
let visited = new Set();
let stack = [start];
while (stack.length > 0) {
let node = stack.pop(); // Remove from top
if (!visited.has(node)) {
visited.add(node);
console.log(node);
// Add all neighbors to stack
for (let neighbor of graph[node]) {
if (!visited.has(neighbor)) {
stack.push(neighbor);
}
}
}
}
}
// Or using Recursion (simpler!)
function dfsRecursive(graph, node, visited = new Set()) {
visited.add(node);
console.log(node);
for (let neighbor of graph[node]) {
if (!visited.has(neighbor)) {
dfsRecursive(graph, neighbor, visited);
}
}
}
14. Dijkstra's Algorithm
What is Dijkstra's Algorithm?
Dijkstra's algorithm finds the shortest path from one node to all other nodes in a graph. It works by always picking the closest unvisited node and updating distances to its neighbors.
- You want to drive from City A to City Z
- There are many routes with different distances
- Dijkstra finds the shortest route
How Dijkstra Works
1. Set starting distance to 0, all others to infinity
2. Pick the unvisited node with smallest distance
3. For each neighbor, if new path is shorter, update distance
4. Mark node as visited
5. Repeat until all nodes visited
function dijkstra(graph, start) {
let distances = {};
let visited = new Set();
// Initialize distances
for (let node in graph) {
distances[node] = Infinity;
}
distances[start] = 0;
while (visited.size < Object.keys(graph).length) {
// Find unvisited node with smallest distance
let current = null;
let minDist = Infinity;
for (let node in distances) {
if (!visited.has(node) && distances[node] < minDist) {
current = node;
minDist = distances[node];
}
}
if (current === null) break;
visited.add(current);
// Update distances to neighbors
for (let [neighbor, weight] of Object.entries(graph[current])) {
let newDist = distances[current] + weight;
if (newDist < distances[neighbor]) {
distances[neighbor] = newDist;
}
}
}
return distances;
}
// Example graph with weights
let graph = {
'A': {'B': 4, 'C': 2},
'B': {'A': 4, 'C': 1, 'D': 5},
'C': {'A': 2, 'B': 1, 'D': 8},
'D': {'B': 5, 'C': 8}
};
console.log(dijkstra(graph, 'A'));
// Output: {A: 0, B: 3, C: 2, D: 8}
3. Longest Common Subsequence (LCS)
What is LCS?
LCS finds the longest sequence of characters that appear in the SAME ORDER in two strings. The characters don't need to be next to each other - they just need to appear in the same order.
String 1: AGGTAB
String 2: GXTXAYB
LCS: GTAB (length 4)
Simple Example
String 1: ABCD
String 2: AEBD
LCS: ABD (length 3)
Why? A, B, D appear in same order in both strings!
How to Solve It
Create a table where each cell shows: "What's the LCS length using first i characters of string 1 and first j characters of string 2?"
Rule: If characters match, take diagonal + 1. If not, take max of left or top.
function lcs(str1, str2) {
let m = str1.length;
let n = str2.length;
let table = Array(m+1).fill(0).map(() => Array(n+1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (str1[i-1] === str2[j-1]) {
table[i][j] = table[i-1][j-1] + 1;
} else {
table[i][j] = Math.max(table[i-1][j], table[i][j-1]);
}
}
}
return table[m][n];
}
console.log(lcs("AGGTAB", "GXTXAYB")); // Output: 4
4. Bellman-Ford Algorithm
What is Bellman-Ford?
Bellman-Ford finds the shortest path from one node to all others, like Dijkstra. BUT it can handle NEGATIVE weights! Dijkstra cannot. It's slower but more powerful.
Dijkstra vs Bellman-Ford
Dijkstra: Faster, NO negative weights
Bellman-Ford: Slower, handles negative weights and detects negative cycles
How It Works
1. Set starting distance to 0, all others to infinity
2. Relax all edges (V-1) times
3. Check one more time for negative cycles
function bellmanFord(graph, start) {
let distances = {};
let nodes = Object.keys(graph);
for (let node of nodes) distances[node] = Infinity;
distances[start] = 0;
// Relax edges (V-1) times
for (let i = 0; i < nodes.length - 1; i++) {
for (let node of nodes) {
for (let [neighbor, weight] of Object.entries(graph[node])) {
if (distances[node] !== Infinity &&
distances[node] + weight < distances[neighbor]) {
distances[neighbor] = distances[node] + weight;
}
}
}
}
return distances;
}
8. Topological Sort
What is Topological Sort?
Topological Sort arranges nodes in a directed graph in a line so that for every edge from A to B, A comes BEFORE B. It only works on DAGs (no cycles).
Data Structures β Algorithms β Machine Learning
Take courses in this order!
How to Solve It
1. Do DFS from each unvisited node
2. When you finish a node, add it to a stack
3. Reverse the stack to get topological order
function topologicalSort(graph) {
let visited = new Set();
let stack = [];
function dfs(node) {
visited.add(node);
for (let neighbor of graph[node] || []) {
if (!visited.has(neighbor)) dfs(neighbor);
}
stack.push(node);
}
for (let node in graph) {
if (!visited.has(node)) dfs(node);
}
return stack.reverse();
}
9. Strongly Connected Components (SCC)
What is SCC?
A Strongly Connected Component is a group of nodes where EVERY node can reach EVERY other node by following directed edges.
Group 1: A β B β C β A (they can all message each other)
Group 2: D β E β F β D (separate group)
Simple Example
Graph: A β B β C β A (forms a cycle)
SCC: {A, B, C} (one component)
From any node, you can reach any other node!
How to Find SCCs (Kosaraju's Algorithm)
1. Do DFS, store nodes by finish time
2. Create reverse graph
3. Do DFS on reverse graph in finish time order
4. Each DFS tree is one SCC
function findSCC(graph) {
let visited = new Set();
let stack = [];
function dfs1(node) {
visited.add(node);
for (let neighbor of graph[node] || []) {
if (!visited.has(neighbor)) dfs1(neighbor);
}
stack.push(node);
}
for (let node in graph) {
if (!visited.has(node)) dfs1(node);
}
// Create reverse graph and do DFS
let reverseGraph = {};
for (let node in graph) reverseGraph[node] = [];
for (let node in graph) {
for (let neighbor of graph[node]) {
reverseGraph[neighbor].push(node);
}
}
visited.clear();
let sccs = [];
function dfs2(node, component) {
visited.add(node);
component.push(node);
for (let neighbor of reverseGraph[node]) {
if (!visited.has(neighbor)) dfs2(neighbor, component);
}
}
while (stack.length > 0) {
let node = stack.pop();
if (!visited.has(node)) {
let component = [];
dfs2(node, component);
sccs.push(component);
}
}
return sccs;
}
10. Spanning Trees & Minimum Spanning Trees
What is a Spanning Tree?
A Spanning Tree connects ALL nodes using the MINIMUM number of edges (V-1 edges for V nodes). It has no cycles and connects everything.
Need exactly 4 roads to connect all cities
All cities reachable from any other
What is a Minimum Spanning Tree (MST)?
A Minimum Spanning Tree is a spanning tree with the SMALLEST TOTAL WEIGHT. Connects all nodes with minimum edges and minimum total cost.
Simple Example
4 cities: A-B(1), A-C(4), B-C(2), B-D(5), C-D(3)
MST: A-B(1), B-C(2), C-D(3) = total cost 6
let edges = [
{from: 'A', to: 'B', weight: 1},
{from: 'A', to: 'C', weight: 4},
{from: 'B', to: 'C', weight: 2},
{from: 'B', to: 'D', weight: 5},
{from: 'C', to: 'D', weight: 3}
];
// Minimum Spanning Tree
let mst = [
{from: 'A', to: 'B', weight: 1},
{from: 'B', to: 'C', weight: 2},
{from: 'C', to: 'D', weight: 3}
];
let totalWeight = mst.reduce((sum, e) => sum + e.weight, 0);
console.log("MST Total:", totalWeight); // 6
11. Prim's Algorithm
What is Prim's Algorithm?
Prim's algorithm finds the Minimum Spanning Tree by starting with one node and gradually adding the cheapest edge that connects a new node to the tree.
Start with city A
Find cheapest road from A to others
Keep adding cheapest roads until all connected
How Prim's Works
1. Start with any node in the tree
2. Find minimum edge connecting tree to non-tree nodes
3. Add that edge and new node
4. Repeat until all nodes in tree
function prims(graph) {
let nodes = Object.keys(graph);
let inMST = new Set([nodes[0]]);
let mstEdges = [];
let totalWeight = 0;
while (inMST.size < nodes.length) {
let minEdge = null;
let minWeight = Infinity;
for (let node of inMST) {
for (let [neighbor, weight] of Object.entries(graph[node])) {
if (!inMST.has(neighbor) && weight < minWeight) {
minWeight = weight;
minEdge = {from: node, to: neighbor, weight};
}
}
}
if (minEdge) {
mstEdges.push(minEdge);
inMST.add(minEdge.to);
totalWeight += minEdge.weight;
}
}
return {edges: mstEdges, totalWeight};
}
Prim's vs Kruskal's
Prim's: Grows tree from one node
Kruskal's: Sorts edges, picks minimum that don't create cycles
Both: Find same MST
12. Kruskal's Algorithm
What is Kruskal's Algorithm?
Kruskal's algorithm finds the Minimum Spanning Tree by sorting ALL edges by weight and adding them one by one, as long as they don't create a cycle.
List all roads with costs
Sort by cost (cheapest first)
Build roads in order, skip if creates loop
How Kruskal's Works
1. Sort all edges by weight
2. For each edge: If connects different components, add it
3. If creates cycle, skip it
4. Stop when all nodes connected
class UnionFind {
constructor(nodes) {
this.parent = {};
for (let node of nodes) this.parent[node] = node;
}
find(x) {
if (this.parent[x] !== x)
this.parent[x] = this.find(this.parent[x]);
return this.parent[x];
}
union(x, y) {
let px = this.find(x), py = this.find(y);
if (px !== py) {
this.parent[px] = py;
return true;
}
return false;
}
}
function kruskals(nodes, edges) {
edges.sort((a, b) => a.weight - b.weight);
let uf = new UnionFind(nodes);
let mstEdges = [];
for (let edge of edges) {
if (uf.union(edge.from, edge.to)) {
mstEdges.push(edge);
if (mstEdges.length === nodes.length - 1) break;
}
}
return mstEdges;
}
Kruskal's vs Prim's
Kruskal's: Sort edges first, pick minimum that don't create cycles
Prim's: Grow tree from one node, pick minimum edge connected to tree
13. Single-Source Shortest Paths
What is Single-Source Shortest Path?
Single-Source Shortest Path means finding the shortest path from ONE starting node to ALL other nodes. "Shortest" means minimum total edge weight.
You're at City A
Find shortest routes to all other cities
A to B: 5km, A to C: 8km, A to D: 12km
Different Algorithms for Different Cases
Dijkstra's: NO negative weights (most common)
Bellman-Ford: WITH negative weights
BFS: Unweighted graphs
Simple Example
Graph: AβB(5), AβC(2), BβD(3), CβD(8)
Shortest from A:
A to A: 0
A to B: 5
A to C: 2
A to D: 8 (via B: 5+3)
How to Choose Algorithm
No negative weights? Use Dijkstra (faster)
Has negative weights? Use Bellman-Ford
Unweighted? Use BFS
function dijkstraShortestPath(graph, start) {
let distances = {};
let visited = new Set();
for (let node in graph) distances[node] = Infinity;
distances[start] = 0;
while (visited.size < Object.keys(graph).length) {
let current = null;
for (let node in distances) {
if (!visited.has(node) &&
(current === null || distances[node] < distances[current])) {
current = node;
}
}
if (current === null) break;
visited.add(current);
for (let [neighbor, weight] of Object.entries(graph[current])) {
if (distances[current] + weight < distances[neighbor]) {
distances[neighbor] = distances[current] + weight;
}
}
}
return distances;
}
15. 50 MCQ Practice Test
Answer all 50 questions. Each answer is revealed immediately β green = correct, red = wrong. The correct answer is always shown.