Algorithm Notes (Exam-Ready)
Prim’s Algorithm
Minimum Spanning Tree (MST). Start with one vertex, repeatedly add the minimum weight edge
that connects a visited vertex to an unvisited vertex. Complexity: O(E log V).
Kruskal’s Algorithm
MST. Sort edges by weight, pick edges if they don’t form a cycle. Uses Union-Find. Complexity:
O(E log E).
Dijkstra’s Algorithm
Single Source Shortest Path (non-negative weights). Greedy. Complexity: O(V^2) or O(E log V).
Knapsack Problem
0/1 Knapsack: DP solution O(nW). Fractional Knapsack: Greedy, take fraction based on
value/weight.
Divide & Conquer
Break → Solve subproblems → Combine. Examples: Merge Sort, Quick Sort, Binary Search.
Sorting
Comparison sorts: Bubble, Selection, Insertion, Merge, Quick, Heap. O(n log n) best, O(n^2) worst.
Asymptotic Notation
Big-O (upper bound), Ω (lower bound), Θ (tight bound).
Maximum & Minimum
Linear O(n). Divide & Conquer reduces comparisons (~1.5n).
Exponential Algorithms
Time grows as 2^n, n!, etc. Examples: TSP brute force, subset generation.
Tower of Hanoi
Recurrence: T(n)=2T(n-1)+1. Solution: T(n)=2^n-1. Classic recursion.
Greedy Fractional Knapsack
Take items in decreasing value/weight ratio. Optimal since fractions allowed.
Order of Growth
O(1)<O(log n)<O(n)<O(n log n)<O(n^2)<O(n^3)<O(2^n)<O(n!).
Travelling Salesman Problem
NP-hard. Exact DP Held-Karp O(n^2 2^n). Approximations exist.
BFS, DFS, Graph
BFS: Queue, level-order, shortest path in unweighted. DFS: Stack/recursion. Represent with
adjacency list/matrix.
LCS & Matrix Chain Multiplication
LCS: DP. MCM: DP for optimal parenthesization.
Bellman-Ford
Shortest Path with negative weights. Relax edges V-1 times. Detects negative cycles. O(VE).
NP Problems
P: solvable in poly time. NP: verifiable in poly. NP-Complete: hardest in NP. NP-Hard: at least as
hard as NP-C.
Subset Problems
Subset Sum: does subset sum = target? Brute O(2^n), DP O(nW).