Data Science is the interdisciplinary field that uses scientific methods, algorithms, and systems to extract knowledge and insights from structured and unstructured data. It combines statistics, computer science, and domain expertise.

Mathematics & Statistics (modelling, inference), Computer Science (algorithms, scalable systems), and Domain knowledge (asking the right questions).

Big Data refers to extremely large, complex datasets that cannot be processed by traditional tools. It is characterized by the 4 Vs — Volume, Velocity, Variety, Veracity — and requires distributed systems like Hadoop or Spark.

Volume (size — terabytes/petabytes), Velocity (speed of arrival — real-time streams), Variety (structured + semi-structured + unstructured), Veracity (trustworthiness, noise level). Often a fifth V — Value — is added.

Data Science is the broad field of extracting insight from data (wrangling, EDA, statistics, ML, visualisation, deployment). Machine Learning is a specific tool inside data science — algorithms that learn patterns from data automatically.

Builds predictive models, performs statistical analysis, runs experiments, communicates insights. Uses Python/R, statistics, ML libraries (scikit-learn, TensorFlow), and translates business problems into data problems.

Builds data infrastructure — ETL/ELT pipelines, data warehouses, real-time streaming systems — so that clean data reaches analysts and scientists. Uses SQL, Spark, Kafka, Airflow, cloud services.

A hybrid software + ML role focused on deploying ML models to production at scale. Wraps prototype models as APIs, handles serving, monitoring, retraining. Uses Docker, Kubernetes, MLflow, PyTorch/TensorFlow.

CRISP-DM (Cross-Industry Standard Process for Data Mining) is a six-phase framework for data science projects: Business Understanding → Data Understanding → Data Preparation → Modelling → Evaluation → Deployment. Iterative — phases loop back as needed.

A 5-step data-science workflow: Obtain, Scrub, Explore, Model, iNterpret. Simpler than CRISP-DM, focuses on the analyst's day-to-day workflow.

The process of transforming raw, messy data into clean, model-ready form. Includes cleaning, integration, transformation, reduction, and discretization. Typically consumes 60–80% of a project.

Data organised in a predefined schema (rows + columns), typically in relational databases. Example: a customer table with columns id, name, age, email.

Data with some organisational structure but no rigid schema — uses tags or keys. Examples: JSON and XML files, NoSQL document databases.

Data with no predefined format — needs feature extraction. Examples: free text (emails, reviews), images, audio, video. Forms ~80% of enterprise data.

$z_i = \dfrac{x_i - \mu}{\sigma}$. Points with $|z_i| > 3$ are flagged as outliers. Assumes the data is roughly Normal.

A point is an outlier if it lies outside $[Q_1 - 1.5 \cdot IQR, \; Q_3 + 1.5 \cdot IQR]$, where $IQR = Q_3 - Q_1$. Robust to skewed distributions.

Synthetic Minority Oversampling Technique — generates synthetic samples of the minority class by interpolating between existing minority points. Used to balance imbalanced classification datasets.

Converts a categorical feature with $K$ values into $K$ binary columns, with exactly one column = 1 per row. Used so categorical features can be fed into numeric ML algorithms without implying false order.

$x' = \dfrac{x - \mu}{\sigma}$. Transforms a feature to have zero mean and unit variance. Required for distance-based and gradient-based models (k-NN, SVM, neural nets).

$x' = \dfrac{x - \min}{\max - \min}$. Maps a feature to the $[0, 1]$ range. Sensitive to outliers but useful for neural nets with sigmoid activations.

• Mean — arithmetic average $\bar x = \dfrac{1}{n}\sum x_i$. Sensitive to outliers.
• Median — middle value when sorted. Robust.
• Mode — most frequent value. Useful for categorical data.

Variance $\sigma^2 = \dfrac{1}{n}\sum (x_i - \bar x)^2$ — average squared deviation. Standard deviation $\sigma = \sqrt{\sigma^2}$ — same units as the data, the most interpretable measure of spread.

A measure of asymmetry of a distribution. $\text{Skew} > 0$ means right-skewed (long right tail; income); $\text{Skew} < 0$ means left-skewed; $\text{Skew} = 0$ is symmetric.

A measure of tailedness. Leptokurtic ($> 0$ excess) — fat tails, more outliers (stock returns). Platykurtic ($< 0$) — thin tails, flat top. Normal distribution has excess kurtosis 0.

$(\min, Q_1, \text{median}, Q_3, \max)$. Forms the basis of the box plot — a quick visual summary of distribution centre, spread, and outliers.

The five-number summary visually: a box from $Q_1$ to $Q_3$, line at median, whiskers to the most extreme non-outlier points, and individual points outside $Q_1 - 1.5 \cdot IQR$ or $Q_3 + 1.5 \cdot IQR$ as outliers.

$r = \dfrac{\sum (x_i - \bar x)(y_i - \bar y)}{\sqrt{\sum (x_i - \bar x)^2 \sum (y_i - \bar y)^2}}$. Range $[-1, 1]$; measures linear association.

$\hat y = \beta_0 + \beta_1 x$, where $\beta_0$ is the intercept and $\beta_1$ is the slope. Fit by OLS (minimise sum of squared residuals).

The coefficient of determination: $R^2 = 1 - \dfrac{SSE}{SST}$. Ranges 0 to 1; the fraction of variance in $y$ explained by the model. For simple regression, $R^2 = r^2$.

A condition where two or more predictors in a regression are strongly linearly related. Inflates coefficient variances and unstabilises the model. Detected with VIF (Variance Inflation Factor) — VIF > 5 or 10 is concerning.

$\text{MSE} = \dfrac{1}{n}\sum (y_i - \hat y_i)^2$. Penalises large errors quadratically. Differentiable and used as a training loss.

$\text{RMSE} = \sqrt{\text{MSE}}$. Has the same units as $y$, so it is more interpretable than MSE. Most commonly reported regression metric.

$\text{MAE} = \dfrac{1}{n}\sum |y_i - \hat y_i|$. Mean absolute error. Robust to outliers (no squaring), but not as smooth for optimization.

$R^2 = 1 - \dfrac{SS_{res}}{SS_{tot}}$ — fraction of variance in $y$ explained. 1 = perfect fit, 0 = no better than mean. Can be negative on test data when model is very bad.

The model learns the training data — including its noise — so closely that it fails on new data. Symptom: training error very low, test error high.

The model is too simple to capture the underlying pattern. Symptom: both training and test errors are high.

Total error = $\text{Bias}^2 + \text{Variance} + \text{Noise}$. Simpler models have high bias, low variance; complex models reverse. Optimal complexity minimises both.

Split data into $k$ equal folds. For each $i = 1, \dots, k$, train on the other $k-1$ folds and validate on fold $i$. Average the $k$ scores. Common $k = 5$ or $10$.

A special case of k-fold with $k = n$. Each iteration trains on $n-1$ points and validates on 1. Almost unbiased but very expensive — used for very small datasets.

A regularisation technique for iterative models (gradient boosting, neural networks): stop training when validation error stops improving — prevents overfitting from training too long.

A data structure where elements are arranged sequentially, each (except first/last) having one predecessor and one successor. Examples: array, linked list, stack, queue.

A structure where elements are arranged hierarchically or in a network — not sequentially. Examples: tree, graph, heap.

