Sorting Algorithms Comparisons:

Best-Case Average Worst-Case Space In-

Algorithm Type Description Stable?
Runtime Runtime Runtime Complexity Place?
Uses binary heap data structure; builds max heap
Heapsort Incramental O(n log n) O(n log n) O(n log n) O(1) Yes No
then repeatedly extracts maximum
Max Helper Maintains heap property by comparing node
O(log n) O(log n) O(log n) O(1) Yes -
Heapify Function with children and swapping if needed
Build Max Helper Converts array into max heap by calling heapify
O(n log n) O(n log n) O(n log n) O(1) Yes -
Heap Function from bottom up
Distributes elements into buckets, sorts each
Bucket Sort Distribution O(n + k) O(n + k) O(n²) O(n + k) No Yes*
bucket, then concatenates (x10 yaptığın)
Selection Repeatedly finds minimum element and places it
Incramental O(n²) O(n²) O(n²) O(1) Yes No
Sort at the beginning
Insertion Builds sorted array one element at a time by
Incremental O(n) O(n²) O(n²) O(1) Yes Yes
Sort inserting each element in correct position
Bubble Exchange- Repeatedly swaps adjacent elements if they're in
O(n) O(n²) O(n²) O(1) Yes Yes
Sort based wrong order
Divide and Recursively divides array in half, sorts each half,
Merge Sort O(n log n) O(n log n) O(n log n) O(n) No Yes
Conquer then merges sorted halves
Divide and Selects pivot, partitions array around pivot,
Quick Sort O(n log n) O(n log n) O(n²) O(log n) Yes No
Conquer recursively sorts partitions
Counting Non- O(n) Counts occurrences of each element, uses counts
O(n + k) O(n + k) O(k) No Yes
Sort comparative (k=n) to place elements in sorted order
Sorts by individual digits/characters using stable
Non- O(nd)
Radix Sort O(d(n + k)) O(d(n + k)) O(n + k) sort (usually counting sort)(significant bitten No Yes
comparative (n=k)
başlayan)
Topological Orders vertices of DAG such that for every edge
Graph-based O(V + E) O(V + E) O(V + E) O(V) No -
Sort (u,v), u comes before v

Notes:

• n = number of elements
• k = range of input values (for counting/bucket sort)
değil insertion pardon
• d = number of digits/characters (for radix sort)
• Bucket Sort stability: Depends on the sorting algorithm used within each bucket (biz counting kullanıyoz >>yes)
• Quick Sort space: O(log n) average case due to recursion stack, O(n) worst case

Selection Algorithms:
Algorithm Type Min Average Max Space Description In- Deterministic?
Runtime Runtime Runtime Complexity Place?
Random Divide and O(n) O(n) O(n²) O(log n) Finds kth smallest element using Yes No
Select Conquer randomized pivot selection and
partitioning
Random Helper O(n) O(n) O(n) O(1) Partitions array around randomly Yes No
Partition Function selected pivot element
Median of Divide and O(n) O(n) O(n) O(log n) Finds kth smallest element with Yes Yes
Medians Conquer guaranteed good pivot selection
(deterministic)

Notes:

• Random Select: Also known as Randomized Quickselect

• Random Partition: Helper function used by Random Select and Randomized Quicksort

Best/Worst Case Conditions:

Sorting Algorithms:

