Theory_Consolidated

Maths 1: Complete Theory Notes

IIT Madras BS DS - Foundational Level All 12 Weeks Covered

---

Week 1: Sets, Relations & Functions

1.1 Sets

Definition

A set is a well-defined collection of distinct objects. Objects in a set are called elements or members.

Notation:

• $A=\{1,2,3\}$ (Roster form)
• $B=\{x\mid x\in \mathbb{N},x<5\}$ (Set-builder form)

Types of Sets

Type	Definition	Example
Empty Set	No elements	$\varnothing$ or $\{\}$
Singleton	Exactly one element	$\{5\}$
Finite	Countable elements	$\{1,2,3\}$
Infinite	Uncountable elements	$\mathbb{N},\mathbb{R}$
Universal	Contains all elements under consideration	$U$

Set Operations

Union: $A\cup B=\{x\mid x\in A\text{ or }x\in B\}$

Intersection: $A\cap B=\{x\mid x\in A\text{ and }x\in B\}$

Difference: $A\setminus B=\{x\mid x\in A\text{ and }x\notin B\}$

Symmetric Difference: $A\Delta B=(A\setminus B)\cup (B\setminus A)$

Complement: $A^{\prime }=\{x\mid x\in U\text{ and }x\notin A\}$

De Morgan’s Laws

$$(A\cup B{)}^{\prime }=A^{\prime }\cap B^{\prime }$$ $$(A\cap B{)}^{\prime }=A^{\prime }\cup B^{\prime }$$

Cardinality Formulas

$|A\cup B|=|A|+|B|-|A\cap B|$ $|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$

---

1.2 Relations

Definition

A relation $R$ from set $A$ to set $B$ is a subset of $A\times B$ (Cartesian product).

If $(a,b)\in R$, we write $aRb$.

Properties of Relations (on set $A$)

Property	Definition	Example
Reflexive	$(a,a)\in R$ for all $a\in A$	“is equal to”
Symmetric	$(a,b)\in R\Rightarrow (b,a)\in R$	”is sibling of”
Transitive	$(a,b),(b,c)\in R\Rightarrow (a,c)\in R$	”is ancestor of”
Antisymmetric	$(a,b),(b,a)\in R\Rightarrow a=b$	”≤“

Equivalence Relation

A relation is an equivalence relation if it is:

• Reflexive
• Symmetric
• Transitive

Example: “Same age as” is an equivalence relation.

---

1.3 Functions

Definition

A function $f:A\to B$ assigns exactly one element of $B$ to each element of $A$.

• Domain: Set $A$ (inputs)
• Codomain: Set $B$ (possible outputs)
• Range: Actual outputs, $\{f(a)\mid a\in A\}$

Types of Functions

Type	Definition	Test
Injective (1-1)	$f(a_1)=f(a_2)\Rightarrow a_1=a_2$	Horizontal line test
Surjective (Onto)	Range = Codomain	Every element in B has a preimage
Bijective	Both injective and surjective	Invertible

Domain Restrictions

For $f(x)$ to be defined:

1. Denominator ≠ 0
2. Square root argument ≥ 0
3. Log argument > 0

---

Week 2: Coordinate Geometry

2.1 Distance Formula

$d=\sqrt{(x_2-x_1{)}^2+(y_2-y_1{)}^2}$

2.2 Section Formula

Point dividing line segment $(x_1,y_1)$ to $(x_2,y_2)$ in ratio $m:n$: $\left(\frac{m{x}_2+n{x}_1}{m+n},\frac{m{y}_2+n{y}_1}{m+n}\right)$

Midpoint: (when $m=n=1$) $\left(\frac{x_1+x_2}{2},\frac{y_1+y_2}{2}\right)$

2.3 Equations of Lines

Slope-Intercept: $y=mx+c$

Point-Slope: $y-y_1=m(x-x_1)$

Two-Point: $\frac{y-y_1}{y_2-y_1}=\frac{x-x_1}{x_2-x_1}$

Intercept Form: $\frac{x}{a}+\frac{y}{b}=1$

General Form: $ax+by+c=0$

2.4 Slope Relationships

• Parallel lines: $m_1=m_2$
• Perpendicular lines: $m_1\cdot m_2=-1$

2.5 Distance from Point to Line

Distance from $(x_0,y_0)$ to line $ax+by+c=0$: $d=\frac{|a{x}_0+b{y}_0+c|}{\sqrt{a^2+b^2}}$

2.6 Area of Triangle

With vertices $(x_1,y_1),(x_2,y_2),(x_3,y_3)$: $\text{Area}=\frac{1}{2}|x_1(y_2-y_3)+x_2(y_3-y_1)+x_3(y_1-y_2)|$

---

Week 3: Quadratic Functions

3.1 Standard Forms

Standard Form: $f(x)=a{x}^2+bx+c$

Vertex Form: $f(x)=a(x-h{)}^2+k$ where vertex = $(h,k)$

Factored Form: $f(x)=a(x-r_1)(x-r_2)$ where $r_1,r_2$ are roots

3.2 Vertex

$h=-\frac{b}{2a},k=f(h)=c-\frac{b^2}{4a}$

3.3 Roots (Quadratic Formula)

$x=\frac{-b\pm \sqrt{b^2-4ac}}{2a}$

3.4 Discriminant

$D=b^2-4ac$

$D$ Value	Nature of Roots
$D>0$	Two distinct real roots
$D=0$	One repeated real root
$D<0$	Two complex conjugate roots

3.5 Sum and Product of Roots

If roots are $\alpha ,\beta$: $\alpha +\beta =-\frac{b}{a}$ $\alpha \cdot \beta =\frac{c}{a}$

