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

Introduction to Computational Thinking and Data Science

Builds on 6.0001. Introduces computational problem-solving with data: plotting, stochastic simulation, random walks, Monte Carlo methods, and an introduction to machine learning concepts. Emphasises reasoning about uncertainty.

10Lectures
2Assignments
2Exams
1hDuration
1

Optimisation and the Knapsack Problem

Overview The knapsack problem asks you to choose items to maximise value under a weight limit. It appears in budgeting, cargo loading, and resource allocation. Key ideas Greedy approach: pick the...

โฑ 1 min read

Overview

The knapsack problem asks you to choose items to maximise value under a weight limit. It appears in budgeting, cargo loading, and resource allocation.

Key ideas

  • Greedy approach: pick the best value/weight ratio first.
  • Brute-force: try all subsets.
  • Dynamic programming: pseudo-polynomial, exact.

Worked example

Greedy fails: capacity 10, items (6,6),(5,5),(5,5). Greedy picks 6/6; optimal picks two 5/5.

Common pitfalls

  • Assuming greedy is optimal.
  • Ignoring the weight budget.

Why it matters

Not every problem has a fast exact solution.

2

Graph Problems and Search

Overview Graphs model networks, dependencies, and state spaces. Key ideas BFS explores by levels. DFS goes deep first. Both run in O(V+E). Worked example Course prerequisite chains form a DAG....

โฑ 1 min read

Overview

Graphs model networks, dependencies, and state spaces.

Key ideas

  • BFS explores by levels.
  • DFS goes deep first.
  • Both run in O(V+E).

Worked example

Course prerequisite chains form a DAG. Topological sort gives a valid study order.

Common pitfalls

  • Using DFS when shortest paths are needed.

Why it matters

Traversal is the foundation of routing and scheduling.

3

Stochastic Thinking

Overview Real data is noisy. Probability gives us a language for uncertainty. Key ideas Random variables, distributions. Independence vs dependence. Law of large numbers. Worked example Roll two dice...

โฑ 1 min read

Overview

Real data is noisy. Probability gives us a language for uncertainty.

Key ideas

  • Random variables, distributions.
  • Independence vs dependence.
  • Law of large numbers.

Worked example

Roll two dice 10,000 times. Average sum is ~7. Error scales as 1/sqrt(N).

Common pitfalls

  • Confusing correlation with causation.

Why it matters

Every later topic rests on probability.

4

Random Walks and Monte Carlo

Overview A random walk is a path of random steps. Monte Carlo estimates quantities by sampling. Key ideas Simulate many walks. Error ~ 1/sqrt(N). Used in physics and finance. Worked example Estimate...

โฑ 1 min read

Overview

A random walk is a path of random steps. Monte Carlo estimates quantities by sampling.

Key ideas

  • Simulate many walks.
  • Error ~ 1/sqrt(N).
  • Used in physics and finance.

Worked example

Estimate pi: N random points, pi ~ 4*(inside/total).

Common pitfalls

  • Too few samples gives high variance.

Why it matters

Complex integrals can be estimated by simulation.

5

Probability Distributions and Inference

Overview Distributions describe how likely each outcome is. Key ideas Discrete: Bernoulli, binomial, Poisson. Continuous: uniform, normal. Maximum likelihood. Worked example 8 heads in 10 flips gives...

โฑ 1 min read

Overview

Distributions describe how likely each outcome is.

Key ideas

  • Discrete: Bernoulli, binomial, Poisson.
  • Continuous: uniform, normal.
  • Maximum likelihood.

Worked example

8 heads in 10 flips gives MLE p=0.8.

Common pitfalls

  • Assuming normality without checking.

Why it matters

Inference is how we learn from data.

6

Linear Regression

Overview The simplest predictive model: fit a line to data. Key ideas Minimise squared error. Normal equations. Regularisation prevents overfitting. Worked example Slope = cov(x,y)/var(x). Intercept...

โฑ 1 min read

Overview

The simplest predictive model: fit a line to data.

Key ideas

  • Minimise squared error.
  • Normal equations.
  • Regularisation prevents overfitting.

Worked example

Slope = cov(x,y)/var(x). Intercept = mean(y) - slope*mean(x).

Common pitfalls

  • Extrapolating beyond range.

Why it matters

Regression is the entry to supervised learning.

7

Classification and Logistic Regression

Overview When target is a category, regression is not enough. Key ideas Sigmoid squashes output to (0,1). Linear decision boundary. Log-loss minimisation. Worked example Predict spam from word...

โฑ 1 min read

Overview

When target is a category, regression is not enough.

Key ideas

  • Sigmoid squashes output to (0,1).
  • Linear decision boundary.
  • Log-loss minimisation.

Worked example

Predict spam from word counts.

Common pitfalls

  • Thresholding at 0.5 on imbalanced data.

Why it matters

Classification is the workhorse of practical ML.

8

Clustering

Overview Unsupervised learning: group data without labels. Key ideas k-means alternates assign/recompute. Hierarchical builds a merge tree. Silhouette evaluation. Worked example Cluster customers by...

โฑ 1 min read

Overview

Unsupervised learning: group data without labels.

Key ideas

  • k-means alternates assign/recompute.
  • Hierarchical builds a merge tree.
  • Silhouette evaluation.

Worked example

Cluster customers by purchase history with k=5.

Common pitfalls

  • Assuming spherical clusters.

Why it matters

Clustering reveals hidden structure.

9

Model Selection and Cross-Validation

Overview A model fitting training data perfectly may be useless on new data. Key ideas Split: train/validation/test. k-fold cross-validation. Occams razor. Worked example Train 80%, tune 10%, test...

โฑ 1 min read

Overview

A model fitting training data perfectly may be useless on new data.

Key ideas

  • Split: train/validation/test.
  • k-fold cross-validation.
  • Occams razor.

Worked example

Train 80%, tune 10%, test 10% with 5 splits.

Common pitfalls

  • Tuning on test set.

Why it matters

Reliable evaluation separates a model from a guess.

10

Bias, Fairness, and the Limits of Models

Overview Data-driven systems can amplify social biases. Key ideas Bias enters at collection, labelling, modelling, deployment. Multiple fairness definitions. Model cards. Worked example A hiring...

โฑ 1 min read

Overview

Data-driven systems can amplify social biases.

Key ideas

  • Bias enters at collection, labelling, modelling, deployment.
  • Multiple fairness definitions.
  • Model cards.

Worked example

A hiring model trained on historical data may reproduce past discrimination.

Common pitfalls

  • Assuming math is neutral.

Why it matters

A model is not neutral because it is mathematical.

๐Ÿ“ Knapsack and Greedy

Q1. Show greedy 0/1 knapsack is suboptimal.

Show Solution

Capacity 10; items (6,6),(5,5),(5,5).

๐Ÿ“ Monte Carlo

Q1. Estimate pi via random points.

Show Solution

pi ~ 4 * inside/total; error ~ 1/sqrt(N).

๐ŸŽฏ Midterm Exam

Q1. Estimate pi via Monte Carlo for N=1000 and N=10000; compare errors.

Show Solution

Error scales as 1/sqrt(N).

Q2. Show that greedy 0/1 knapsack can be suboptimal.

Show Solution

Provide a counterexample.

๐ŸŽฏ Final Exam

Q1. Fit a linear regression to the given dataset and report residuals.

Show Solution

Normal equations or gradient descent.

Q2. Explain the bias-variance trade-off with an example from k-NN.

Show Solution

Small k: low bias high variance; large k: opposite.