• Heapsort: All cases O(n log n) - performance doesn't depend on input order
• Selection Sort: All cases O(n²) - always scans entire unsorted portion regardless of input
• Insertion Sort:
o Best O(n): Array is already sorted (each element needs only 1 comparison)
o Worst O(n²): Array is reverse sorted (each element needs maximum shifts)
• Bubble Sort:
o Best O(n): Array is already sorted (optimized version with early termination)
o Worst O(n²): Array is reverse sorted (maximum swaps needed)
• Merge Sort: All cases O(n log n) - always divides and merges the same way
• Quick Sort:
o Best O(n log n): Pivot always divides array into equal halves
o Worst O(n²): Pivot is always smallest/largest element (already sorted/reverse sorted arrays with poor pivot
selection)
• Bucket Sort:
o Best O(n + k): Elements uniformly distributed across buckets
o Worst O(n²): All elements fall into same bucket, degenerates to sorting algorithm used within bucket
• Counting/Radix Sort: Performance independent of input order
• Topological Sort:
o All cases O(V + E): Performance depends on graph structure, not vertex ordering
o Only works on DAGs: Directed Acyclic Graphs - if cycle exists, topological sort is impossible
o Two main approaches: DFS-based (using finishing times) or BFS-based (Kahn's algorithm using in-degrees)

Selection Algorithms:

• Random Select:
o Best/Average O(n): Good pivot selection reduces problem size effectively
o Worst O(n²): Consistently poor pivot selection (always picks min/max element)
• Median of Medians:
o All cases O(n): Guarantees good pivot selection by finding median of medians as pivot
o Algorithm: Divides array into groups of 5, finds median of each group, recursively finds median of those median
 Algorithm Summary Tables:
Rod Cutting Problem

Algorithm Approach Logic Formula/Recurrence Time Space Variables Properties Key Points
1. Naive Recursive Try every r(n) = max(p[i] + O(2^ O(n) n=rod length, p[i]=price ✓ Optimal substructure, ✓ - Very slow (exponential), -
Recursive possible cut r(n-i)) for i=1 to n n) stack for length i, r(n)=max Recomputes same
Overlapping subproblems,
position and space revenue for length n ✗ Greedy-choice property subproblems, - Base case: r(0)
take maximum =0
2. Top- Dynamic Same logic but r(n) = max(p[i] + O(n²) O(n) Same as above + memo ✓ Optimal substructure, ✓ - Good approach, - Saves
Down with Programmin cache results r(n-i)) with memo table for caching subproblem results, - Avoids
Overlapping subproblems,
Memoizati g to avoid table redundant work
✗ Greedy-choice property
on (Recursive) recomputation
3. Bottom- Dynamic Build solution r[j] = max(p[i] + O(n²) O(n) j=current length being ✓ Optimal substructure, ✓ - Most efficient approach, - No
Up Programmin from smallest r[j-i]) for i=1 to j computed, i=cut position, recursion overhead, - Computes
Overlapping subproblems,
g (Iterative) subproblems r[j]=max revenue for ✗ Greedy-choice property each subproblem once
up length j

Problem Definition

• Input: Rod of length n, price table p[1..n]

• Goal: Cut rod to maximize revenue
• Key Insight: For each length, try all possible first cuts and take the maximum
• Brute Force Complexity: 2^(n-1) ways to cut a rod (exponential without DP)

Variable Definitions

• n: Length of the rod

• p[i]: Price for a rod piece of length i
• r[i] or r(i): Maximum revenue obtainable from a rod of length i
• i, j: Loop variables for cut positions/lengths

Notes

• Brute Force: Try every combination (2^(n-1) ways to cut)

• DP Insight: Optimal substructure - optimal solution contains optimal solutions to subproblems
• Memoization: Top-down saves computed results
• Bottom-up: Iterative, no recursion stack

Matrix Chain Multiplication

Algorithm Approach Logic Formula/Recurrence Time Space Variables Properties Key Points
MCM(p,i,j) =
1. Naive Recursive Try all
min(MCM(p,i,k) +
O(2^n) O(n) p[]=dimension array, ✓ Optimal substructure, ✓ - Exponential time, - Base
Recursive possible MCM(p,k+1,j) + p[i- stack i,j=matrix range, k=split Overlapping subproblems, case: i=j return 0, - Explores
split points 1]×p[k]×p[j])for k=i to j-1 space point, MCM(p,i,j)=min ✗ Greedy-choice property all possible splits
k, take cost
minimum
cost
2. Top- Dynamic Same logic Same recurrence with O(n³) O(n²) Same as above + ✓ Optimal substructure, ✓ - Reduces exponential to
Down with Programmin but cache memo table m[i,j] m[i,j]=memo table stores Overlapping subproblems, polynomial, - Avoids
Memoizati g results in min costs ✗ Greedy-choice property recomputation, - Check
on (Recursive) m[i,j] table memo before computing
3. Bottom- Dynamic Fill table m[i,j] = min(m[i,k] +
m[k+1,j] + p[i-
O(n³) O(n²) l=chain length, i,j=matrix ✓ Optimal substructure, ✓ - Most common approach, -
Up Programmin from smaller 1]×p[k]×p[j]) indices, k=split point, Overlapping subproblems, No recursion overhead, - Fill
g (Iterative) lengths to m[i,j]=min cost table ✗ Greedy-choice property by increasing chain length
larger

Problem Definition

• Input: Chain of matrices A₁×A₂×...×Aₙ with dimensions p₀×p₁, p₁×p₂, ..., pₙ₋₁×pₙ
 • Goal: Find optimal parenthesization to minimize scalar multiplications
• Key Insight: Different parenthesizations have vastly different costs
• Brute Force Complexity: Catalan number C(n-1) = (2n-2)!/(n-1)!n! ≈ 4^n ways to parenthesize (exponential
without DP)

Variable Definitions for MCM

• p[i]: Dimension array where matrix Aᵢ has dimensions p[i-1] × p[i]

• m[i,j]: Minimum cost to multiply matrices Aᵢ through Aⱼ
• k: Split point where we divide the chain (i ≤ k < j)
• l: Length of matrix chain being considered

Longest Common Subsequence (LCS)

Algorithm Approach Logic Formula/Recurrence Time Space Variables Properties Key Points
1. Brute Generate all Generate all 2^m Generate all possible O(n × 2^m) O(1) X,Y=input ✓ Optimal substructure, - Exponential and very inefficient,
Force subsequences subsequences of subsequences and sequences, ✓ Overlapping - Generate 2^m subsequences for
X, check if each compare m,n=lengths X, - Check each in Y takes O(n)
subproblems, ✗
appears in Y time
Greedy-choice property
2. Naive Recursive Compare LCS(i,j) = 0, if O(2^(m+n)) O(m+n) i,j=current ✓ Optimal substructure, - Exponential time, - Recomputes
Recursive characters: if i=0 or j=0; stack positions, same subproblems, - Base case:
✓ Overlapping
match, add 1 + X[i],Y[j]=ch empty sequence gives LCS=0
LCS(i-1,j-1)+1, subproblems, ✗
LCS of if X[i]=Y[j]; aracters,
Greedy-choice property
remaining, else LCS(i,j)=len
take max of two max(LCS(i-1,j), gth of LCS
options LCS(i,j-1)) else
3. Top-Down Dynamic Same recursive Same recurrence with O(m×n) O(m×n) Same as ✓ Optimal substructure, - Reduces exponential to
with Programming logic but cache memo table c[i,j] above + ✓ Overlapping polynomial, - Check memo before
Memoization (Recursive) results in c[i,j] c[i,j]=memo computing, - Store computed
subproblems, ✗
table table storing results
Greedy-choice property
LCS lengths
4. Bottom-Up Dynamic Fill table from c[i,j] = 0, if O(m×n) O(m×n) i,j=table ✓ Optimal substructure, - Most efficient approach, - Fill
Programming smaller i=0 or j=0; basic, indices, table row by row, - Can optimize
✓ Overlapping
(Iterative) subproblems to O(min(m, c[i,j]=LCS space to O(min(m,n))
c[i-1,j-1]+1, if subproblems, ✗
larger X[i]=Y[j]; n)) length table,
Greedy-choice property
optimized X,Y=sequen
max(c[i- ces
1,j],c[i,j-1])
else

Problem Definition

• Input: Two sequences X and Y of lengths m and n

• Goal: Find longest subsequence that appears in both sequences in same order
• Key Insight: Subsequence doesn't need consecutive characters but must maintain original order
• Brute Force Complexity: 2^m possible subsequences to generate and check

Variable Definitions for LCS

• X, Y: Input sequences of lengths m and n respectively

• i, j: Current positions/indices in sequences X and Y
• c[i,j]: Length of LCS of X[1..i] and Y[1..j]
• m, n: Lengths of sequences X and Y

Important Notes

• Applications: Gene similarity, version control (Git, SVN), text comparison

• Traceback: To find actual LCS, trace back through table from c[m,n] to c[0,0]
• Space Optimization: Only need previous row, can reduce space to O(min(m,n))
 Activity Selection

Algorithm Approach Logic Formula/Recurrence Time Space Variables Properties Key Points
1. Naive Recursive For each activity, c[i,j] = 0 if Sᵢⱼ = ∅; O(n × O(n) i,j=time indices, ✓ Optimal substructure, - Very slow (exponential), -
Recursive try including it or max{c[i,k] + 1 + c[k,j]} 2^n) stack k=activity index, ✓ Overlapping Explores all possible
not, take if Sᵢⱼ ≠ ∅ space c[i,j]=max activities in combinations, - Recomputes
subproblems, ✓
maximum time interval, subproblems
Greedy-choice property
Sᵢⱼ=compatible activities
2. Dynamic Dynamic Build table c[i,j] c[i,j] = max{c[i,k] + 1 O(n³) O(n²) Same as above + table ✓ Optimal substructure, - Polynomial time, - No recursion
Programmi Programmin for all intervals, + c[k,j]} for all k where c[i,j] for memoization ✓ Overlapping overhead, - Fill table
ng g (Iterative) fill from smaller aₖ ∈ Sᵢⱼ subproblems, ✓
systematically
to larger intervals
Greedy-choice property
3. Greedy Greedy Always select AS(s,f,n): Sort by O(n O(1) s[i]=start times, ✓ Optimal substructure, - FASTEST approach, - Sort
Algorithm activity that finish time, select log n) f[i]=finish times, ✗ Overlapping once by finish time, - Always
finishes earliest earliest finishing, n=number of activities optimal for this problem
subproblems, ✓
among remaining remove overlapping
Greedy-choice property
compatible
activities

Problem Definition

• Input: n activities with start times s[i] and finish times f[i]
• Goal: Select maximum number of non-overlapping activities
• Key Insight: Activities are compatible if they don't overlap in time
• Compatible Activities: Two activities don't overlap if fᵢ ≤ sⱼ or fⱼ ≤ sᵢ

Variable Definitions

• s[i], f[i]: Start and finish times of activity i

• Sᵢⱼ: Subset of activities that start after activity i finishes and end before activity j starts
• c[i,j]: Maximum number of activities that can be selected from Sᵢⱼ

Optimal Prefix Codes

Algorithm Approa Logic Formula/Recurrenc Time Space Variables Properties Key Points
ch e
1. Brute Exhaust Try all possible full ABC = Σ(frequency O(4^n) O(n) n=alphabet size, ✓ Optimal substructure, ✗ - Exponential (Catalan numbers), -
Force ive binary trees with n × code_length) for ABC=average bits Overlapping subproblems, Tests all possible tree structures, -
Search leaves, calculate all characters per character ✓ Greedy-choice property Impractical for large alphabets
ABC for each
2. Shannon- Divide- Split alphabet into Split S into S₁, S₂ O(n² log O(n log S₁, S₂=split ✓ Optimal substructure, ✗ - Not always optimal, - Top-down
Fano (1948) and- two equal-frequency where Σf_l in S₁ ≈ n) n) subsets, recursive Overlapping subproblems, approach, - Attempts balanced splits
Conque parts, recursively Σf_l in S₂ = 0.5 depth=O(logn) ✗ Greedy-choice property
r build subtrees
3. Huffman Greedy Always merge two f_w = f_y + f_z O(n log n) O(n) Q=priority queue, ✓ Optimal substructure, ✗ - OPTIMAL for prefix codes, -
Algorithm (Botto lowest-frequency where y,z are min y,z=min freq Overlapping subproblems, Uses min-heap/priority queue, -
m-up) nodes, build tree frequencies chars, w=new ✓ Greedy-choice property Bottom-up construction
from leaves to root internal node

Problem Definition

• Input: Alphabet S with character frequencies f_l for each character l ∈ S

• Goal: Find variable-length prefix code that minimizes average bits per character
• Key Insight: More frequent characters should have shorter encodings
• Prefix Code Property: No codeword is prefix of another (enables unambiguous decoding)

Variable Definitions

• S: Alphabet of characters, |S| = n

• f_l: Frequency of character l in the text
• c(l): Binary encoding of character l
 • |c(l)|: Length of encoding for character l
• ABC(c): Average Bits per Character = Σ(f_l × |c(l)|)

Minimum Spanning Tree (MST)

Algorithm Approach Logic Formula/Recurrence Time Space Variables Properties Key Points
1. Brute Exhaustive Try all possible Check all n^(n-2) O(n^n) O(n) G=(V,E), ✗ Not optimal for large - NOT OPTIMAL -
Force Search spanning trees, spanning trees w=edge weights, graphs ✗ Exponential time Exponential complexity
calculate weight of (Cayley's formula) T=spanning tree, Theoretical approach only
complexity ✓ Guarantees
each, return minimum n= Guarantees global minimum
absolute minimum ✗ Infeasible for n>10-15
Impractical for real vertices
applications
2. Prim's Greedy Grow tree from single At each step: add O(m log O(n) Q=priority queue, ✓ Optimal substructure, ✗ - OPTIMAL, - Vertex-
Algorithm (Vertex- vertex, always add min{w(u,v) : u∈T, n) with key[v]=min edge Overlapping subproblems, ✓ centric approach, - Good for
based) minimum weight v∉T} heap, weight to v, Greedy-choice property dense graphs, - Uses priority
edge connecting tree O(n²) parent[v]=predec queue
to new vertex with essor
array
3. Greedy Sort all edges by Sort edges: O(m log O(m log O(n) Sorted edge list ✓ Optimal substructure, ✗ - OPTIMAL, - Edge-centric
Kruskal's (Edge- weight, add lightest m), For each edge: if m) E, Union-Find Overlapping subproblems, ✓ approach, - Good for sparse
Algorithm based) edge that doesn't FindSet(u) ≠ structure, Greedy-choice property graphs, - Uses Union-Find
create cycle using FindSet(v) then A=MST edge set for cycle detection
Union-Find Union(u,v)

Problem Definition

• Input: Connected, weighted, undirected graph G = (V, E) with weight function w: E → ℝ

• Goal: Find spanning tree T with minimum total weight Σw(e) for all e ∈ T
• Key Constraint: Spanning tree connects all vertices with exactly n-1 edges (no cycles)
• Applications: Network design, circuit layout, clustering, approximation algorithms

Variable Definitions

• G = (V, E): Input graph with vertices V and edges E

• w(u,v): Weight of edge between vertices u and v
• T: Spanning tree (subset of E with n-1 edges, no cycles)
• n = |V|: Number of vertices
• m = |E|: Number of edges

Union-Find (Disjoint Set) Data Structure

Implementation Approach Logic Operations Time per Operation Space Variables Properties Key Points
1. Naive Linked Linked List Each set is linked MakeSet(x), MakeSet: O(1), O(n) Each element ✗ Expensive - Union updates all pointers, - Total:
List list, maintain FindSet(x), FindSet: O(1), Union: points to Union O(m×n) for m operations
pointer to Union(x,y) O(n) representative
representative
2. Weighted Linked List Always append Same operations, MakeSet: O(1), O(n) Size of each ✓ Weighted - Much faster Union, - Each element
Union + Size smaller list to Union chooses FindSet: O(1), Union: set, weighted Union moved ≤ log n times, - Total: O(m + n
Optimization larger list smaller list O(log n) amortized union Heuristic log n)
heuristic

Problem Definition

• Maintain collection of disjoint sets S = {S₁, S₂, ..., Sₖ}

• Each set has a representative element
• Support three operations: MakeSet, FindSet, Union
• Applications: Kruskal's MST, connected components, equivalence relations
 Variable Definitions

• MakeSet(x): Create new set {x} with x as representative

• FindSet(x): Return representative of set containing x
• Union(x,y): Merge sets containing x and y into single set

Breadth-First Search (BFS)

Algorithm Approach Logic Formula/Recurrence Time Space Variables Properties Key Points
BFS Graph Explore Visit all nodes at O(V O(V) V=vertices, E=edges, ✗ Optimal substructure, - Uses queue for FIFO order, - Finds
Traversal graph level- distance k before + E) Q=queue, colors ✗ Overlapping shortest path in unweighted graphs, -
by-level visiting nodes at (White/Gray/Black), Colors: White=undiscovered,
subproblems, ✗
using queue distance k+1 d[u]=distance, Gray=discovered but not fully explored,
Greedy-choice property
(FIFO) π[u]=parent Black=fully explored

Problem Definition

• Input: Graph G(V,E) and source vertex s

• Goal: Explore graph level-by-level, find shortest paths from source
• Key Insight: Visit all neighbors at current level before going to next level
• Applications: Shortest path in unweighted graphs, connected components, bipartite testing

Depth-First Search (DFS)

Algorithm Approach Logic Formula/Recurrence Time Space Variables Properties Key Points
DFS Graph Go as deep as Recursively visit O(V + O(V) V=vertices, E=edges, ✗ Optimal - Explores structure deeply, - Detects
Traversal possible down neighbors, backtrack E) colors substructure, ✗ cycles, - Used for topological sorting,
one path, then when no unvisited (White/Gray/Black), Overlapping finding strongly connected components, -
backtrack neighbors remain d[u]=discovery time, Time increases every time you discover or
subproblems, ✗
f[u]=finish time, finish a vertex
Greedy-choice
π[u]=parent
property

Problem Definition

• Input: Graph G(V,E)

• Goal: Explore graph by going as deep as possible before backtracking
• Key Insight: Explore one path completely before trying another
• Applications: Cycle detection, topological sorting, strongly connected components, maze solving

Strongly Connected Components (SCC) - Kosaraju's Algorithm

Algorithm Approach Logic Formula/Recurrence Time Space Variables Properties Key Points
Kosaraju's Graph 1) Run DFS on G, record Each DFS tree in step O(V + O(V) G=original graph, ✗ Optimal - 3-step process: DFS → Transpose
SCC Algorithm finish times 2) Transpose G 3 is one SCC E) G^T=transpose substructure, ✗ → DFS on transpose, - Transposing
3) Run DFS on G^T in graph, f[u]=finish Overlapping doesn't change SCC structure, - Each
decreasing order of finish time, SCC subproblems, ✗ DFS tree in final step = one SCC, -
times components Works because of mathematical
Greedy-choice
properties of SCCs
property