Stack is LIFO (Last-In-First-Out) — push/pop at the top. Used in function calls, undo, DFS. Queue is FIFO (First-In-First-Out) — enqueue at back, dequeue at front. Used in BFS, scheduling.

$O(\log n)$. Each step halves the search space. Requires the array to be sorted.

$O(n \log n)$ in all cases (best, average, worst). Stable, but uses extra $O(n)$ memory for merging.

Asymptotic upper bound on growth: $T(n) = O(f(n))$ means there exist constants $c, n_0$ with $T(n) \le c \cdot f(n)$ for all $n \ge n_0$. Used for worst-case analysis.

An algorithm-design technique with three steps: Divide the problem into sub-problems, Conquer by recursion, Combine sub-solutions. Examples: merge sort, binary search, FFT.

Builds a solution one step at a time, always making the locally optimal choice. Works when the problem has the greedy-choice property and optimal substructure. Examples: Kruskal's MST, Huffman coding, Dijkstra.

A search technique that explores partial solutions depth-first and abandons branches that violate constraints. Used for constraint-satisfaction problems like N-Queens, Sudoku, Maze solving.

$O(n^2)$ in average and worst cases. Compares and swaps adjacent pairs in repeated passes. Inefficient for large data — used mainly for teaching.

A data science project is a step-by-step process to turn raw data into business value. The most widely used framework is CRISP-DM (Cross-Industry Standard Process for Data Mining), which has six stages.

Stage 1 — Business Understanding. Understand what the business wants and convert it into a data problem.

• Define the goal in clear terms.
• Set a success metric.
• Example: A bank wants to reduce loan defaults → goal: predict who is likely to default before approving a loan.

Stage 2 — Data Understanding. Collect the data and explore it to understand what we have.

• Gather data from CRM, transactions, surveys, etc.
• Run basic checks — find missing values, outliers, errors.
• Look at distributions and summary statistics.

Stage 3 — Data Preparation. (takes 60–80% of project time) Make data ready for modelling.

• Clean: remove duplicates, fix errors, handle missing values.
• Transform: scale numbers, encode categories.
• Feature engineering: create useful new features.
• Split into training and test sets.

Stage 4 — Modelling. Build and train machine-learning models.

• Try multiple algorithms (e.g., Logistic Regression, Random Forest, XGBoost).
• Tune parameters using cross-validation.
• Compare results to pick the best.

Stage 5 — Evaluation. Test the model on unseen data.

• Check accuracy, precision, recall, etc.
• Match it with business success criteria.
• Audit for fairness and bias.
• Decide: deploy / improve / abandon.

Stage 6 — Deployment. Put the model into production use.

• Wrap as API or batch job.
• Monitor performance over time.
• Retrain regularly when data changes.
• Document everything.

Iterative Nature. The arrows in CRISP-DM go both ways — you often loop back. For example, evaluation may show the model is poor → return to data preparation or business understanding.

Why CRISP-DM is Important:

• Keeps the project focused on business value.
• Prevents wasted effort.
• Standard framework across industries.
• Easy to communicate progress to stakeholders.

Conclusion. A clear data science process like CRISP-DM is essential to deliver successful projects. Without it, teams jump straight to modelling and often build something that doesn't solve the real problem.

A modern data science team has specialized roles. Each owns a different part of the work — from data collection to model deployment.

1. Data Analyst.

• Focuses on understanding what happened in the past.
• Creates dashboards and reports for business teams.
• Skills: SQL, Excel, Tableau, Power BI, basic statistics.
• Tools: SQL databases, BI tools.
• Example task: Build a monthly sales dashboard showing top regions.

2. Data Scientist.

• Builds predictive models using machine learning.
• Designs experiments (A/B tests).
• Communicates results to stakeholders.
• Skills: Python/R, statistics, ML algorithms, data visualization.
• Tools: Jupyter, scikit-learn, pandas, TensorFlow.
• Example task: Build a customer churn prediction model.

3. Data Engineer.

• Builds the data pipelines and infrastructure.
• Makes sure clean, reliable data reaches analysts and scientists.
• Manages databases and data warehouses.
• Skills: SQL, Python, Spark, Kafka, cloud (AWS/Azure/GCP).
• Tools: Airflow, Snowflake, BigQuery, dbt.
• Example task: Move sales data from MySQL to Snowflake every hour.

4. Machine Learning Engineer.

• Takes prototype models and deploys them to production.
• Builds scalable, low-latency systems.
• Monitors model performance and retrains when needed.
• Skills: Python, Docker, Kubernetes, software engineering.
• Tools: MLflow, FastAPI, AWS SageMaker.
• Example task: Deploy fraud detection model as a REST API serving 1000 requests/sec.

5. Business Analyst.

• Bridges the business team and the data team.
• Translates business questions into data problems.
• Presents insights to non-technical stakeholders.
• Skills: Domain knowledge, SQL, Excel, storytelling.

Comparison Table.

How They Work Together.

• Data Engineer prepares the pipelines.
• Data Analyst explores the data and reports trends.
• Data Scientist builds predictive models.
• ML Engineer deploys models in production.
• Business Analyst connects everything to business goals.

Note. In small startups, one person may do several roles. In large companies, the roles are clearly separated. Job titles vary across companies, but the responsibilities follow these patterns.

Definition. Big Data refers to extremely large and complex datasets that cannot be processed using traditional tools (Excel, simple databases). It requires special technologies like Hadoop and Spark.

The 4 V's of Big Data.

1. Volume (Size of Data).

• Refers to massive amounts of data — terabytes (TB) or petabytes (PB).
• Cannot fit on a single machine; needs distributed storage.
• Example: Facebook generates about 4 PB per day. Walmart processes 2.5 PB of customer transactions per hour.

2. Velocity (Speed of Data).

• Speed at which new data arrives and must be processed.
• Often real-time or near real-time.
• Example: Stock market data updates every millisecond. IoT sensors send readings every second. Twitter generates 500 million tweets per day.

3. Variety (Different Types of Data).

• Structured: SQL tables, spreadsheets.
• Semi-structured: JSON, XML, log files.
• Unstructured: text, images, videos, audio.
• Example: A social media app handles user profiles (structured), posts (text), photos (image), and videos.

4. Veracity (Trustworthiness of Data).

• Quality and reliability of the data.
• Big data often has noise, errors, and inconsistencies.
• Must be cleaned and validated.
• Example: Sensor readings may be wrong. Social media has spam and fake accounts. Manual entries have typos.

5th V — Value (often added)

• The final goal: extract business value from data.
• Without value, big data is just storage cost.

Tools Used for Big Data.

Real-life Examples.

• Netflix: recommends shows from billions of viewing events.
• Amazon: tracks every click and purchase to suggest products.
• Google: indexes the entire web continuously.
• Banks: monitor fraud in real-time across millions of transactions.
• Healthcare: analyses genomic data, medical images, electronic health records.

Challenges with Big Data.

• High storage and computing cost.
• Need for skilled data engineers.
• Privacy concerns (GDPR, HIPAA).
• Data quality maintenance.
• Choosing the right tools.

Conclusion. Big Data is at the heart of modern business. Companies that handle volume, velocity, variety, and veracity successfully gain a competitive advantage by understanding customers better and making faster decisions.

