Reference topics: 6.006 ยท independent study notes, not affiliated

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.

8Lectures
2Assignments
2Exams
1hDuration
1

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 ...

โฑ 1 min read

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.

2

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:...

โฑ 1 min read

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.

3

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. ...

โฑ 1 min read

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).

4

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...

โฑ 1 min read

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.

5

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...

โฑ 1 min read

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.

6

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...

โฑ 1 min read

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.

7

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....

โฑ 1 min read

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.

8

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....

โฑ 1 min read

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.