Problem Definition

• Input: Directed graph G(V,E)

• Goal: Find all strongly connected components (maximal groups where every vertex can reach every other vertex in
the same group)
• Key Insight: SCCs remain unchanged when graph is transposed
 • Applications: Web page ranking, social network analysis, circuit design

Algorithm Steps:

1. Run DFS on original graph G, record finishing times

2. Compute transpose graph G^T (reverse all edges)
3. Run DFS on G^T processing vertices in decreasing order of finishing times from step 1
4. Each DFS tree in step 3 forms one SCC

Variable Definitions:

• V, E: Number of vertices and edges in graph

• d[u], f[u]: Discovery and finish times for vertex u in DFS
• π[u]: Parent of vertex u in DFS tree
• Colors: White=undiscovered, Gray=currently being processed, Black=finished processing
• Q: Queue used in BFS for FIFO ordering
• G^T: Transpose of graph G (all edges reversed)

Single Source Shortest Path (SSSP) Algorithms

Algorithm Approach Logic Formula/Recurrence Time Space Variables Properties Key Points
1. Dynamic Relax all edges RELAX(u,v,w): if O(|V| × |E|) O(|V|) G=(V,E), ✓ Optimal - Handles negative weights, -
Bellman- Programming |V|-1 times, then d[u] + w(u,v) < d[v] w=weight substructure, ✓ Detects negative cycles, - |V|-1
Ford check for then d[v] = d[u] + function, Overlapping iterations find all shortest paths, -
negative cycles w(u,v), π[v] = u d[v]=shortest 3rd loop checks for negative cycles
subproblems, ✗
distance,
Greedy-choice
π[v]=predecessor,
property
s=source
2. DAG- Topological Process vertices Same RELAX O(|V| + |E|) O(|V|) Same as above + ✓ Optimal - Only works on DAGs (no cycles),
SSSP Sort + in topological operation but on topological substructure, ✓ - Linear time solution, - Most
Relaxation order, relax topologically sorted ordering Overlapping optimal O(|V| + |E|), - Handles
outgoing edges vertices negative weights
subproblems, ✗
Greedy-choice
property
3. Greedy Always pick Same RELAX + O(|E| + O(|V|) Same as above + ✗ Optimal - Only non-negative weights, -
Dijkstra closest unvisited priority queue for |V|log|V|) with priority queue Q, substructure, ✗ Greedy approach (always pick
vertex, relax its minimum distance Fibonacci heap, S=finalized Overlapping closest), - Most common for
neighbors O(|E|log|V|) vertices practical use, - Fast performance
subproblems, ✓
with binary
Greedy-choice
heap
property