Data in organizations comes in different forms. Knowing the type helps choose the right storage, processing tools, and analysis methods.

Three Main Types of Data.

1. Structured Data.

• Organized in fixed rows and columns.
• Has a clear schema (fields and types defined).
• Easy to query using SQL.
• Examples: Customer table (ID, Name, Email), bank transactions, employee salary records.
• Sources: MySQL, Oracle, PostgreSQL, Excel, CSV files.
• About 20% of total enterprise data.

2. Semi-structured Data.

• Has some organization but no strict schema.
• Uses tags or markers to separate elements.
• Flexible — fields can vary between records.
• Examples: JSON files, XML documents, log files, NoSQL documents.
• Sources: Web APIs (REST, GraphQL), MongoDB, server logs, email metadata.
• Easier to exchange between systems.

3. Unstructured Data.

• No fixed format or schema.
• Cannot be stored in tables directly.
• Needs feature extraction (NLP, image processing) before analysis.
• Examples: Emails, social media posts, images, videos, audio, PDFs.
• Sources: Cameras, microphones, websites, customer reviews, support tickets.
• About 80% of enterprise data — biggest source of insight but hardest to use.

Comparison Table.

Data Collection Sources.

1. Primary Sources (collected new for the project)

• Surveys, sensors, web scraping, A/B tests.
• More control over quality, but expensive.

2. Secondary Sources (existing data, reused)

• Internal databases (CRM, ERP).
• Public datasets (Kaggle, UCI, government).
• Third-party APIs (Twitter, weather, stock).
• Cheaper, faster — but less control.

Common Sampling Methods.

• Simple random sampling — every item has equal chance.
• Stratified sampling — preserves proportion of subgroups.
• Cluster sampling — pick whole groups (e.g., schools, cities).
• Convenience sampling — easy-to-access subset; may be biased.

Importance.

• Most real-world projects mix all three data types.
• Data scientists must be skilled at all three.
• Choice of source affects model quality.
• Bias and privacy must be considered carefully.

Conclusion. Understanding types of data and their sources is the foundation of any data science project. The cleaner and more representative the data, the better the final model.

Definition. Data cleaning is the process of fixing or removing incorrect, incomplete, duplicate, or wrongly formatted data so the model gets reliable input.

Why Important.

• Real data is messy and full of errors.
• Garbage in, garbage out — bad data gives bad models.
• Cleaning takes 60–80% of project time but has huge impact on quality.

Main Cleaning Techniques.

1. Handling Missing Values.

Missing data is common in real datasets. Three approaches:

• Delete — drop rows or columns with missing data. Quick but loses information.
• Impute — fill missing values with:
  • Mean / median for numeric columns.
  • Mode for categorical columns.
  • KNN imputation — use nearest neighbours.
  • Model-based imputation.
• Flag — add an extra column indicating "missing" — captures the fact that missing-ness itself is informative.

Example: In a patient dataset with missing blood pressure for 5% of records, fill with the median by age group and add a "BP_missing" flag.

2. Handling Outliers.

Outliers are extreme values that don't fit the pattern.

Detection:

• Z-score — flag if $|z| > 3$.
• IQR rule — flag values outside $[Q_1 - 1.5 \cdot IQR, \; Q_3 + 1.5 \cdot IQR]$.
• Box plot — outliers appear as dots.

Treatment:

• Remove if clearly an error (e.g., age = 200).
• Cap to a reasonable maximum (winsorize).
• Transform using log to reduce the impact.
• Keep if outlier is meaningful (e.g., fraud transaction).

3. Handling Duplicates.

• Exact duplicates — easy to find and remove with one line.
• Fuzzy duplicates — same person with different spelling ("John Smith" vs "Jon Smith"). Use techniques like Levenshtein distance or phonetic matching.

Example: In a CRM, deduplicate customer names using fuzzy matching.

4. Fixing Inconsistent Formats.

• Convert all dates to one format (e.g., YYYY-MM-DD).
• Standardize units (kg vs lbs).
• Lowercase and trim text fields.
• Fix encoding errors (UTF-8 standard).

Example: "NEW YORK", "new york", "New York " should all become "new york".

5. Removing Noise.

For sensor data and time series:

• Moving average smoothing.
• Exponential smoothing.
• Wavelet denoising.

Tools.

• pandas, NumPy in Python.
• OpenRefine for interactive cleaning.
• Great Expectations for automated quality checks.

Conclusion. Data cleaning is the most critical preprocessing step. A simple model trained on clean data often beats a complex model trained on dirty data. Always validate after cleaning.

Definition. Data transformation reshapes raw features into a form that machine learning algorithms can use effectively.

Why Needed.

• Algorithms expect numeric input.
• Different features may have very different scales (income in lakhs vs age in years).
• Skewed distributions hurt linear models.
• Some categorical features need to be converted into numbers.

Main Transformation Techniques.

1. Scaling (Normalisation).

Makes features comparable in scale.

• Standardization (z-score): $x' = \dfrac{x - \mu}{\sigma}$

  • Mean becomes 0, standard deviation becomes 1.
  • Used for: k-NN, SVM, Neural Networks, PCA.

• Min-Max scaling: $x' = \dfrac{x - \min}{\max - \min}$

  • Maps values to [0, 1].
  • Used for: Neural Networks with sigmoid activation.

• Robust scaling: uses median and IQR instead of mean and std.

  • Better when there are outliers.

Example: Annual income (in lakhs) and age (in years) have very different scales. Without scaling, k-NN distance is dominated by income.

2. Encoding Categorical Variables.

Convert categories into numbers so ML can use them.

• One-Hot Encoding: Each category becomes a separate binary column.

  • Example: "color" with values {Red, Green, Blue} → 3 columns: is_Red, is_Green, is_Blue.
  • Use for: nominal categories (no order).

• Ordinal Encoding: Assign integers in order.

  • Example: education {High School, Bachelors, Masters} → 1, 2, 3.
  • Use for: ordered categories.

• Target Encoding: Replace category with the average target value for that category.

  • Powerful but risk of data leakage.

3. Skew Correction.

Many real-world variables (income, salary, time) are right-skewed.

• Log transform: $x' = \ln(x + 1)$.
• Square root: $x' = \sqrt x$.
• Box-Cox: automatically selects the best power transform.

Example: Income distribution is heavily right-skewed. Log transform makes it roughly Normal — better for linear regression.

4. Date / Time Features.

Extract useful parts from datetime:

• Day of week, hour of day, month.
• Is_weekend, is_holiday.
• Time since last event.
• Cyclical encoding using sine and cosine for hours.

5. Feature Engineering.

Create new useful features from existing ones.

• Ratios: debt/income for credit scoring.
• Aggregations: total purchases per month per customer.
• Interactions: product of two features.
• Domain-driven features: RFM (Recency, Frequency, Monetary) in retail.

Comparison Table.

Best Practice. Apply same transformation at training and inference — use a pipeline. Fit the transformer on training data only to avoid data leakage.

Conclusion. Good data transformation often improves model accuracy more than choosing a fancier algorithm. Always understand your data's distribution before deciding which transformation to apply.

Definition. Data reduction reduces the size of a dataset (rows or features) while preserving important information. Helps with faster training, lower memory use, and better model performance.

Why Reduce Data?

