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