SSSP Algorithm Comparison

Algorithm Time Complexity Space Negative Weights Negative Cycles Best Use Case
Bellman-Ford O(|V| × |E|) O(|V|) ✓ Detects Graph has negative edge weights
DAG-SSSP O(|V| + |E|) O(|V|) ✓ N/A (no cycles) Directed Acyclic Graph
Dijkstra O(|E|log|V|) O(|V|) ✗ N/A All edge weights non-negative

Problem Definition

• Input: Weighted directed graph G(V,E), weight function w, source vertex s

• Goal: Find shortest paths from source s to all other vertices
• Key Insight: Different algorithms optimal for different graph properties
• Applications: GPS navigation, network routing, flight planning

Algorithm Details:
 Bellman-Ford:

• Why |V|-1 iterations: Any shortest path has at most |V|-1 edges (simple path)
• After k iterations: Find shortest paths using at most k edges
• Third loop purpose: If any edge can still be relaxed after |V|-1 iterations, negative cycle exists
• Negative cycle detection: What makes Bellman-Ford special

DAG-SSSP:

• Key idea: Use topological ordering of vertices

• Why it works: Process vertex u before all paths to u have been considered
• Linear time: Most efficient SSSP algorithm O(|V|+|E|)
• Topological sort: Guarantees correct processing order