• High-dimensional data leads to curse of dimensionality — models struggle.
• Faster computation.
• Less risk of overfitting.
• Easier visualization.
• Reduced storage cost.

Main Reduction Techniques.

1. Feature Selection (keep useful features, drop the rest).

Three families:

• Filter Methods (use statistics, model-independent)

  • Variance threshold — drop features with near-zero variance.
  • Chi-square test — categorical features vs categorical target.
  • Correlation filter — drop highly correlated features.
  • Mutual information — captures non-linear relationships.

• Wrapper Methods (use the model itself to score subsets)

  • Forward selection — add one feature at a time.
  • Backward elimination — remove one at a time.
  • Recursive Feature Elimination (RFE).
  • Expensive but accurate.

• Embedded Methods (selection inside model training)

  • L1 Regularization (Lasso) — pushes coefficients to zero.
  • Tree-based importance (Random Forest, XGBoost).

2. Dimensionality Reduction (create new compact features).

• Principal Component Analysis (PCA)

  • Finds new directions of maximum variance.
  • Keeps top k components that capture, say, 95% of variance.
  • Linear method, unsupervised.

• Linear Discriminant Analysis (LDA)

  • Like PCA but supervised — maximizes class separation.
  • Limited to (k-1) dimensions for k classes.

• t-SNE and UMAP

  • Non-linear methods for visualization.
  • Preserve local neighbourhoods.

• Autoencoders

  • Neural network compresses to a small latent vector.

3. Numerosity Reduction (reduce number of rows).

• Sampling — random or stratified subset.
• Aggregation — daily data → monthly summary.
• Clustering — replace each cluster with its centroid.

4. Discretization (bin continuous variables).

• Equal-width binning: e.g., age 0–20, 21–40, 41–60, 61+.
• Equal-frequency binning: each bin contains the same count.
• Used for decision trees, Naive Bayes, business reporting.

Example — PCA.

A dataset has 100 gene expression features but only 50 patients. PCA reduces 100 dimensions to 10 components that capture 95% of variance — speeds modelling and reduces overfitting.

Comparison Table.

Conclusion. Smart data reduction makes models faster, less prone to overfitting, and easier to interpret. Choose the method based on what you want to keep: original features (use selection) or new compressed features (use PCA, etc.).

Definition. Data integration is the process of combining data from different sources into a single, unified view that downstream analysis and models can use.

Why Needed.

• Real organizations have data scattered across many systems: CRM, billing, web logs, mobile apps, third-party APIs.
• One system alone cannot answer cross-functional business questions.
• Integration gives a complete view (e.g., customer 360° view).

Methods of Data Integration.

1. ETL (Extract, Transform, Load).

• Extract data from sources.
• Transform it (clean, join, format) in a separate engine.
• Load clean data into the target warehouse.
• Used in traditional on-premise systems.
• Tools: Informatica, Talend, SSIS.

2. ELT (Extract, Load, Transform).

• Extract data and load raw into the warehouse first.
• Transform inside the warehouse using SQL/dbt.
• Modern cloud approach.
• Tools: Snowflake + dbt, BigQuery + dbt.
• Keeps raw data — easier to re-process when needs change.

3. Data Virtualization.

• Query across multiple sources without physically moving data.
• A virtual layer combines results in real-time.
• Tools: Denodo, Trino.

4. Data Lake.

• Single storage for all raw data (structured + unstructured).
• Schema applied later when querying ("schema-on-read").
• Tools: AWS S3, Azure Data Lake, Delta Lake.

5. Data Lakehouse.

• Combines data lake + warehouse features.
• Stores raw + curated together.
• Tools: Databricks, Delta Lake, Apache Iceberg.

Common Challenges.

1. Schema Mismatch.

• Same concept stored differently across sources.
• Example: "cust_id" in one system, "CustomerID" in another.
• Fix: schema mapping or transformation rules.

2. Entity Resolution (Duplicate Detection).

• Same person appears differently across systems.
• Example: "Mohammed Ali" in one, "Mohamed Ali" in another.
• Fix: fuzzy matching, record linkage.

3. Data Type and Unit Conflicts.

• One source stores weight in kg, another in lbs.
• Fix: type coercion and unit conversion.

4. Value Conflicts.

• Two sources disagree on the same fact.
• Fix: last-write-wins, source trust scores, manual review.

5. Data Quality.

• Some sources are noisier than others.
• Fix: validation rules using Great Expectations or Soda.

6. Real-Time vs Batch.

• Some data needs real-time integration (fraud); some batch is fine.
• Tools: Kafka for real-time, Airflow for batch.

Best Practices.

• Document data lineage (where each field comes from).
• Build a data dictionary.
• Automate quality checks.
• Use a feature store for ML features.
• Plan for incremental updates rather than full reloads.

Conclusion. Data integration is the foundation of analytics. Without it, every team sees a partial view, leading to inconsistent reports and poor decisions. A well-integrated data platform is what separates data-mature organizations from the rest.

Definition. Descriptive statistics summarize the main features of a dataset without making any predictions. It is the first step of Exploratory Data Analysis (EDA).

Three Areas of Descriptive Statistics.

1. Measures of Central Tendency (where is the centre?)

• Mean = sum of all values / number of values

  • $\bar x = \dfrac{1}{n}\sum x_i$
  • Most common; sensitive to outliers.

• Median = middle value when sorted

  • Robust to outliers.
  • Best for skewed data (income, house prices).

• Mode = most frequent value

  • Useful for categorical data.
  • A dataset can have multiple modes.

Example. Salaries: 30k, 32k, 33k, 35k, 200k.

• Mean = 66k (pulled up by outlier).
• Median = 33k (more representative).
• Mode = none (all unique).

2. Measures of Dispersion (how spread out is the data?)

• Range = max − min

  • Simple; sensitive to outliers.

• Inter-Quartile Range (IQR) = $Q_3 - Q_1$

  • Middle 50% spread; robust.

• Variance = average of squared deviations from mean

  • $\sigma^2 = \dfrac{1}{n}\sum (x_i - \bar x)^2$

• Standard Deviation = square root of variance

  • $\sigma = \sqrt{\sigma^2}$
  • Same units as data; most reported.

• Coefficient of Variation $CV = \sigma / \bar x$

  • Scale-free; compares variability across different units.

Example. For (2, 4, 4, 4, 5, 5, 7, 9): mean = 5, variance = 4, std = 2.

3. Measures of Shape (what does the distribution look like?)

• Skewness — measures asymmetry.

  • Skew = 0: symmetric.
  • Skew > 0: right-skewed (long right tail; e.g., income).
  • Skew < 0: left-skewed (long left tail; e.g., exam scores capped at 100).

• Kurtosis — measures tail heaviness.

  • High kurtosis: fat tails (more outliers, e.g., stock returns).
  • Low kurtosis: thin tails (flatter top).

Five-Number Summary.

$(\min, Q_1, \text{median}, Q_3, \max)$ — visualized as a box plot.

Why Important.

• Quickly understand the data.
• Spot data-quality issues (impossible values).
• Decide which transformations to apply (e.g., log for skewed data).
• Choose the right model (parametric vs non-parametric).
• Identify outliers.

Worked Example. Incomes (₹k): 20, 24, 26, 30, 35, 40, 45, 60, 200.