3.6 Derivative (Slope of Parabola)

$f^{\prime }(x)=2ax+b$

At point $(x_0,y_0)$: Slope $=2a{x}_0+b$

---

Week 4: Polynomials

4.1 General Form

$p(x)=a_n{x}^n+a_{n-1}{x}^{n-1}+\cdots +a_{1}x+a_0$

• Degree: Highest power of $x$
• Leading coefficient: $a_n$

4.2 Multiplicity and Graph Behavior

Factor $(x-r{)}^k$	Behavior at $x=r$
$k$ is odd	Graph crosses x-axis
$k$ is even	Graph touches/bounces

4.3 End Behavior

Degree	Leading Coeff	As $x\to \infty$	As $x\to -\infty$
Even	Positive	$\uparrow$	$\uparrow$
Even	Negative	$\downarrow$	$\downarrow$
Odd	Positive	$\uparrow$	$\downarrow$
Odd	Negative	$\downarrow$	$\uparrow$

4.4 Turning Points

A polynomial of degree $n$ has at most $n-1$ turning points.

---

Week 5-6: Exponentials & Logarithms

5.1 Exponential Functions

$f(x)=a^x(a>0,a\ne 1)$

Properties:

• Domain: $\mathbb{R}$
• Range: $(0,\infty )$
• $a^0=1$
• $a^{m+n}=a^m\cdot a^n$
• $a^{-n}=\frac{1}{a^n}$

5.2 Logarithmic Functions

$y={\log }_{a}x⟺a^y=x$

Properties:

• Domain: $(0,\infty )$
• Range: $\mathbb{R}$
• ${\log }_{a}1=0$
• ${\log }_{a}a=1$

5.3 Log Rules

${\log }_a(xy)={\log }_{a}x+{\log }_{a}y$ ${\log }_a\left(\frac{x}{y}\right)={\log }_{a}x-{\log }_{a}y$ ${\log }_a(x^n)=n{\log }_{a}x$ ${\log }_{a}x=\frac{{\log }_{b}x}{{\log }_{b}a}$ (Change of base)

5.4 Special Cases

• $e\approx 2.718$ (Euler’s number)
• $\ln x={\log }_{e}x$ (Natural log)
• $e^{\ln x}=x$
• $\ln (e^x)=x$

---

Week 7-8: Limits & Derivatives

7.1 Limits

${\lim }_{x\to a}f(x)=L$

Key Limits: ${\lim }_{x\to 0}\frac{\sin x}{x}=1$ ${\lim }_{x\to 0}\frac{e^x-1}{x}=1$ ${\lim }_{x\to 0}\frac{\ln (1+x)}{x}=1$

7.2 Continuity

$f$ is continuous at $x=a$ if:

1. $f(a)$ is defined
2. ${\lim }_{x\to a}f(x)$ exists
3. ${\lim }_{x\to a}f(x)=f(a)$

8.1 Derivative Definition

$f^{\prime }(x)={\lim }_{h\to 0}\frac{f(x+h)-f(x)}{h}$

8.2 Basic Derivatives

Function	Derivative
$x^n$	$n{x}^{n-1}$
$e^x$	$e^x$
$\ln x$	$\frac{1}{x}$
$\sin x$	$\cos x$
$\cos x$	$-\sin x$

8.3 Rules

Sum: $(f+g{)}^{\prime }=f^{\prime }+g^{\prime }$

Product: $(fg{)}^{\prime }=f^{\prime }g+f{g}^{\prime }$

Quotient: ${\left(\frac{f}{g}\right)}^{\prime }=\frac{f^{\prime }g-f{g}^{\prime }}{g^2}$

Chain: $(f\circ g{)}^{\prime }(x)=f^{\prime }(g(x))\cdot g^{\prime }(x)$

---

Week 9: Optimization & Integration

9.1 Critical Points

Set $f^{\prime }(x)=0$ and solve. These are candidates for local max/min.

9.2 Second Derivative Test

• $f^{\prime \prime }(x)>0$: Local minimum
• $f^{\prime \prime }(x)<0$: Local maximum
• $f^{\prime \prime }(x)=0$: Inconclusive

9.3 Global Max/Min

On a closed interval $[a,b]$:

1. Find all critical points in $(a,b)$
2. Evaluate $f$ at critical points and endpoints
3. Largest value = Global max, Smallest = Global min

9.4 Integration

$\int x^{n}dx=\frac{x^{n+1}}{n+1}+C(n\ne -1)$

Definite Integral: ${\int }_a^{b}f(x)dx=F(b)-F(a)$

---

Week 10-12: Graph Theory

10.1 Graph Basics

• Vertex (Node): A point
• Edge: Connection between vertices
• Degree: Number of edges at a vertex

10.2 Handshaking Lemma

${\sum }_{v\in V}\mathrm{deg}(v)=2|E|$

10.3 Adjacency Matrix

$A_{ij}=1$ if edge exists between $i$ and $j$, else $0$.

$A_{ij}^k$ = Number of paths of length $k$ from $i$ to $j$.

10.4 Graph Traversals

BFS	DFS
Uses Queue	Uses Stack
Finds shortest path (unweighted)	Good for cycle detection
Level-order	Depth-first

10.5 Shortest Path Algorithms

Dijkstra: No negative edges. $O(V^2)$ or $O(E\log V)$.

Bellman-Ford: Handles negative edges (no negative cycles). $O(VE)$.

10.6 Minimum Spanning Tree

Prim: Start from vertex, add cheapest edge.

Kruskal: Sort edges, add if no cycle.

---

End of Maths 1 Theory. Good luck!