Dijkstra:

• Greedy choice: Always process closest unvisited vertex

• Why no negative weights: Greedy choice might not be optimal with negative weights
• Priority queue: Extract-min for closest vertex, decrease-key for relaxation
• Finalized set S: Vertices whose shortest distances are final

Key Insights:

1. Greedy vs. Dynamic Programming: Dijkstra uses greedy (works due to non-negative weights), Bellman-Ford
uses dynamic programming approach
2. Why Dijkstra fails with negative weights: Greedy choice might not be optimal, once a vertex is in S, its distance
is considered final
3. Topological ordering power: DAG-SSSP achieves linear time by processing vertices in right order

All-Pairs Shortest Path (APSP) Algorithms

Algorithm Approach Logic Formula/Recurrence Time Space Variables Properties Key Points
1. Run Multiple Apply Same as Bellman-Ford, O(|V|²×|E|) O(|V|²) Same as ✓ Optimal substructure, ✓ - Very slow for dense graphs, -
Bellman- SSSP Bellman-Ford repeated |V| times Bellman-Ford + Overlapping subproblems, Handles negative edge weights, -
Ford from algorithm distance matrix ✗ Greedy-choice property Detects negative cycles
each vertex from every output
vertex as
source
2. Run Multiple Apply Same as Dijkstra, O(|V|×(|E|log O(|V|²) Same as Dijkstra ✗ Optimal substructure, ✗ - Better for sparse graphs, -
Dijkstra SSSP Dijkstra repeated |V| times |V|)) = + distance matrix Overlapping subproblems, Cannot handle negative edge
from each algorithm O(|V|×|E|log| output ✓ Greedy-choice property weights, - Good practical
vertex from every V|) performance
vertex as
source
3. Floyd- Dynamic For each d[i,j] = min(d[i,j], d[i,k] O(|V|³) O(|V|²) d[i,j]=shortest ✓ Optimal substructure, ✓ - Most common APSP algorithm,
Warshall Programmin intermediate + d[k,j]) for all i,j,k distance from i to Overlapping subproblems, - Simple 3-nested loops, -
g (Vertex- vertex k, j, k=intermediate ✗ Greedy-choice property Handles negative weights, -
based) update all vertex Detects negative cycles
pairs (i,j) if
path through
k is shorter
4. Matrix Dynamic Use repeated L(m) = min(L(m-1)×W) O(|V|³log|V|) O(|V|²) L(m)=distance ✓ Optimal substructure, ✓ - Theoretical interest, - Uses
Multiplicati Programmin matrix where L(m)[i,j] = using fast matrix for paths Overlapping subproblems, matrix multiplication, - Can be
on Method g (Edge- squaring, shortest path using ≤m matrix ≤m edges, ✗ Greedy-choice property faster with advanced techniques, -
based) extend paths edges multiplicatio W=weight Complex implementation
by one edge n matrix
at a time