• Mean = 53.3, Median = 35 (median is more representative).
• Std ≈ 56 (large spread due to outlier).
• Skewness > 0 (right-skewed).
• Conclusion: log-transform the income before modelling; report median, not mean.

Conclusion. Descriptive statistics are simple but powerful tools that drive every downstream modelling decision. Always start data analysis with them.

Why Visualize.

• Pictures reveal patterns that numbers hide.
• Faster than reading raw data.
• Helps spot outliers, trends, and relationships.
• Critical for stakeholder communication.

Common Visualizations.

1. Histogram.

• Shows distribution of one numeric variable using bars.
• Reveals shape (Normal, skewed, bimodal).
• Use: see how customer age is distributed.

2. Box Plot.

• Shows five-number summary: min, $Q_1$, median, $Q_3$, max.
• Highlights outliers as dots.
• Use: compare salaries across departments.

3. Scatter Plot.

• Points $(x, y)$ for two numeric variables.
• Reveals relationships, clusters, outliers.
• Use: study hours vs exam marks.

4. Bar Chart.

• Bars showing counts or values for categorical data.
• Use: sales by region.

5. Pie Chart.

• Shows parts of a whole.
• Use sparingly — bar charts are usually clearer.
• Use: market share of competitors.

6. Line Plot.

• Connects points over time.
• Use: monthly revenue trend.

7. Heatmap.

• 2D matrix with colour-coded values.
• Use: correlation matrix, student-subject performance, hour-of-day vs day-of-week traffic.

8. Pair Plot (Scatter Matrix).

• Grid of scatter plots for every pair of features.
• Histograms on the diagonal.
• Use: quick view of all pairwise relationships in a small dataset.

9. Violin Plot.

• Combines box plot + density curve.
• Shows distribution shape more clearly than box plot.

10. Pivot Table.

• Multi-dimensional summary across two grouping variables.
• Use: revenue by region × quarter.

Summary Table.

Tools.

• Python: matplotlib, seaborn, plotly.
• R: ggplot2.
• Dashboards: Tableau, Power BI, Looker.

Best Practices.

• Always label axes and add titles.
• Use color thoughtfully (color-blind friendly).
• Avoid 3D charts — they confuse rather than help.
• Use small multiples (many small plots) for comparing groups.

Conclusion. A good visualization is worth a thousand statistical tests. EDA without plots is incomplete — always combine summary numbers with visual exploration before modelling.

Definition. Simple Linear Regression models the relationship between one predictor variable $x$ and a continuous response $y$ as a straight line:

$\hat y = \beta_0 + \beta_1 x.$

• $\beta_0$ = intercept (value of $y$ when $x = 0$).
• $\beta_1$ = slope (change in $y$ for one-unit change in $x$).

Goal. Find $\beta_0$ and $\beta_1$ that minimize the Sum of Squared Errors (SSE):

$\text{SSE} = \sum (y_i - \hat y_i)^2.$

OLS Derivation.

Take partial derivatives of SSE with respect to $\beta_0$ and $\beta_1$ and set them to zero:

$\dfrac{\partial \text{SSE}}{\partial \beta_0} = -2 \sum (y_i - \beta_0 - \beta_1 x_i) = 0$.

$\dfrac{\partial \text{SSE}}{\partial \beta_1} = -2 \sum x_i (y_i - \beta_0 - \beta_1 x_i) = 0$.

Solving these two equations:

$\boxed{\beta_1 = \dfrac{\sum (x_i - \bar x)(y_i - \bar y)}{\sum (x_i - \bar x)^2}}, \quad \boxed{\beta_0 = \bar y - \beta_1 \bar x}.$

Worked Example.

Data: hours studied $x = (1, 2, 3, 4, 5)$, marks $y = (52, 55, 60, 65, 70)$.

$\bar x = 3, \bar y = 60.4$.

$\beta_1 = 46/10 = 4.6$. $\beta_0 = 60.4 - 4.6 \times 3 = 46.6$.

Fitted Line: $\hat y = 46.6 + 4.6 x$.

Interpretation: Each extra hour of study adds about 4.6 marks.

Goodness of Fit — $R^2$.

$R^2 = 1 - \dfrac{\text{SSE}}{\text{SST}}$, where SST = $\sum (y_i - \bar y)^2$.

For this data, $R^2 \approx 0.99$ — the model explains ~99% of variance.

Assumptions (LINE).

• Linearity — true relationship is linear.
• Independence — residuals are independent.
• Normality — residuals approximately Normal.
• Equal variance (homoscedasticity).

Check assumptions using residual plots.

Use Cases.

• Predict house price from area.
• Forecast sales from advertising spend.
• Estimate crop yield from rainfall.

Conclusion. Simple linear regression is the most basic but most interpretable predictive model. It is the foundation of advanced techniques like multiple regression, logistic regression, and even neural networks.

Definition. Multiple Linear Regression (MLR) extends simple linear regression to multiple predictors:

$\hat y = \beta_0 + \beta_1 x_1 + \beta_2 x_2 + \dots + \beta_p x_p.$

Each $\beta_j$ is the change in $y$ for one-unit increase in $x_j$, holding other features constant.

Why Use Multiple Regression.

• Real-world outcomes depend on multiple factors.
• More predictors usually give better predictions.
• Captures combined effects.

Example. Predict house price using area, bedrooms, and location score: $\hat{\text{price}} = 5.0 + 0.3 \cdot \text{area} + 0.5 \cdot \text{bedrooms} + 1.2 \cdot \text{location}.$

Interpretation:

• Each extra sq.m of area adds ₹0.3 lakh.
• Each extra bedroom adds ₹0.5 lakh (holding area constant).
• Each unit of location score adds ₹1.2 lakh.

Fitting the Model.

Uses Ordinary Least Squares (OLS) — minimize sum of squared residuals.

In matrix form: $\hat \beta = (X^T X)^{-1} X^T y$. (Theory only — not needed to memorize for diploma.)

Goodness of Fit — Two Key Measures.

1. $R^2$ (Coefficient of Determination).

• Fraction of variance in $y$ explained by the model.
• Range: 0 to 1.
• Problem: adding any new predictor (even a useless one) increases $R^2$.

2. Adjusted $R^2$.

$R^2_{adj} = 1 - \dfrac{(1 - R^2)(n - 1)}{n - p - 1},$

where $n$ = number of observations, $p$ = number of predictors.

• Adjusts for the number of predictors.
• Only increases if the new feature actually helps.
• Use for comparing models with different number of features.

Multicollinearity (Important Concept).

Definition: Two or more predictors are strongly linearly related to each other.

Why it's a Problem:

• Makes coefficient estimates unstable.
• Standard errors blow up.
• Sign of coefficients may flip.
• p-values become unreliable.

Detection:

• Pairwise correlation matrix — values > 0.9 are suspicious.
• Variance Inflation Factor (VIF):
  • VIF = 1: no multicollinearity.
  • VIF > 5 or 10: serious problem.

Treatment:

• Drop one of the correlated features.
• Combine them (e.g., total square feet = area × stories).
• Use Ridge Regression (adds penalty to stabilize coefficients).

Example. Predicting house price using area and number of rooms. These are strongly correlated (bigger houses → more rooms). VIF for both > 10. Solution: drop one or combine.

Assumptions of MLR.

