============================================================================= DAA Internal Exam - Algorithm Study Content (with Programs) ============================================================================= -- @BEGIN: MERGE_SORT_PROGRAM -- Write a C program to implement Merge Sort algorithm for sorting a list of integers in ascending order. -- Keywords: merge sort program, merge sort C code, merge function, mergeSort function, divide and conquer #include void merge(int arr[], int l, int m, int r) { int n1 = m - l + 1; int n2 = r - m; int L[n1], R[n2]; for (int i = 0; i < n1; i++) L[i] = arr[l + i]; for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j]; int i = 0, j = 0, k = l; while (i < n1 && j < n2) { if (L[i] <= R[j]) arr[k++] = L[i++]; else arr[k++] = R[j++]; } while (i < n1) arr[k++] = L[i++]; while (j < n2) arr[k++] = R[j++]; } void mergeSort(int arr[], int l, int r) { if (l < r) { int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); merge(arr, l, m, r); } } void printArray(int arr[], int size) { for (int i = 0; i < size; i++) printf("%d ", arr[i]); printf("\n"); } int main() { int n; printf("Enter number of elements: "); scanf("%d", &n); int arr[n]; printf("Enter %d elements: ", n); for (int i = 0; i < n; i++) scanf("%d", &arr[i]); printf("Given array:\n"); printArray(arr, n); mergeSort(arr, 0, n - 1); printf("Sorted array:\n"); printArray(arr, n); return 0; } -- @END: MERGE_SORT_PROGRAM -- @BEGIN: MERGE_SORT_PSEUDOCODE -- Write the pseudocode for Merge Sort. -- Keywords: merge sort pseudocode, function mergeSort, function merge, left sublist, right sublist function mergeSort(arr, l, r): if l >= r: return m = l + (r - l) / 2 mergeSort(arr, l, m) mergeSort(arr, m + 1, r) merge(arr, l, m, r) function merge(arr, l, m, r): L = arr[l..m], R = arr[m+1..r] i = 0, j = 0, k = l while i < len(L) and j < len(R): if L[i] <= R[j]: arr[k++] = L[i++] else: arr[k++] = R[j++] copy remaining L and R into arr -- @END: MERGE_SORT_PSEUDOCODE -- @BEGIN: MERGE_SORT_COMPLEXITY -- What is the time and space complexity of Merge Sort? -- Keywords: merge sort complexity, O(n log n), stable sort, space complexity O(n) | Case | Time | |---------|-------------| | Best | O(n log n) | | Average | O(n log n) | | Worst | O(n log n) | | Space | O(n) | Stable: Yes (equal elements keep original order) -- @END: MERGE_SORT_COMPLEXITY -- @BEGIN: QUICK_SORT_PROGRAM -- Write a C program to implement Quick Sort algorithm for sorting a list of integers in ascending order. -- Keywords: quick sort program, quick sort C code, partition function, swap, pivot #include void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; } int partition(int arr[], int low, int high) { int pivot = arr[high]; int i = low - 1; for (int j = low; j < high; j++) { if (arr[j] < pivot) { i++; swap(&arr[i], &arr[j]); } } swap(&arr[i + 1], &arr[high]); return i + 1; } void quickSort(int arr[], int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } void printArray(int arr[], int size) { for (int i = 0; i < size; i++) printf("%d ", arr[i]); printf("\n"); } int main() { int n; printf("Enter number of elements: "); scanf("%d", &n); int arr[n]; printf("Enter %d elements: ", n); for (int i = 0; i < n; i++) scanf("%d", &arr[i]); printf("Given array:\n"); printArray(arr, n); quickSort(arr, 0, n - 1); printf("Sorted array:\n"); printArray(arr, n); return 0; } -- @END: QUICK_SORT_PROGRAM -- @BEGIN: QUICK_SORT_PSEUDOCODE -- Write the pseudocode for Quick Sort and Partition. -- Keywords: quick sort pseudocode, function partition, swap, pivot, index i function quickSort(arr, low, high): if low >= high: return pi = partition(arr, low, high) quickSort(arr, low, pi - 1) quickSort(arr, pi + 1, high) function partition(arr, low, high): pivot = arr[high] i = low - 1 for j = low to high - 1: if arr[j] < pivot: swap(arr[++i], arr[j]) swap(arr[i + 1], arr[high]) return i + 1 -- @END: QUICK_SORT_PSEUDOCODE -- @BEGIN: QUICK_SORT_COMPLEXITY -- What is the time and space complexity of Quick Sort? -- Keywords: quick sort complexity, O(n log n), O(n^2) worst case, unstable sort | Case | Time | |---------|-------------| | Best | O(n log n) | | Average | O(n log n) | | Worst | O(n^2) | | Space | O(log n) | Worst case: Already sorted array with last-element pivot. Stable: No -- @END: QUICK_SORT_COMPLEXITY -- @BEGIN: MERGE_VS_QUICK -- Compare Merge Sort and Quick Sort. -- Keywords: merge sort vs quick sort, comparison, stable, space, worst case | Feature | Merge Sort | Quick Sort | |---------------|-----------------|-----------------| | Strategy | Divide & Conquer| Divide & Conquer| | Time (all) | O(n log n) | O(n log n)/O(n^2)| | Space | O(n) | O(log n) | | Stable | Yes | No | | Worst case | Never occurs | Sorted input | -- @END: MERGE_VS_QUICK -- @BEGIN: STRASSEN_PROGRAM -- Write a C program to implement Strassen's matrix multiplication algorithm. -- Keywords: strassen program, strassen C code, matrix multiplication, divide and conquer, 7 products #include void add(int n, int a[n][n], int b[n][n], int result[n][n]) { for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) result[i][j] = a[i][j] + b[i][j]; } void sub(int n, int a[n][n], int b[n][n], int result[n][n]) { for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) result[i][j] = a[i][j] - b[i][j]; } void divide(int n, int a[n][n], int c[n/2][n/2], int row, int col) { for (int i = 0, i2 = row; i < n/2; i++, i2++) for (int j = 0, j2 = col; j < n/2; j++, j2++) c[i][j] = a[i2][j2]; } void join(int n, int result[n][n], int c[n/2][n/2], int row, int col) { for (int i = 0, i2 = row; i < n/2; i++, i2++) for (int j = 0, j2 = col; j < n/2; j++, j2++) result[i2][j2] = c[i][j]; } void multiply(int n, int a[n][n], int b[n][n], int result[n][n]) { if (n == 2) { int p1 = (a[0][0] + a[1][1]) * (b[0][0] + b[1][1]); int p2 = (a[1][0] + a[1][1]) * b[0][0]; int p3 = a[0][0] * (b[0][1] - b[1][1]); int p4 = a[1][1] * (b[1][0] - b[0][0]); int p5 = (a[0][0] + a[0][1]) * b[1][1]; int p6 = (a[1][0] - a[0][0]) * (b[0][0] + b[0][1]); int p7 = (a[0][1] - a[1][1]) * (b[1][0] + b[1][1]); result[0][0] = p1 + p4 - p5 + p7; result[0][1] = p3 + p5; result[1][0] = p2 + p4; result[1][1] = p1 + p3 - p2 + p6; return; } int a11[n/2][n/2], a12[n/2][n/2], a21[n/2][n/2], a22[n/2][n/2]; int b11[n/2][n/2], b12[n/2][n/2], b21[n/2][n/2], b22[n/2][n/2]; divide(n, a, a11, 0, 0); divide(n, a, a12, 0, n/2); divide(n, a, a21, n/2, 0); divide(n, a, a22, n/2, n/2); divide(n, b, b11, 0, 0); divide(n, b, b12, 0, n/2); divide(n, b, b21, n/2, 0); divide(n, b, b22, n/2, n/2); int t1[n/2][n/2], t2[n/2][n/2]; int p1[n/2][n/2], p2[n/2][n/2], p3[n/2][n/2], p4[n/2][n/2]; int p5[n/2][n/2], p6[n/2][n/2], p7[n/2][n/2]; add(n/2, a11, a22, t1); add(n/2, b11, b22, t2); multiply(n/2, t1, t2, p1); add(n/2, a21, a22, t1); multiply(n/2, t1, b11, p2); sub(n/2, b12, b22, t1); multiply(n/2, a11, t1, p3); sub(n/2, b21, b11, t1); multiply(n/2, a22, t1, p4); add(n/2, a11, a12, t1); multiply(n/2, t1, b22, p5); sub(n/2, a21, a11, t1); add(n/2, b11, b12, t2); multiply(n/2, t1, t2, p6); sub(n/2, a12, a22, t1); add(n/2, b21, b22, t2); multiply(n/2, t1, t2, p7); int c11[n/2][n/2], c12[n/2][n/2], c21[n/2][n/2], c22[n/2][n/2]; int r1[n/2][n/2], r2[n/2][n/2]; add(n/2, p1, p4, r1); sub(n/2, r1, p5, r2); add(n/2, r2, p7, c11); add(n/2, p3, p5, c12); add(n/2, p2, p4, c21); add(n/2, p1, p3, r1); sub(n/2, r1, p2, r2); add(n/2, r2, p6, c22); join(n, result, c11, 0, 0); join(n, result, c12, 0, n/2); join(n, result, c21, n/2, 0); join(n, result, c22, n/2, n/2); } int main() { int n; printf("Enter order of matrices (power of 2): "); scanf("%d", &n); int a[n][n], b[n][n], result[n][n]; printf("Enter first matrix (%dx%d):\n", n, n); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%d", &a[i][j]); printf("Enter second matrix (%dx%d):\n", n, n); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%d", &b[i][j]); multiply(n, a, b, result); printf("Result:\n"); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) printf("%d\t", result[i][j]); printf("\n"); } return 0; } -- @END: STRASSEN_PROGRAM -- @BEGIN: STRASSEN_FORMULAS -- Write the 7 product formulas and result quadrant formulas for Strassen's algorithm. -- Keywords: strassen formulas, P1 P2 P3 P4 P5 P6 P7, C11 C12 C21 C22, A11 A12 A21 A22 P1 = (A11 + A22)(B11 + B22) P2 = (A21 + A22)(B11) P3 = (A11)(B12 - B22) P4 = (A22)(B21 - B11) P5 = (A11 + A12)(B22) P6 = (A21 - A11)(B11 + B12) P7 = (A12 - A22)(B21 + B22) C11 = P1 + P4 - P5 + P7 C12 = P3 + P5 C21 = P2 + P4 C22 = P1 + P3 - P2 + P6 -- @END: STRASSEN_FORMULAS -- @BEGIN: STRASSEN_PSEUDOCODE -- Write the pseudocode for Strassen's Matrix Multiplication. -- Keywords: strassen pseudocode, function strassen, divide, join, base case n=2 function strassen(A, B, n): if n == 2: P1 = (A11+A22)(B11+B22); P2 = (A21+A22)(B11) P3 = A11(B12-B22); P4 = A22(B21-B11) P5 = (A11+A12)(B22); P6 = (A21-A11)(B11+B12) P7 = (A12-A22)(B21+B22) C11 = P1+P4-P5+P7; C12 = P3+P5 C21 = P2+P4; C22 = P1+P3-P2+P6 return C divide A, B into quadrants P1 = strassen(A11+A22, B11+B22, n/2) P2 = strassen(A21+A22, B11, n/2) P3 = strassen(A11, B12-B22, n/2) P4 = strassen(A22, B21-B11, n/2) P5 = strassen(A11+A12, B22, n/2) P6 = strassen(A21-A11, B11+B12, n/2) P7 = strassen(A12-A22, B21+B22, n/2) return join(P1+P4-P5+P7, P3+P5, P2+P4, P1+P3-P2+P6) -- @END: STRASSEN_PSEUDOCODE -- @BEGIN: STRASSEN_COMPLEXITY -- What is the recurrence relation and complexity of Strassen's algorithm? -- Keywords: strassen complexity, T(n) = 7T(n/2) + O(n^2), O(n^2.81), log2(7) Recurrence: T(n) = 7T(n/2) + O(n^2) By Master Theorem: O(n^log2(7)) ≈ O(n^2.81) Standard: O(n^3) with 8 multiplications per level Strassen: O(n^2.81) with 7 multiplications per level -- @END: STRASSEN_COMPLEXITY -- @BEGIN: DIJKSTRA_PROGRAM -- Write a C program to implement Dijkstra's algorithm for the single source shortest path problem. -- Keywords: dijkstra program, dijkstra C code, shortest path, adjacency matrix, INFINITY #include #define INFINITY 9999 #define MAX 10 void dijkstra(int G[MAX][MAX], int n, int startnode) { int cost[MAX][MAX], distance[MAX], pred[MAX]; int visited[MAX], count, mindistance, nextnode, i, j; for (i = 0; i < n; i++) for (j = 0; j < n; j++) cost[i][j] = (G[i][j] == 0) ? INFINITY : G[i][j]; for (i = 0; i < n; i++) { distance[i] = cost[startnode][i]; pred[i] = startnode; visited[i] = 0; } distance[startnode] = 0; visited[startnode] = 1; count = 1; while (count < n - 1) { mindistance = INFINITY; for (i = 0; i < n; i++) if (distance[i] < mindistance && !visited[i]) { mindistance = distance[i]; nextnode = i; } visited[nextnode] = 1; for (i = 0; i < n; i++) if (!visited[i] && mindistance + cost[nextnode][i] < distance[i]) { distance[i] = mindistance + cost[nextnode][i]; pred[i] = nextnode; } count++; } for (i = 0; i < n; i++) { if (i == startnode) continue; printf("\nDistance of node %d = %d", i, distance[i]); printf("\nPath = %d", i); j = i; do { j = pred[j]; printf(" <- %d", j); } while (j != startnode); } printf("\n"); } int main() { int G[MAX][MAX], n, u, i, j; printf("Enter no. of vertices: "); scanf("%d", &n); printf("Enter the adjacency matrix:\n"); for (i = 0; i < n; i++) for (j = 0; j < n; j++) scanf("%d", &G[i][j]); printf("Enter the starting node: "); scanf("%d", &u); dijkstra(G, n, u); return 0; } -- @END: DIJKSTRA_PROGRAM -- @BEGIN: DIJKSTRA_PSEUDOCODE -- Write the pseudocode for Dijkstra's algorithm. -- Keywords: dijkstra pseudocode, function dijkstra, priority queue, visited, tentative distance function dijkstra(graph, source): dist[] = INFINITY, dist[source] = 0 visited[] = false Q = priority queue with (source, 0) while Q is not empty: current = dequeue min from Q if visited[current]: continue visited[current] = true for each neighbor of current: tentative = dist[current] + weight(current, neighbor) if tentative < dist[neighbor]: dist[neighbor] = tentative enqueue (neighbor, tentative) into Q return dist -- @END: DIJKSTRA_PSEUDOCODE -- @BEGIN: DIJKSTRA_COMPLEXITY -- What is the time complexity of Dijkstra's algorithm? -- Keywords: dijkstra complexity, O(V^2), O((V+E) log V), priority queue, min-heap | Implementation | Time | |----------------|-----------------| | Array | O(V^2) | | Min-Heap | O((V+E) log V) | Limitation: Does NOT work with negative edge weights (use Bellman-Ford). -- @END: DIJKSTRA_COMPLEXITY -- @BEGIN: PRIMS_PROGRAM -- Write a C program that implements Prim's algorithm to generate minimum cost spanning tree. -- Keywords: prims program, prims C code, minimum spanning tree, MST, adjacency matrix #include #define infinity 9999 #define MAX 20 int G[MAX][MAX], spanning[MAX][MAX], n; int prims() { int cost[MAX][MAX]; int u, v, min_distance, distance[MAX], from[MAX]; int visited[MAX], no_of_edges, i, min_cost, j; for (i = 0; i < n; i++) for (j = 0; j < n; j++) { cost[i][j] = (G[i][j] == 0) ? infinity : G[i][j]; spanning[i][j] = 0; } distance[0] = 0; visited[0] = 1; for (i = 1; i < n; i++) { distance[i] = cost[0][i]; from[i] = 0; visited[i] = 0; } min_cost = 0; no_of_edges = n - 1; while (no_of_edges > 0) { min_distance = infinity; for (i = 1; i < n; i++) if (!visited[i] && distance[i] < min_distance) { min_distance = distance[i]; v = i; } u = from[v]; spanning[u][v] = distance[v]; spanning[v][u] = distance[v]; no_of_edges--; visited[v] = 1; for (i = 1; i < n; i++) if (!visited[i] && cost[i][v] < distance[i]) { distance[i] = cost[i][v]; from[i] = v; } min_cost += cost[u][v]; } return min_cost; } int main() { int i, j, total_cost; printf("Enter no. of vertices: "); scanf("%d", &n); printf("Enter the adjacency matrix:\n"); for (i = 0; i < n; i++) for (j = 0; j < n; j++) scanf("%d", &G[i][j]); total_cost = prims(); printf("\nSpanning tree matrix:\n"); for (i = 0; i < n; i++) { printf("\n"); for (j = 0; j < n; j++) printf("%d\t", spanning[i][j]); } printf("\n\nTotal cost of spanning tree = %d\n", total_cost); return 0; } -- @END: PRIMS_PROGRAM -- @BEGIN: PRIMS_PSEUDOCODE -- Write the pseudocode for Prim's algorithm. -- Keywords: prims pseudocode, function prims, priority queue, visited, dist array function prims(graph, start): visited[] = false dist[] = INFINITY, dist[start] = 0 Q = priority queue with (start, 0) mstCost = 0 while Q is not empty: u = dequeue min from Q if visited[u]: continue visited[u] = true mstCost += dist[u] for each neighbor v of u: if not visited[v] and weight(u,v) < dist[v]: dist[v] = weight(u,v) enqueue (v, dist[v]) into Q return mstCost -- @END: PRIMS_PSEUDOCODE -- @BEGIN: PRIMS_COMPLEXITY -- What is the time complexity of Prim's algorithm? -- Keywords: prims complexity, O(V^2), O(E log V), array, min-heap | Implementation | Time | |----------------|------------| | Array | O(V^2) | | Min-Heap | O(E log V) | -- @END: PRIMS_COMPLEXITY -- @BEGIN: KRUSKALS_PROGRAM -- Write a C program that implements Kruskal's algorithm to generate minimum cost spanning tree. -- Keywords: kruskals program, kruskals C code, union-find, edge list, sort edges #include #define MAX 30 typedef struct edge { int u, v, w; } edge; typedef struct edgelist { edge data[MAX]; int n; } edgelist; edgelist elist, spanlist; int G[MAX][MAX], n; int find(int belongs[], int vertexno) { return belongs[vertexno]; } void union1(int belongs[], int c1, int c2) { for (int i = 0; i < n; i++) if (belongs[i] == c2) belongs[i] = c1; } void sort() { edge temp; for (int i = 1; i < elist.n; i++) for (int j = 0; j < elist.n - 1; j++) if (elist.data[j].w > elist.data[j + 1].w) { temp = elist.data[j]; elist.data[j] = elist.data[j + 1]; elist.data[j + 1] = temp; } } void kruskal() { int belongs[MAX], i, j, cno1, cno2; elist.n = 0; for (i = 1; i < n; i++) for (j = 0; j < i; j++) if (G[i][j] != 0) { elist.data[elist.n].u = i; elist.data[elist.n].v = j; elist.data[elist.n].w = G[i][j]; elist.n++; } sort(); for (i = 0; i < n; i++) belongs[i] = i; spanlist.n = 0; for (i = 0; i < elist.n; i++) { cno1 = find(belongs, elist.data[i].u); cno2 = find(belongs, elist.data[i].v); if (cno1 != cno2) { spanlist.data[spanlist.n] = elist.data[i]; spanlist.n++; union1(belongs, cno1, cno2); } } } void print() { int cost = 0; for (int i = 0; i < spanlist.n; i++) { printf("\n%d\t%d\t%d", spanlist.data[i].u, spanlist.data[i].v, spanlist.data[i].w); cost += spanlist.data[i].w; } printf("\n\nCost of the spanning tree = %d\n", cost); } int main() { printf("Enter number of vertices: "); scanf("%d", &n); printf("Enter the adjacency matrix:\n"); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%d", &G[i][j]); kruskal(); print(); return 0; } -- @END: KRUSKALS_PROGRAM -- @BEGIN: KRUSKALS_PSEUDOCODE -- Write the pseudocode for Kruskal's algorithm including Union-Find. -- Keywords: kruskals pseudocode, function kruskal, function find, function union, belongs array function kruskal(graph): edges = all non-zero edges from graph sort edges by weight ascending belongs[] = [0, 1, 2, ..., n-1] mst = [], cost = 0 for each (u, v, w) in edges: if find(u) != find(v): mst.append((u, v, w)) cost += w union(u, v) if mst.size == n - 1: break return mst, cost function find(x): return belongs[x] function union(a, b): set all belongs[i]==b to a -- @END: KRUSKALS_PSEUDOCODE -- @BEGIN: KRUSKALS_COMPLEXITY -- What is the time complexity of Kruskal's algorithm? -- Keywords: kruskals complexity, O(E log E), union-find, inverse Ackermann, alpha(V) | Step | Time | |----------------|------------------| | Sort edges | O(E log E) | | Union-Find | O(E · α(V)) ≈ O(E) | | Total | O(E log E) | α(V) = inverse Ackermann function, nearly constant. -- @END: KRUSKALS_COMPLEXITY -- @BEGIN: PRIMS_VS_KRUSKALS -- Compare Prim's and Kruskal's algorithms for MST. -- Keywords: prims vs kruskals, comparison, sparse graph, dense graph, edge sort, vertex grow | Feature | Prim's | Kruskal's | |----------------|----------------------|----------------------| | Strategy | Grow from vertex | Sort all edges | | Data Structure | Priority Queue | Union-Find | | Best for | Dense graphs | Sparse graphs | | Time (array) | O(V^2) | O(E log E) | | Time (heap) | O(E log V) | O(E log E) | -- @END: PRIMS_VS_KRUSKALS -- @BEGIN: GREEDY_APPROACH -- What is the Greedy approach in algorithm design? Give examples. -- Keywords: greedy algorithm, optimal choice, local optimum, prims, kruskal, dijkstra, job sequencing Greedy algorithms make locally optimal choices at each step hoping to find a global optimum. Examples: Dijkstra's (shortest path), Prim's and Kruskal's (MST), Job Sequencing (scheduling). -- @END: GREEDY_APPROACH -- @BEGIN: DIVIDE_CONQUER_APPROACH -- What is the Divide and Conquer approach? Give examples. -- Keywords: divide and conquer, recursion, merge sort, quick sort, strassen, base case, combine Divide and Conquer breaks a problem into smaller subproblems, solves them recursively, and combines results. Examples: Merge Sort, Quick Sort, Strassen's Matrix Multiplication. -- @END: DIVIDE_CONQUER_APPROACH -- @BEGIN: MST_CONCEPT -- What is a Minimum Spanning Tree? What are its properties? -- Keywords: minimum spanning tree, MST, connected, acyclic, n-1 edges, total weight, undirected A Minimum Spanning Tree (MST) is a subset of edges in a connected, undirected graph that: - Connects all vertices - Has no cycles (tree) - Has exactly n-1 edges - Minimizes total edge weight -- @END: MST_CONCEPT -- @BEGIN: SHORTEST_PATH_CONCEPT -- What is the shortest path problem? What algorithms solve it? -- Keywords: shortest path, dijkstra, bellman-ford, single source, weighted graph, negative edges The shortest path problem finds the path between two nodes with minimum total weight. Dijkstra's solves it for non-negative weights. Bellman-Ford handles negative weights. -- @END: SHORTEST_PATH_CONCEPT -- @BEGIN: UNION_FIND_CONCEPT -- What is Union-Find data structure? How is it used in Kruskal's algorithm? -- Keywords: union-find, disjoint set, find, union, cycle detection, belongs array, path compression Union-Find tracks disjoint sets with two operations: find(x) returns the set representative, union(a,b) merges sets. In Kruskal's, it detects cycles — if find(u) == find(v), adding edge (u,v) creates a cycle. -- @END: UNION_FIND_CONCEPT -- @BEGIN: MASTER_THEOREM -- What is the Master Theorem? How is it applied to Strassen's recurrence? -- Keywords: master theorem, T(n) = aT(n/b) + f(n), strassen, O(n^2.81), log_b(a) Master Theorem solves recurrences of form T(n) = aT(n/b) + f(n). For Strassen: T(n) = 7T(n/2) + O(n^2) a=7, b=2, f(n)=O(n^2) log_b(a) = log2(7) ≈ 2.81 > 2 Case 1 applies: T(n) = O(n^log2(7)) ≈ O(n^2.81) -- @END: MASTER_THEOREM -- @BEGIN: STABLE_SORT -- What is a stable sorting algorithm? Is Merge Sort stable? Is Quick Sort stable? -- Keywords: stable sort, unstable sort, merge sort stable, quick sort unstable, equal elements A stable sort preserves the relative order of equal elements. Merge Sort is stable (uses <= in comparison). Quick Sort is unstable (swaps can reorder equal elements). -- @END: STABLE_SORT -- @BEGIN: ADJACENCY_MATRIX -- What is an adjacency matrix? How is it used in graph algorithms? -- Keywords: adjacency matrix, graph representation, weighted graph, 2D array, vertices, edges An adjacency matrix is a 2D array where G[i][j] represents the weight of edge from vertex i to j. 0 means no edge. Used in Dijkstra's, Prim's, and Kruskal's algorithms. -- @END: ADJACENCY_MATRIX ============================================================================= END OF CONTENT =============================================================================