Problem Definition:

• Input: Weighted directed graph G(V,E) with weight function w

• Goal: Compute shortest paths between every pair of vertices
 • Output: Distance matrix where entry (i,j) contains shortest path distance from vertex i to vertex j
• Applications: Network analysis, game AI pathfinding, urban planning

APSP Algorithm Comparison:

Algorithm Time Complexity Space Best For

Bellman-Ford (×|V|) O(|V|²×|E|) O(|V|²) Sparse graphs with negative edges
Dijkstra (×|V|) O(|V|×|E|log|V|) O(|V|²) Sparse graphs, no negative edges
Floyd-Warshall O(|V|³) O(|V|²) Dense graphs, simple implementation
Matrix-based DP O(|V|³log|V|) O(|V|²) Theoretical optimality

Key Algorithm Properties Summary

Dynamic Programming Properties:

1. Optimal Substructure: Optimal solution contains optimal solutions to subproblems

2. Overlapping Subproblems: Same subproblems are solved multiple times

Greedy Algorithm Properties:

1. Greedy Choice Property: Locally optimal choice leads to globally optimal solution
2. Optimal Substructure: Must also have optimal substructure

Time Complexity Patterns:

• Exponential without DP: O(2^n), O(4^n) - brute force approaches

• Polynomial with DP: O(n²), O(n³) - dynamic programming solutions
• Graph algorithms: Often O(V²), O(V³), O(E log V) depending on approach