• Linearity (relationship is linear).
• Independence of residuals.
• Normality of residuals.
• Constant variance (homoscedasticity).
• No severe multicollinearity.

Conclusion. Multiple Linear Regression is widely used because it's interpretable, fast, and provides a strong baseline. The two big things to watch are multicollinearity (use VIF) and overfitting (use Adjusted $R^2$).

Why Need Evaluation Metrics.

• Different problems weight errors differently.
• The right metric drives the right model choice.
• Helps compare different models.

Main Regression Metrics.

1. Mean Squared Error (MSE).

$\text{MSE} = \dfrac{1}{n}\sum (y_i - \hat y_i)^2.$

• Squares the errors.
• Penalizes big errors more.
• Used as a loss function during training.
• Units = $y^2$ — hard to interpret directly.

2. Root Mean Squared Error (RMSE).

$\text{RMSE} = \sqrt{\text{MSE}}.$

• Square root of MSE.
• Same units as $y$ — easy to interpret.
• Most reported regression metric.
• Sensitive to outliers.

3. Mean Absolute Error (MAE).

$\text{MAE} = \dfrac{1}{n}\sum |y_i - \hat y_i|.$

• Absolute errors averaged.
• Robust to outliers.
• Easier to interpret in business terms.

4. Mean Absolute Percentage Error (MAPE).

$\text{MAPE} = \dfrac{100}{n}\sum \left|\dfrac{y_i - \hat y_i}{y_i}\right|\%.$

• Expressed as percentage.
• Scale-free.
• Problem when $y_i$ is close to zero.

5. $R^2$ (Coefficient of Determination).

$R^2 = 1 - \dfrac{\text{SSE}}{\text{SST}}.$

• Fraction of variance explained.
• 1 = perfect fit, 0 = no better than mean, negative = worse.
• Easy to communicate.

6. Adjusted $R^2$.

Penalizes addition of useless predictors. Use when comparing models with different feature counts.

Comparison Table.

Worked Example.

Actual prices (₹ lakhs): 50, 60, 70, 80, 90. Predicted: 48, 62, 68, 78, 91.

Errors: 2, -2, 2, 2, -1.

• MAE = $(2 + 2 + 2 + 2 + 1)/5 = 1.8$ lakhs.
• MSE = $(4 + 4 + 4 + 4 + 1)/5 = 3.4$.
• RMSE = $\sqrt{3.4} \approx 1.84$ lakhs.

So on average, predictions are off by about ₹1.8 lakh.

When to Use Which.

• Default: RMSE (interpretable).
• With outliers: MAE (robust).
• For business reports: MAPE (percentage).
• Quick overview: $R^2$.
• Comparing models with different number of features: Adjusted $R^2$.

Best Practice.

• Always report multiple metrics.
• Evaluate on a held-out test set, not training.
• Use cross-validation to avoid lucky/unlucky splits.

Conclusion. Choosing the right evaluation metric is as important as choosing the right model. The metric should align with business cost — if missing a prediction by ₹10 lakh is 100× worse than missing by ₹1 lakh, use MSE; if equally bad, use MAE.

Why Classification Metrics.

• Accuracy alone is misleading, especially with imbalanced data.
• Need to balance different kinds of errors.

Confusion Matrix.

For a binary classifier (Yes/No), the confusion matrix shows:

• TP: model says Yes, actually Yes (correct).
• TN: model says No, actually No (correct).
• FP: model says Yes, actually No (Type I error / false alarm).
• FN: model says No, actually Yes (Type II error / miss).

Main Classification Metrics.

1. Accuracy.

$\text{Accuracy} = \dfrac{TP + TN}{TP + TN + FP + FN}.$

• Fraction of correct predictions.
• Misleading for imbalanced data.

2. Precision.

$\text{Precision} = \dfrac{TP}{TP + FP}.$

