Introduction to Algorithms
Covers the design and analysis of algorithms: sorting, hashing, binary search trees, heaps, graph search, shortest paths, dynamic programming, and NP-completeness. Emphasises rigorous complexity analysis.
Algorithmic Thinking and Peak Finding
Overview An algorithm transforms input to output. Key ideas 1-D: linear scan O(n) vs binary search O(log n). 2-D: extend to a grid. Worked example For [1,3,5,2,4,0], 5 is a peak. Common pitfalls ...
Overview
An algorithm transforms input to output.
Key ideas
- 1-D: linear scan O(n) vs binary search O(log n).
- 2-D: extend to a grid.
Worked example
For [1,3,5,2,4,0], 5 is a peak.
Common pitfalls
- Assuming binary search works on unsorted data.
Why it matters
Divide and conquer beats linear scan.
Models of Computation and Document Distance
Overview Word RAM treats each operation as O(1). Key ideas Document = vector of word frequencies. Distance = angle between vectors. Naive O(n^2) vs dictionary O(n). Worked example Two 1000-word docs:...
Overview
Word RAM treats each operation as O(1).
Key ideas
- Document = vector of word frequencies.
- Distance = angle between vectors.
- Naive O(n^2) vs dictionary O(n).
Worked example
Two 1000-word docs: naive = 1M comparisons; hash = 2000.
Common pitfalls
- Ignoring data structure cost.
Why it matters
Choosing the right structure is the biggest win.
Sorting: Insertion, Merge, Heap
Overview Three classic comparison sorts. Key ideas Insertion: O(n^2). Merge: O(n log n), stable. Heap: O(n log n) in place. Worked example 1M integers: insertion takes hours, merge takes seconds. ...
Overview
Three classic comparison sorts.
Key ideas
- Insertion: O(n^2).
- Merge: O(n log n), stable.
- Heap: O(n log n) in place.
Worked example
1M integers: insertion takes hours, merge takes seconds.
Common pitfalls
- Using insertion on large arrays.
Why it matters
Any comparison sort is Omega(n log n).
Hashing with Chaining and Open Addressing
Overview Hash tables provide average O(1) lookup. Key ideas Chaining: linked lists. Open addressing: probing. Good hash spreads uniformly. Worked example 1000 keys in table of 1013 gives average...
Overview
Hash tables provide average O(1) lookup.
Key ideas
- Chaining: linked lists.
- Open addressing: probing.
- Good hash spreads uniformly.
Worked example
1000 keys in table of 1013 gives average chain 1.
Common pitfalls
- Ignoring load factor.
Why it matters
Worst case O(n); randomised hashing mitigates.
Binary Search Trees and AVL
Overview BST stores keys so in-order traversal is sorted. Key ideas Insert/search/delete: O(h). Degenerate trees: h = n. AVL maintains h = O(log n). Worked example Inserting sorted keys gives a...
Overview
BST stores keys so in-order traversal is sorted.
Key ideas
- Insert/search/delete: O(h).
- Degenerate trees: h = n.
- AVL maintains h = O(log n).
Worked example
Inserting sorted keys gives a linked list. AVL rebalances.
Common pitfalls
- Forgetting to update heights.
Why it matters
A balanced tree turns a list into a fast dictionary.
Graph Search: BFS and DFS
Overview Graphs model networks, dependencies, state spaces. Key ideas BFS: levels, shortest unweighted paths. DFS: deep first, cycles. Both O(V+E). Worked example Friendship graph: BFS finds degrees...
Overview
Graphs model networks, dependencies, state spaces.
Key ideas
- BFS: levels, shortest unweighted paths.
- DFS: deep first, cycles.
- Both O(V+E).
Worked example
Friendship graph: BFS finds degrees of separation.
Common pitfalls
- Using DFS for shortest paths.
Why it matters
Traversal underlies routing and scheduling.
Shortest Paths: Dijkstra and Bellman-Ford
Overview Cheapest path from a source to every vertex. Key ideas Dijkstra: non-negative, O((V+E)logV). Bellman-Ford: negative, O(VE). Worked example GPS routing: cities as vertices, roads as edges....
Overview
Cheapest path from a source to every vertex.
Key ideas
- Dijkstra: non-negative, O((V+E)logV).
- Bellman-Ford: negative, O(VE).
Worked example
GPS routing: cities as vertices, roads as edges.
Common pitfalls
- Using Dijkstra with negative edges.
Why it matters
Shortest paths underlie routing and network analysis.
Dynamic Programming
Overview Overlapping subproblems and optimal substructure. Key ideas Break into subproblems. Store answers. Build up to final. Worked example LCS of "ABCBDAB" and "BDCABA" is 4....
Overview
Overlapping subproblems and optimal substructure.
Key ideas
- Break into subproblems.
- Store answers.
- Build up to final.
Worked example
LCS of "ABCBDAB" and "BDCABA" is 4.
Common pitfalls
- Defining subproblem incorrectly.
Why it matters
DP solves problems that look exponential.
๐ Asymptotic Analysis
Q1. Solve T(n)=2T(n/2)+n.
Show Solution
Master Theorem Case 2: Theta(n log n).
Q2. Prove Omega(n log n) lower bound.
Show Solution
log2(n!) = Theta(n log n).
๐ Graph Algorithms
Q1. Implement BFS and DFS.
Show Solution
Queue vs stack.
Q2. Dijkstra on weighted graph.
Show Solution
Priority queue + relaxation.
๐ฏ Midterm Exam
Q1. Prove RB-tree height is O(log n).
Show Solution
Black-height argument.
Q2. Hash table vs balanced BST.
Show Solution
Ordering support.
๐ฏ Final Exam
Q1. Reduce 3-SAT to graph problem.
Show Solution
Polynomial reduction.
Q2. DP for edit distance.
Show Solution
D[i][j] recurrence.