PageRank Algorithm

Algorithm Approach Logic Formula/Recurrence Time Space Variables Properties Key Points
1. Basic Iterative Each page PR(A) = (1-d)/N + d × O(k×n²) O(n²) PR(A)=PageRank ✗ Optimal - Models web as directed graph, -
PageRank (Power shares its Σ(PR(T)/C(T)) for all T where of page A, substructure, ✗ Iterative until convergence, - Handles
Method) importance linking to A k=iterations d=damping factor Overlapping "random surfer" behavior
equally (0.85), N=total
subproblems, ✗
among pages pages,
Greedy-choice
it links to C(T)=outgoing
property
links from T
2. Google Linear Solve Ax = x M = (1-d)/N × J + d × O(n³) direct O(n²) M=Google matrix, ✗ Optimal - Eigenvector with eigenvalue 1, -
Matrix Algebra where A is A, where PageRank solution, A=transition substructure, ✗ Perron-Frobenius theorem applies, -
Form (Eigenvalue) Google vector v* is dominant O(k×n²) matrix, J=matrix Overlapping Power iteration converges to dominant
Matrix eigenvector iterative of all 1s, eigenvector
subproblems, ✗
v*=PageRank
Greedy-choice
vector
property

Problem Definition:

• Input: Web graph G(V,E) where V=webpages, E=links between pages