• Of predicted positives, how many are real?
• Use when false positives are costly (e.g., spam filter — don't lose real emails).

3. Recall (Sensitivity).

$\text{Recall} = \dfrac{TP}{TP + FN}.$

• Of actual positives, how many did we find?
• Use when false negatives are costly (e.g., cancer screening — don't miss patients).

4. F1-Score.

$F_1 = 2 \cdot \dfrac{\text{Precision} \cdot \text{Recall}}{\text{Precision} + \text{Recall}}.$

• Harmonic mean of precision and recall.
• Balanced single number.
• Best for imbalanced data.

5. Specificity.

$\text{Specificity} = \dfrac{TN}{TN + FP}.$

• Of actual negatives, how many correctly identified.

6. ROC-AUC.

• Plot of True Positive Rate vs False Positive Rate as threshold varies.
• Area under the curve = AUC (0.5 = random, 1 = perfect).
• Threshold-independent.

Worked Example.

100 emails: 30 are spam, 70 are not. Model flagged 35 as spam — 28 truly spam, 7 not spam.

• TP = 28, FP = 7, FN = 2 (spam missed), TN = 63.

Compute:

• Accuracy = (28 + 63)/100 = 91%.
• Precision = 28/35 = 80%.
• Recall = 28/30 = 93%.
• F1 = 2 × (0.80 × 0.93)/(0.80 + 0.93) ≈ 0.86.

Which Metric to Use?

Imbalanced Data Warning.

If 99% of data is class 0, a "predict-all-zero" model gives 99% accuracy but is useless. Always use F1, Precision, Recall, or PR-AUC for imbalanced data — never accuracy alone.

Conclusion. Confusion matrix is the foundation of all classification metrics. Always look at the full confusion matrix and choose metrics that match the business cost of errors.

Definition. The total error of a model has three parts:

$\text{Total Error} = \text{Bias}^2 + \text{Variance} + \text{Noise}.$

The Three Components.

1. Bias.

• Error from wrong model assumptions.
• High bias = model too simple (e.g., linear when reality is curved).
• Causes underfitting.

2. Variance.

• Error from being too sensitive to training data.
• High variance = model too complex (memorizes training noise).
• Causes overfitting.

3. Noise.

• Random error in the data that cannot be reduced.

The Tradeoff.

As complexity increases, bias goes down but variance goes up. The "sweet spot" minimises total error.

Underfitting (High Bias).

• Symptoms: Both training and test error are high.
• Cause: Model too simple.
• Fix: More features, more complex model, less regularization.

Overfitting (High Variance).

• Symptoms: Training error very low, test error high (big gap).
• Cause: Model memorizes noise.
• Fix: More data, regularization (L1/L2), dropout, ensembling, early stopping, simpler model.

Good Fit.

• Both errors low and close to each other.
• Model captures the real pattern without learning noise.

Learning Curves — Diagnostic Tool.

A learning curve plots training error and validation error against:

• Training-set size, OR
• Model complexity / training epochs.

Pattern 1 — Underfitting.

• Both curves plateau at high error.
• Adding more data does NOT help.
• Action: increase model complexity, add features.

Pattern 2 — Overfitting.

• Training error very low, validation error stays high.
• Gap between them is wide.
• Action: add data, regularize, simplify.

Pattern 3 — Good Fit.

• Both curves converge to low error.
• Gap is small.
• Action: deploy.

Worked Example.

Random Forest on a small medical dataset:

• Training F1 = 0.95, Validation F1 = 0.71.
• Big gap → overfitting.

Fix:

• Limit tree depth.
• Increase min_samples_leaf.
• Use cross-validation.
• Maybe collect more data.

After tuning: Training F1 = 0.78, Validation F1 = 0.73. Gap closed — model now generalizes.

Comparison Table.

Conclusion. The bias-variance tradeoff is the central idea in machine learning. Always evaluate model on a held-out test set and look at the gap. Learning curves provide a clear visual diagnostic of whether to add data, simplify, or call it done.

What is a Residual.

After fitting a regression model, the residual for each data point is:

$e_i = y_i - \hat y_i,$

where $y_i$ is the actual value and $\hat y_i$ is the predicted value.

A residual plot is a scatter plot of residuals on the y-axis vs predicted values (or one of the predictors) on the x-axis.

Why Plot Residuals.

• Summary numbers like $R^2$ can hide model defects.
• Famous example: Anscombe's quartet has 4 datasets with same $R^2$ but completely different patterns.
• Residual plots check regression assumptions:
  • Linearity
  • Independence
  • Constant variance
  • Normality

Ideal Pattern.

• Random horizontal scatter around zero.
• No clear shape or trend.
• Means model is correct.

Common Bad Patterns and What They Mean.

1. U-Shape (Curved Pattern).

• What: Residuals form a smile or frown.
• Means: Model is missing a non-linear relationship.
• Fix: Add polynomial term ($x^2$) or use non-linear model (decision tree, kernel regression).
• Example: Fitting a straight line to a curved relationship.

2. Funnel Shape (Heteroscedasticity).

• What: Residual spread grows as predictions get larger.
• Means: Error variance is not constant (heteroscedasticity).
• Fix: Log-transform $y$ (especially for prices, salaries); try weighted least squares.
• Example: Residuals small for cheap houses, huge for expensive ones.

3. Trend / Slope in Residuals.

• What: Residuals follow a linear slope.
• Means: Model missed an important predictor.
• Fix: Add the missing variable.
• Example: Predicting sales without seasonality; residuals rise over time.

4. Outliers.

• What: A few points sit far from zero.
• Means: Either real outliers or data-entry errors.
• Fix: Investigate; remove if error, keep if real.

5. Step Pattern.

• What: Sudden jumps between groups.
• Means: Missing categorical effect.
• Fix: Include the categorical feature.

Summary Table.

Other Diagnostic Plots.

• Q-Q plot: checks residual normality. Straight diagonal = Normal.
• Scale-location plot: $\sqrt{|residual|}$ vs predicted. Flat line = constant variance.
• Cook's distance: flags points whose removal significantly changes the fit.

Best Practice.

• Always plot residuals after fitting a regression model.
• Don't rely on $R^2$ alone — it can be high even with bad model fit.
• If residuals show a pattern, fix it before deploying.

Conclusion. Residual plots are the most important diagnostic tool in regression. They expose what summary statistics hide. A good model has random residual scatter around zero — anything else needs to be fixed.

Why Analyze Algorithms.

• Two algorithms for the same problem can differ by millions in performance.
• Empirical timing depends on machine and compiler; mathematical analysis is universal.
• Helps predict whether an algorithm will scale to large data.

Time Complexity.

The number of basic operations an algorithm performs as a function of input size $n$. We care about how it grows as $n$ grows.

Big O Notation.

Big O describes the upper bound on the growth rate:

$T(n) = O(f(n)) \iff T(n) \le c \cdot f(n) \text{ for large } n.$

• We ignore constants and lower-order terms.
• $5 n^2 + 3 n + 7$ is $O(n^2)$.

Common Complexity Classes (slowest to fastest growth).

Practical Impact at $n = 10^6$ (assuming $10^9$ operations/sec).

Three Types of Analysis.

• Best case: luckiest input.
• Average case: expected behaviour on random input.
• Worst case: guaranteed upper bound (most useful).

Example. Quick sort has best/average case $O(n \log n)$ but worst case $O(n^2)$ (when pivot is always smallest or largest).

Space Complexity.

Similar to time, but measures memory used. Some algorithms trade time for space (e.g., dynamic programming uses memory to avoid recomputation).

Examples of Big O Analysis.

Linear Search:

• For each of $n$ elements, do constant work.
• $T(n) = O(n)$.

Binary Search:

• Each step halves the search space.
• $T(n) = O(\log n)$.

Bubble Sort:

• Two nested loops over $n$ elements.
• $T(n) = O(n^2)$.

Merge Sort:

• Splits into halves recursively, then merges in linear time.
• $T(n) = O(n \log n)$.

Why Analysis Matters.

• Predicts scalability before coding the full algorithm.
• Helps choose between algorithms.
• Helps justify infrastructure decisions ("your $O(n^2)$ approach will take 15 hours; switch to $O(n \log n)$").
• In ML, this is why batching and GPUs are essential.

Conclusion. Big O notation is the universal language for algorithm efficiency. Knowing complexity classes helps decide whether an algorithm will work for your data size. Always think about scalability before scaling up.

Definition. Divide and Conquer (D&C) is an algorithm design technique that solves a problem by:

1. Divide the problem into smaller sub-problems.
2. Conquer each sub-problem by recursion.
3. Combine the sub-solutions into the final answer.

Why Use D&C.

• Often turns slow $O(n^2)$ algorithms into fast $O(n \log n)$.
• Sub-problems are independent → easy to parallelize.
• Clean, recursive code.

Example 1 — Binary Search.

Problem: Find a target value $x$ in a sorted array of size $n$.

Algorithm:

1. Look at the middle element.
2. If it equals $x$, return.
3. If $x$ is smaller, search the left half.
4. If $x$ is larger, search the right half.
5. Repeat until found or array is empty.

Time Complexity: $T(n) = O(\log n)$.

Each step halves the search space, so after $\log_2 n$ steps the array is reduced to one element.

Example. Search for 25 in [3, 8, 12, 17, 25, 31, 42].

• Step 1: middle is 17, smaller → search right.
• Step 2: middle of [25, 31, 42] is 31, larger → search left.
• Step 3: middle of [25] is 25 → found.

Only 3 comparisons instead of up to 7 with linear search.

Example 2 — Merge Sort.

Problem: Sort an array of $n$ elements.

Algorithm:

1. Divide: split the array into two halves.
2. Conquer: recursively sort each half.
3. Combine: merge the two sorted halves.

Time Complexity: $T(n) = O(n \log n)$.

• $\log n$ levels of recursion.
• $O(n)$ work to merge at each level.
• Stable sort, but uses $O(n)$ extra memory.

Step-by-step Example. Sort [38, 27, 43, 3].

1. Split: [38, 27] and [43, 3].
2. Sort each half recursively:
   • [38, 27] → split → [38] and [27] → merge → [27, 38].
   • [43, 3] → split → [43] and [3] → merge → [3, 43].
3. Merge [27, 38] and [3, 43]:
   • Compare 27 vs 3 → take 3.
   • Compare 27 vs 43 → take 27.
   • Compare 38 vs 43 → take 38.
   • Take remaining 43.
   • Result: [3, 27, 38, 43].

Other D&C Examples.

• Quick Sort: pick pivot, partition, recurse on each side. Average $O(n \log n)$, worst $O(n^2)$.
• Strassen's Matrix Multiplication: $O(n^{2.807})$ vs naive $O(n^3)$.
• Fast Fourier Transform (FFT): $O(n \log n)$.
• Closest Pair of Points: $O(n \log n)$.

Pros and Cons.

When D&C Fails.

If sub-problems overlap (same sub-problem solved many times), D&C is wasteful. Use Dynamic Programming instead.

Example: Naive recursive Fibonacci is $O(2^n)$ because $fib(n-1)$ and $fib(n-2)$ both compute many of the same things. DP reduces this to $O(n)$.

Conclusion. Divide and Conquer is one of the most powerful algorithm design techniques. Famous algorithms like Merge Sort, Quick Sort, FFT, and Binary Search all use it to achieve $O(n \log n)$ or better. Understanding D&C is essential for writing efficient programs.

Definition. A greedy algorithm builds a solution step by step, always making the locally best choice at each step, without going back to revise earlier decisions.

When Greedy Works.

The problem must have:

1. Greedy-choice property — the global optimum can be reached by making local optimal choices.

2. Optimal substructure — the optimal solution of the problem contains optimal solutions of its sub-problems.

If both hold, greedy gives the correct answer. If not, greedy may fail.

Why Use Greedy.

• Fast — usually $O(n \log n)$.
• Simple to implement.
• Less memory than dynamic programming.

Example 1 — Kruskal's Minimum Spanning Tree.

Problem: Given a weighted connected graph, find a spanning tree (connecting all vertices) with minimum total edge weight.

Algorithm:

1. Sort all edges by weight (ascending).
2. Use a Union-Find data structure.
3. For each edge in order:
   • If endpoints are in different components, add edge to MST and merge components.
   • Else skip (it would form a cycle).
4. Stop when (V - 1) edges added.

Time Complexity: $O(E \log E)$.

Worked Example.

Graph with edges: (A,B,4), (A,C,1), (B,C,2), (B,D,5), (C,D,8), (D,E,2).

Sort: (A,C,1), (B,C,2), (D,E,2), (A,B,4), (B,D,5), (C,D,8).

• Add (A,C,1): component {A,C}.
• Add (B,C,2): component {A,B,C}.
• Add (D,E,2): component {D,E}.
• Skip (A,B,4): A and B already connected.
• Add (B,D,5): merges to {A,B,C,D,E}.
• Stop — 4 edges added (V-1 = 4).

MST total weight = 1 + 2 + 2 + 5 = 10.

Example 2 — Activity Selection Problem.

Problem: Given $n$ activities with start and finish times, select the maximum number that don't overlap.

Algorithm:

1. Sort activities by finish time.
2. Pick the first activity.
3. For each remaining activity, pick it if its start time is ≥ finish time of the last picked.

Time Complexity: $O(n \log n)$.

Why It's Optimal.

Choosing the activity that finishes earliest leaves the most room for future activities.

Worked Example.

Activities (start, finish): (1,4), (3,5), (0,6), (5,7), (3,8), (5,9), (6,10), (8,11).

Sort by finish: (1,4), (3,5), (0,6), (5,7), (3,8), (5,9), (6,10), (8,11).

• Pick (1,4). Last finish = 4.
• (3,5): start 3 < 4. Skip.
• (0,6): start 0 < 4. Skip.
• Pick (5,7). Last finish = 7.
• (3,8): start 3 < 7. Skip.
• (5,9): start 5 < 7. Skip.
• (6,10): start 6 < 7. Skip.
• Pick (8,11).

Maximum activities = 3 — (1,4), (5,7), (8,11).

Other Greedy Examples.

• Huffman Coding — build optimal prefix code for compression.
• Dijkstra's Shortest Path — always pick closest unvisited vertex.
• Fractional Knapsack — pick items by highest value/weight ratio.
• Prim's MST — grow tree from one vertex.

When Greedy Fails.

0/1 Knapsack: items cannot be split. Greedy by value/weight ratio gives wrong answer. Use Dynamic Programming instead.

Coin change: for non-standard coin sets like {1, 3, 4}, greedy gives wrong answer for amount 6 (gives 4+1+1 = 3 coins; optimal is 3+3 = 2 coins).

Conclusion. Greedy algorithms are elegant and fast when applicable. The challenge is proving that local choices lead to a global optimum. When in doubt, use Dynamic Programming as a safer fallback.

Definition. Dynamic Programming (DP) solves problems by breaking them into smaller sub-problems and storing the answers so they aren't recomputed.

When DP Applies.

Two key conditions:

1. Optimal Substructure. The optimal answer is built from optimal answers to smaller sub-problems.

2. Overlapping Sub-problems. The same sub-problem is needed multiple times during recursion.

If sub-problems are NOT overlapping → use Divide and Conquer instead.

Two Implementation Styles.

1. Top-Down (Memoization).

• Write natural recursion.
• Cache results in a table.
• Solve only the sub-problems we actually need.

2. Bottom-Up (Tabulation).

• Iteratively fill a table from base cases.
• No recursion overhead.
• More efficient.

Example 1 — Fibonacci.

Definition: $F(n) = F(n-1) + F(n-2)$, with $F(0) = 0, F(1) = 1$.

Naive Recursion: $O(2^n)$.

$F(5)$ recomputes $F(2)$ three times, $F(1)$ five times, etc. — exponential.

DP Bottom-Up: $O(n)$.

• Create array dp[0..n].
• dp[0] = 0, dp[1] = 1.
• For i = 2 to n: dp[i] = dp[i-1] + dp[i-2].
• Return dp[n].

Memory can be reduced to $O(1)$ — only last two values needed.

Comparison.

Example 2 — 0/1 Knapsack.

Problem: Given $n$ items with weights $w_i$ and values $v_i$, and a knapsack capacity $W$, select items (each taken once or not at all) to maximize total value.

State: dp[i][w] = maximum value using first $i$ items with capacity $w$.

Recurrence:

• Base: dp[0][w] = 0.
• If $w < w_i$: dp[i][w] = dp[i-1][w] (can't take item).
• Else: dp[i][w] = max(dp[i-1][w], dp[i-1][w - w_i] + v_i).

Time Complexity: $O(n \times W)$.

Worked Example.

Items: (weight 2, value 3), (weight 3, value 4), (weight 4, value 5), (weight 5, value 6). Capacity W = 5.

Maximum value = 7 (take items 1 and 2: total weight 2+3=5, total value 3+4=7).

Why Greedy Fails Here. We cannot take fractions of items, so greedy by ratio doesn't always give optimal.

Other DP Examples.

• Longest Common Subsequence (LCS) — for diff utilities, DNA alignment.
• Edit Distance — for spell-checkers.
• Matrix Chain Multiplication — for optimal parenthesization.
• Coin Change — minimum coins to make a value.
• Floyd-Warshall — all-pairs shortest paths.

Design Pattern for DP.

1. Define the state — what does dp[i] or dp[i][j] mean?
2. Identify the base case(s).
3. Write the recurrence relating current state to smaller states.
4. Choose direction (top-down or bottom-up).
5. Reconstruct the solution by backtracking if needed.

DP vs Divide and Conquer.

Conclusion. Dynamic Programming transforms exponential problems into polynomial ones by saving repeated work. The key skill is identifying the state and recurrence. Once that's clear, the rest is just filling a table.