• Goal: Rank pages by importance based on link structure
• Key Insight: A page's importance determined by who links to it
• Applications: Search engine ranking, social network analysis, recommendation systems

PageRank Key Concepts:

• Links = Votes: If page A links to page B, A "votes" for B's importance

 • Vote Weight: Vote from important page means more than vote from random page
• Damping Factor (d=0.85): Probability user follows links vs. random jump
• Random Surfer Model: User either follows link (85%) or jumps randomly (15%)

Graph Theory Algorithms & Concepts

Concept Approac Logic Formula/Rec Time Space Variables Properties Key Points
h urrence
1. Eulerian Graph Check if every Check degree O(V + E) O(V) G=(V,E), ✓ Polynomial verifiable, - Visit every EDGE exactly once, -
Cycle Traversal vertex has even of each vertex: degree(v)=number ✓ Polynomial solvable All vertices must have even degree,
Detection degree and graph is degree(v) % 2 of edges incident to - Graph must be connected
connected == 0 for all v v
2. Backtrack Try to visit every No simple O(n!) brute O(n²) for G=(V,E), path ✓ Polynomial verifiable, - Visit every NODE exactly once, -
Hamiltonia ing/DP vertex exactly once formula - NP- force, DP visiting each vertex ✗ No known polynomial NP-complete problem, - No
n Cycle and return to start complete O(n²2ⁿ) DP once solution efficient algorithm known
Detection problem

Graph Theory Problem Definitions:

Eulerian Cycle:

• Definition: Path that visits every edge exactly once and returns to starting vertex
• Condition: All vertices must have even degree AND graph must be connected
• Certificate: Sequence of edges using each edge once
• Verifier: Check edges used exactly once and path is valid
• Examples: Seven Bridges of Königsberg (no solution - odd degrees)

Hamiltonian Cycle:

• Definition: Path that visits every vertex exactly once and returns to starting vertex
• Condition: No simple necessary/sufficient condition known
• Certificate: Sequence of vertices visiting each vertex once
• Verifier: Check all vertices visited exactly once and edges exist
• Examples: Traveling Salesman Problem (find shortest Hamiltonian cycle)

Complexity Classes

Class Definition Key Properties Examples Relationship

P Polynomial Time Problems solvable in polynomial time Shortest path, sorting, Eulerian cycle P ⊆ NP
NP Nondeterministic Polynomial Problems verifiable in polynomial time SAT, Hamiltonian cycle, Clique, TSP P ⊆ NP ⊆ PSPACE
NP- Hardest NP Problems In NP AND every NP problem reduces to it SAT, 3-SAT, Hamiltonian cycle, Clique If any NP-complete problem is in P, then P = NP
Complete

Key Complexity Insights:

• P vs NP Question: Does P = NP? (Million dollar problem)

• NP-Complete Problems: All equally hard - if you solve one in polynomial time, you solve all
• Polynomial Reduction: Problem A reduces to B if A can be solved using B as subroutine
• Cook-Levin Theorem: SAT is NP-complete (first proven NP-complete problem)

Important NP-Complete Problems:

• SAT (Boolean Satisfiability): Given boolean formula, does satisfying assignment exist?
• 3-SAT: SAT with clauses of exactly 3 literals
• Clique: Does graph contain complete subgraph of size k?
• Hamiltonian Cycle: Does graph have cycle visiting each vertex once?
• Traveling Salesman: Find shortest tour visiting all cities once