Notes
Books 📚
Mathematics I 🔥

MATHEMATICS FOR DATA SCIENCE 1 - Sets and Functions

Here is a simplified and emoji-enhanced summary of the key study material from the PDF “MATHEMATICS FOR DATA SCIENCE 1: Sets and Functions” along with practice questions and detailed solutions to help you learn effectively. 📚✨

1. Set Theory & Numbers 🔢

Natural Numbers & Integers

  • Natural numbers (N): {0, 1, 2, 3, …} — counting numbers including zero.
  • Integers (Z): {…, -3, -2, -1, 0, 1, 2, 3, …} — whole numbers including negatives.

Arithmetic Operations ➕➖✖️➗

  • Addition (+), Subtraction (-), Multiplication (×), Division (÷), Modulo (mod).
  • Example: 10 mod 3 = 1 (remainder when 10 is divided by 3).

Rational Numbers (Q) & Greatest Common Divisor (gcd)

  • Rational numbers: numbers expressed as p/q, where p,q ∈ integers.
  • gcd is the largest positive integer dividing two numbers.
  • Example: gcd(9,12) = 3.

Real & Irrational Numbers

  • Real numbers include rationals and irrationals (cannot be expressed as p/q).
  • Examples of irrationals: √2, π.

Sets & Subsets

  • A set is a collection of distinct elements.
  • Subset (X ⊆ Y): every element of X is in Y.
  • Proper subset (X ⊂ Y): X is a subset but not equal to Y.

Relations & Functions

  • Relation: subset of Cartesian product X × Y.
  • Function: each element in X maps to exactly one element in Y.
  • Types of functions:
    • Injective (one-to-one)
    • Surjective (onto)
    • Bijective (both)

1. Set Theory & Numbers 🧠

Q1. Which of the following sets is a subset of Z (integers)?

A) {2, 4, 6}

B) {1/2, 3/2, 5/2}

C) {π, √2, 2}

D) {–3, 0, 7}

Solution: A subset must have all its elements in the parent set. Z is the set of all integers.

  • A: All elements are integers. ✅
  • B: Contains fractions, not all integers. ❌
  • C: Contains irrationals, not all integers. ❌
  • D: All elements are integers. ✅

Answer: Both A and D are subsets of Z.

Q2. Find the gcd of 18 and 24. 🤝

Solution:

  • Factors of 18: 1, 2, 3, 6, 9, 18
  • Factors of 24: 1, 2, 3, 4, 6, 8, 12, 24
  • Common factors: 1, 2, 3, 6
  • Greatest: 6

Answer: gcd(18, 24) = 6

Q3. 🌟 Which of the following is a rational number?

A) √2 B) 3/7 C) π D) 0.333…

Solution:

  • B and D are rational (0.333… = 1/3).
  • √2 and π are irrational.

Answer: B and D.

Q4. 🧮 Find gcd(18, 24).

Solution: 18: 1, 2, 3, 6, 9, 18 24: 1, 2, 3, 4, 6, 8, 12, 24 Common: 1, 2, 3, 6 gcd = 6

Q5. 🗂️ List all subsets of {a, b}.

Solution: {}, {a}, {b}, {a, b}

Q6. 🔗 Is the relation R = {(1,1), (2,2), (3,3), (1,2), (2,1)} on S = {1,2,3} symmetric?

Solution: (1,2) ∈ R ⇒ (2,1) ∈ R. All such pairs exist. Yes, R is symmetric.

Key Concepts

  • Natural Numbers (N): {0, 1, 2, 3, …} 🧒
  • Integers (Z): {…, -3, -2, -1, 0, 1, 2, …} 🔢
  • Arithmetic Operations: +, –, ×, ÷, mod ➕➖✖️➗
  • Factors: a is a factor of b if b mod a = 0
  • Rational Numbers (Q): Numbers of the form p/q, p, q ∈ Z, q ≠ 0 🧮
  • Greatest Common Divisor (gcd): Largest integer dividing two numbers
  • Irrational Numbers: Cannot be written as p/q (e.g., √2, π) 🌀
  • Real Numbers (R): All rationals + irrationals 🌐
  • Sets: Collection of well-defined items (e.g., {1, 2, 3}) 🗂️
  • Subsets: X ⊆ Y if every element of X is in Y
  • Set Comprehension: Building subsets using rules
  • Relations: Subsets of Cartesian products (ordered pairs) 🔗
  • Properties of Relations: Reflexive, symmetric, transitive, equivalence
  • Functions: Special relations where each input has one output
    • Injective (one-to-one), Surjective (onto), Bijective (both)

2. Straight Lines 📏

Cartesian Coordinates & Distance

  • Distance between points (x1,y1) and (x2,y2):
$$ \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2} $$
  • Section formula for dividing a segment in ratio m:n:
$$ x = \frac{mx_2 + nx_1}{m+n}, \quad y = \frac{my_2 + ny_1}{m+n} $$

Slope of a Line

  • Slope $m = \frac{y_2 - y_1}{x_2 - x_1}$.
  • Parallel lines: equal slopes.
  • Perpendicular lines: product of slopes = -1.

Equation Forms

  • Slope-intercept: $y = mx + c$.
  • Point-slope: $y - y_1 = m(x - x_1)$.
  • Two-point form: $y - y_1 = \frac{y_2 - y_1}{x_2 - x_1}(x - x_1)$.

Distance from Point to Line

$$ d = \frac{|ax_1 + by_1 + c|}{\sqrt{a^2 + b^2}} $$

2. Straight Lines 🧠

Q1. What is the distance between the points (3, 4) and (7, 1)? 📐

Solution: Use the distance formula:

$$ d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2} $$$$ d = \sqrt{(7-3)^2 + (1-4)^2} = \sqrt{4^2 + (-3)^2} = \sqrt{16 + 9} = \sqrt{25} = 5 $$

Answer: 5 units

Q2. Find the equation of the line passing through (1, 2) with slope 3. 📝

Solution: Point-slope form: $ y - y_1 = m(x - x_1) $

$$ y - 2 = 3(x - 1) \implies y = 3x - 1 $$

Answer: $ y = 3x - 1 $

Q3. 📏 Find the distance between (2,4) and (–4,12).

Solution: $ d = \sqrt{(-4-2)^2 + (12-4)^2} = \sqrt{36 + 64} = \sqrt{100} = 10 $

Q4. 🔺 Find the area of triangle with points (0,10), (–20,–30), (10,30).

Solution: $ \Delta = \frac{1}{2}|0((-30)-30) + (-20)(30-10) + 10(10-(-30))| $ $ = \frac{1}{2}|0 + (-20)(20) + 10(40)| = \frac{1}{2}|-400 + 400| = 0 $ Points are collinear.

Q5. 📝 Find the equation of the line through (1,2) with slope 3.

Solution: $ y - 2 = 3(x - 1) \implies y = 3x - 1 $

Q6. 📊 Calculate SSE for points (1,5), (2,6), (4,9), (9,18) with line y = 2x + 2.

Solution: SSE = (5–4)² + (6–6)² + (9–10)² + (18–20)² = 1 + 0 + 1 + 4 = 6

Key Concepts

  • Cartesian Coordinates: Points as (x, y) 📍
  • Distance Formula: $ d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2} $ 📏
  • Section Formula: Dividing a line segment in ratio m:n
  • Area of Triangle: $ \Delta = \frac{1}{2} |x_1(y_2-y_3) + x_2(y_3-y_1) + x_3(y_1-y_2)| $ 🔺
  • Slope (m): $ m = \frac{y_2 - y_1}{x_2 - x_1} $
  • Equation Forms:
    • Slope-intercept: $ y = mx + c $
    • Point-slope: $ y - y_1 = m(x - x_1) $
    • Two-point: $ y - y_1 = \frac{y_2 - y_1}{x_2 - x_1}(x - x_1) $
  • Parallel/Perpendicular:
    • Parallel: Equal slopes
    • Perpendicular: Product of slopes = –1
  • Distance from Point to Line: $ d = \frac{|ax_1 + by_1 + c|}{\sqrt{a^2 + b^2}} $
  • Sum Squared Error (SSE): $ SSE = \sum (y_i - (mx_i + c))^2 $

3. Quadratic Functions & Equations 📐

  • Quadratic function: $f(x) = ax^2 + bx + c$, $a \neq 0$.
  • Vertex: $\left(-\frac{b}{2a}, f\left(-\frac{b}{2a}\right)\right)$.
  • Axis of symmetry: $x = -\frac{b}{2a}$.
  • Parabolas open up if $a > 0$, down if $a < 0$.

Solving Quadratic Equations

  • By factoring
  • By completing the square
  • By quadratic formula:
$$ x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a} $$

Practice Questions 🧠

Q1. 🧮 Solve $ x^2 + 2x = 24 $ by factoring.

Solution: $ x^2 + 2x - 24 = 0 $ $ (x + 6)(x - 4) = 0 $ $ x = -6, 4 $

Q2. 📍 Find the vertex of $ f(x) = 2x^2 - 8x + 3 $.

Solution: $ x_v = -\frac{-8}{2 \times 2} = 2 $ $ y_v = 2(2)^2 - 8(2) + 3 = 8 - 16 + 3 = -5 $ Vertex: (2, –5)

Q3. 🧩 Solve $ x^2 + 2x - 24 = 0 $ using quadratic formula.

Solution: $ a = 1, b = 2, c = -24 $ $ x = \frac{-2 \pm \sqrt{4 + 96}}{2} = \frac{-2 \pm 10}{2} $ $ x = 4, -6 $

Q5. Solve the quadratic equation $ x^2 - 5x + 6 = 0 $ by factoring. 🧮

Solution: Factor: $ (x - 2)(x - 3) = 0 $ So, $ x = 2 $ or $ x = 3 $

Answer: $ x = 2, 3 $

Q6. Find the vertex of $ f(x) = 2x^2 - 8x + 3 $. 📍

Solution: Vertex $ x $-coordinate: $ x = -\frac{b}{2a} = -\frac{-8}{2 \times 2} = 2 $ $ y $-coordinate: $ f(2) = 2(2)^2 - 8(2) + 3 = 8 - 16 + 3 = -5 $ Vertex: (2, –5)

Answer: (2, –5)

Key Concepts

  • Quadratic Function: $ f(x) = ax^2 + bx + c $, $ a \neq 0 $ 📈
  • Parabola: Graph of quadratic function
  • Axis of Symmetry: $ x = -\frac{b}{2a} $
  • Vertex: $ \left(-\frac{b}{2a}, f(-\frac{b}{2a})\right) $ 📍
  • Roots/Solutions: Where $ f(x) = 0 $
  • Solving Methods: Factoring, completing the square, quadratic formula: $ x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a} $

4. Polynomial Functions ✍️

  • Polynomial: sum of terms $a_n x^n + \cdots + a_0$.
  • Degree: highest exponent.
  • Types: monomial, binomial, trinomial.
  • Operations: addition, subtraction, multiplication, division (long division).

Practice Questions 🧠

Q1. ➕ Add $ p(x) = x^3 + 3x^2 + 5x - 10 $, $ q(x) = 3x^3 + 5x^2 - 6x - 20 $.

Solution: $ (1+3)x^3 + (3+5)x^2 + (5-6)x + (-10-20) = 4x^3 + 8x^2 - x - 30 $

Q2. ➗ Divide $ x^3 - 2x^2 + 4x - 8 $ by $ x - 2 $.

Solution: $ x - 2 $ is a factor (since substituting x = 2 gives 0). Quotient: $ x^2 + 0x + 4 $, remainder 0.

Q3. 🔎 Find the zeroes of $ f(x) = x^2 - 4 $.

Solution: $ x^2 - 4 = 0 \implies x = 2, -2 $

Q7. Add the polynomials $ p(x) = 2x^2 + 3x - 1 $ and $ q(x) = x^2 - x + 4 $. ➕

Solution:

$$ p(x) + q(x) = (2x^2 + x^2) + (3x - x) + (-1 + 4) = 3x^2 + 2x + 3 $$

Answer: $ 3x^2 + 2x + 3 $

Q8. Divide $ x^3 - 2x^2 + 4x - 8 $ by $ x - 2 $. ➗

Solution: Use synthetic division or the remainder theorem:

  • Substitute $ x = 2 $: $ (2)^3 - 2(2)^2 + 4(2) - 8 = 8 - 8 + 8 - 8 = 0 $ So, $ x - 2 $ is a factor. Divide:
$$ x^3 - 2x^2 + 4x - 8 = (x - 2)(x^2 + 4) $$

Answer: Quotient is $ x^2 + 4 $, remainder is 0.

Key Concepts

  • Polynomial: Expression with terms $ a_nx^n + … + a_0 $ ✍️
  • Degree: Highest exponent
  • Types: Monomial (1 term), binomial (2), trinomial (3)
  • Operations: Addition, subtraction, multiplication, division
  • Zeroes: Values where $ f(x) = 0 $

5. Exponential Functions & Composition 🔥

  • Exponential function: $f(x) = a^x$, $a > 0, a \neq 1$.
  • Vertical Line Test: checks if a relation is a function.
  • Horizontal Line Test: checks if a function is one-to-one.
  • Composition: $(f \circ g)(x) = f(g(x))$.

Q1. ⚡ Solve $ 2^x = 16 $.

Solution: $ 16 = 2^4 \implies x = 4 $

Q2. 🔄 Find the inverse of $ f(x) = 4x $.

Solution: Let $ y = 4x \implies x = y/4 $ Inverse: $ f^{-1}(x) = x/4 $

Q9. Solve for $ x $: $ 2^x = 16 $. ⚡

Solution: $ 16 = 2^4 $, so $ 2^x = 2^4 \Rightarrow x = 4 $

Answer: $ x = 4 $

Q10. Solve for $ x $: $ \log_3(x) = 2 $. 🔑

Solution:

$$ x = 3^2 = 9 $$

Answer: $ x = 9 $

Q11. Simplify $ \log_2(8) + \log_2(4) $. 🧩

Solution: $ \log_2(8) = 3 $, $ \log_2(4) = 2 $ Sum: $ 3 + 2 = 5 $

Answer: 5

Q12. Solve $ \log_5(x - 1) + \log_5(x + 1) = 1 $. 🔍

Solution: Use the product rule: $ \log_5((x - 1)(x + 1)) = 1 \implies \log_5(x^2 - 1) = 1 \implies x^2 - 1 = 5^1 = 5 \implies x^2 = 6 \implies x = \pm \sqrt{6} $ But for log to be defined, $ x > 1 $. So, $ x = \sqrt{6} $ (approx 2.45)

Answer: $ x = \sqrt{6} $

Key Concepts

  • Exponential Function: $ f(x) = a^x $, $ a > 0, a \neq 1 $ 📈
  • Laws of Exponents:
    • $ a^m \times a^n = a^{m+n} $
    • $ (a^m)^n = a^{mn} $
  • Graph: Always positive, increasing if $ a > 1 $, decreasing if $ 0 < a < 1 $
  • Composition: $ (f \circ g)(x) = f(g(x)) $
  • Inverse Function: Exists if function is one-to-one

6. Logarithmic Functions 🔑

  • Logarithm is inverse of exponential: $y = \log_a x \iff x = a^y$.
  • Domain: $x > 0$, Range: all real numbers.
  • Properties:
    • $\log_a (MN) = \log_a M + \log_a N$
    • $\log_a \frac{M}{N} = \log_a M - \log_a N$
    • $\log_a M^r = r \log_a M$

Practice Questions 🧠

Q1. 🔑 Solve $ \log_3 x = 2 $.

Solution: $ x = 3^2 = 9 $

Q2. 🧩 Simplify $ \log_2 8 + \log_2 4 $.

Solution: $ \log_2 8 = 3 $, $ \log_2 4 = 2 $, so $ 3 + 2 = 5 $

Q3. 🔍 Solve $ \log_8(x+1) + \log_8(x-1) = 1 $.

Solution: $ \log_8((x+1)(x-1)) = 1 \implies \log_8(x^2-1) = 1 \implies x^2-1 = 8 \implies x^2 = 9 \implies x = 3 $ (since log not defined for negative arguments).

Q4. 🚀 Solve $ \log_2(x^2 - 4) = 3 $.

Solution: $ x^2 - 4 = 2^3 = 8 \implies x^2 = 12 \implies x = \pm 2\sqrt{3} $ Domain: $ x^2 - 4 > 0 \implies x > 2 $ or $ x < -2 $ So, $ x = 2\sqrt{3}, -2\sqrt{3} $

Q13. If $ f(x) = 2x + 3 $ and $ g(x) = x^2 $, find $ (f \circ g)(1) $. 🔗

Solution: $ (f \circ g)(1) = f(g(1)) = f(1^2) = f(1) = 2(1) + 3 = 5 $

Answer: 5

Q14. If $ f(x) = x + 1 $, find its inverse. 🔁

Solution: Let $ y = x + 1 \implies x = y - 1 $. So, $ f^{-1}(x) = x - 1 $

Answer: $ f^{-1}(x) = x - 1 $

7. Challenge Problem 🌟

Q15. Solve: $ \log_2(x^2 - 4) = 3 $. 🚀

Solution: $ x^2 - 4 = 2^3 = 8 \implies x^2 = 12 \implies x = \pm 2\sqrt{3} $ But $ x^2 - 4 > 0 \implies x > 2 $ or $ x < -2 $. So, both $ x = 2\sqrt{3} $ and $ x = -2\sqrt{3} $ are valid.

Answer: $ x = 2\sqrt{3} $ or $ x = -2\sqrt{3} $

Key Concepts

  • Logarithm: Inverse of exponential, $ y = \log_a x \iff x = a^y $ 🔑
  • Domain: $ x > 0 $, Range: all real numbers
  • Laws:
    • $ \log_a(MN) = \log_a M + \log_a N $
    • $ \log_a(M/N) = \log_a M - \log_a N $
    • $ \log_a(M^r) = r \log_a M $
  • Natural Logarithm: $ \ln x = \log_e x $
  • Common Logarithm: $ \log_{10} x $

Practice Questions with Solutions 📝✨

Q1: Find the distance between points (2,4) and (-4,12). 📐

Solution:

$$ \sqrt{(-4 - 2)^2 + (12 - 4)^2} = \sqrt{(-6)^2 + 8^2} = \sqrt{36 + 64} = \sqrt{100} = 10 $$

Q2: Solve quadratic equation $x^2 + 2x = 24$ by factoring. 🧮

Solution:

$$ x^2 + 2x - 24 = 0 $$

Factor:

$$ (x + 6)(x - 4) = 0 $$

Roots:

$$ x = -6, \quad x = 4 $$

Q3: Add polynomials $p(x) = x^3 + 3x^2 + 5x - 10$ and $q(x) = 3x^3 + 5x^2 - 6x - 20$. ➕

Solution:

$$ p(x) + q(x) = (1+3)x^3 + (3+5)x^2 + (5 - 6)x + (-10 - 20) = 4x^3 + 8x^2 - x - 30 $$

Q4: Find the inverse of $f(x) = 4x$ and verify if $g(x) = \frac{x}{4}$ is the inverse. 🔄

Solution: Check compositions:

$$ (g \circ f)(x) = g(4x) = \frac{4x}{4} = x $$$$ (f \circ g)(x) = f\left(\frac{x}{4}\right) = 4 \times \frac{x}{4} = x $$

Hence, $g$ is inverse of $f$.

Q5: Solve $\log_8 (x+1) + \log_8 (x-1) = 1$. 🔍

Solution:

$$ \log_8 ((x+1)(x-1)) = 1 \implies \log_8 (x^2 - 1) = 1 $$$$ x^2 - 1 = 8^1 = 8 \implies x^2 = 9 \implies x = \pm 3 $$

Check domain: $x > 1$, so $x = 3$ only.

Q6: If $f(x) = 3x - 4$ and $g(x) = x^2$, find $(f \circ g)(x)$. 🎯

Solution:

$$ (f \circ g)(x) = f(g(x)) = f(x^2) = 3x^2 - 4 $$

Q7: Calculate sum squared error (SSE) for points (1,5), (2,6), (4,9), (9,18) with line $y=2x+2$. 📊

Solution:

$$ SSE = \sum (y_i - (2x_i + 2))^2 = (5-4)^2 + (6-6)^2 + (9-10)^2 + (18-20)^2 = 1 + 0 + 1 + 4 = 6 $$

This summary covers essential concepts with emojis for easy understanding and practice questions with detailed solutions to reinforce learning. For more exercises and deeper understanding, refer to the full PDF. 📘✨

If you want, I can prepare more practice questions or detailed explanations on any specific topic! 😊

⁂
M1_VOL3_GRAPHTHEORY 📈

Related Chapters 📂

  • Essential English Grammar Course

    01 Essential English Grammar Course

    Essential English Grammar Course - Improved Layout & Examples This rewritten course is based on the structure and progression of “Essential Grammar in Use” (4th Edition by Raymond Murphy), but is reorganized for clarity, with enhanced explanations and more practical, modern examples. Each unit includes a concise explanation, clear tables, and sample sentences for real-life situations. Course Structure Part 1: Foundations Unit 1: The Verb “To Be” (am, is, are) Unit 2: Present Simple & Present Continuous Unit 3: Questions & Negatives Unit 4: Nouns, Pronouns, & Possessives Part 2: Tenses Unit 5: Past Simple & Past Continuous Unit 6: Present Perfect & Past Perfect Unit 7: Future Forms (will, going to, present continuous) Part 3: Expanding Sentences Unit 8: Modals (can, could, must, should, might) Unit 9: Articles (a/an, the) Unit 10: Countable & Uncountable Nouns Unit 11: Adjectives & Adverbs Part 4: Sentence Building Unit 12: Word Order & Questions Unit 13: Conjunctions & Clauses Unit 14: Prepositions Part 5: Practical Grammar Unit 15: Passive Voice Unit 16: Reported Speech Unit 17: Gerunds & Infinitives Unit 18: Phrasal Verbs Appendices Irregular Verbs List Spelling Rules Contractions Additional Practice Exercises Part 1: Foundations Unit 1: The Verb “To Be” (am, is, are) Explanation: “To be” is used to describe people, places, things, and feelings.

  • IIT Madras BS Descriptive Statistics

    02 IIT Madras BS Descriptive Statistics

    Certainly! Below is a detailed explanation of the key topics in the IIT Madras BS Descriptive Statistics PDF, presented with examples, questions, and step-by-step solutions in a clear and structured layout[1]. 1. Introduction to Statistics Statistics is the science of collecting, organizing, analyzing, interpreting, and presenting data. Key Concepts Population: All elements of interest (e.g., all houses in Tamil Nadu). Sample: A subset of the population (e.g., 1000 houses from Tamil Nadu). Descriptive Statistics: Summarizing and describing data. Inferential Statistics: Drawing conclusions about a population from sample data. Example: A teacher wants to know the average marks of all students in a school. She collects a sample of students and calculates their average. If she uses this to estimate the school average, she is using inferential statistics.

  • IIT Madras BS Probability and Probability Distributions

    03 IIT Madras BS Probability and Probability Distributions

    explain this pdf course with exmaples , questions and their detailed solutions , with ease to understands and with better layout with all steps mentionedCertainly! Below is a clear, step-by-step explanation of the IIT Madras BS Probability and Probability Distributions PDF course, with examples, questions, and detailed solutions for each major topic1. The layout is designed for ease of understanding and covers all essential steps. 1. Data, Statistics, and Probability Key Concepts

  • M1 VOL1 SETS & FUNCTIONS.pdf

    04 M1 VOL1 SETS & FUNCTIONS.pdf

    explain all concepts from this pdf with detailed structure , examples, related questions & answers with ease to understandHere’s a detailed, structured explanation of all the key concepts from the provided PDF, “Mathematics for Data Science-1: Sets and Functions,” along with examples, related questions, and answers, designed for easy understanding1. 1. Set Theory Definition: A set is a collection of well-defined, distinct objects called elements. Order and duplicates do not matter.

  • M1_VOL2_CALCULUS.pdf

    05 M1_VOL2_CALCULUS.pdf

    explain all concepts from this pdf with detailed structure , examples, related questions & answers with ease to understandBelow is a structured, detailed, and easy-to-understand explanation of all major concepts from the PDF “M1_VOL2_CALCULUS.pdf,” including definitions, examples, related questions, and answers1. 1. Limits and Continuity 1.1 Introduction Concept: Calculus builds on real numbers, sets, functions, and operations. It introduces limits and continuity to understand behavior at points and infinity. Example: In school, you learned about real numbers and functions like $ f(x) = x^2 $. 1.2 What is a Function? Definition: A function $ f: A \to B $ assigns exactly one output in $ B $ for every input in $ A $. Domain: Input set $ A $. Codomain: Output set $ B $. Range: Actual output values $ {f(a) \mid a \in A} $. Example: $ f(x) = x^2 $ is a function from $ \mathbb{R} $ to $ \mathbb{R} $. Counterexample: $ R = {(1,a), (2,b), (3,a), (1,b)} $ is not a function because 1 maps to both $ a $ and $ b $. Graph of Functions Definition: Graph of $ f $ is $ {(x, f(x)) \mid x \in domain} $. Example: For $ f(x) = 7x+2 $, graph is all points $ (x, 7x+2) $. Types of Functions Linear: $ f(x) = ax + b $ Quadratic: $ f(x) = ax^2 + bx + c $ Polynomial: $ f(x) = a_nx^n + ··· + a_0 $ Exponential: $ f(x) = a^x $ Logarithmic: $ f(x) = \log_a x $ Trigonometric: $ \sin x, \cos x, \tan x $ Step functions: Floor $ \lfloor x \rfloor $, Ceiling $ \lceil x \rceil $, Absolute $ |x| $ Examples: Floor in $[-1,2]$: $ \lfloor x \rfloor = -1 $ for $-1 \leq x < 0$, $0$ for $0 \leq x < 1$, $1$ for $1 \leq x < 2$. Absolute: $ |x| = x $ if $ x \geq 0 $, $-x$ if $ x < 0 $. Bounded Function Definition: $ f $ is bounded if $ m \leq f(x) \leq M $ for all $ x $. Example: $ f(x) = \frac{1}{x^2+1} $ is bounded ($0 \leq f(x) \leq 1$). Counterexample: $ f(x) = \frac{1}{x} $ on $ (0, \infty) $ is unbounded. Monotonicity Increasing: If $ x \leq y \implies f(x) \leq f(y) $. Decreasing: If $ x \leq y \implies f(x) \geq f(y) $. Example: $ f(x) = x^2 $ is increasing on $[0, \infty)$. Example: $ f(x) = 7-4x $ is decreasing on $ \mathbb{R} $. Example: $ f(x) = |x| $ is neither increasing nor decreasing on $ \mathbb{R} $. Arithmetic Operations on Functions Sum: $ (f+g)(x) = f(x) + g(x) $ Difference: $ (f-g)(x) = f(x) - g(x) $ Product: $ (fg)(x) = f(x)g(x) $ Quotient: $ (f/g)(x) = f(x)/g(x) $ (if $ g(x) \neq 0 $) Example: If $ f(x) = x^3 + 5x + 1 $, $ g(x) = 3x^2 + 2x + 5 $, then $ (f-g)(x) = x^3 - 3x^2 + 3x - 4 $. Composition of Functions Definition: $ (g \circ f)(x) = g(f(x)) $. Example: If $ f(x) = x^2 $, $ g(x) = 3x^3 + 2x $, then $ (g \circ f)(x) = 3x^6 + 2x^2 $. Question: If $ f(x) = \frac{x}{x+a} $, $ f(f(x)) = \frac{x}{3x+4} $, find $ a $. Answer: $ a = 2 $. 1.3 Curve and Tangent Curve: Path of a moving point. Tangent: Line touching curve at a point, representing instantaneous direction. Example: Graph of $ f(x) = x^2 $ is a curve. At point $ (a, a^2) $, tangent is unique. Example: Floor function $ f(x) = \lfloor x \rfloor $ is not a curve (has jumps). Question: Is tangent possible for $ f(x) = \lfloor x \rfloor $ at $ x=2 $ and $ x=3.5 $? Answer: No tangent at $ x=2 $ (jump), tangent is $ y=3 $ at $ x=3.5 $. 1.4 Sequence and Limit of Sequence Sequence: Function $ f: \mathbb{N} \to \mathbb{R} $, denoted $ {a_n} $. Limit of Sequence: $ \lim_{n \to \infty} a_n = L $ if $ a_n $ gets arbitrarily close to $ L $ as $ n $ increases. Example: $ a_n = 1 - \frac{1}{n^2} $ converges to 1. Example: $ a_n = n $ diverges. Example: $ a_n = (-1)^n $ diverges (oscillates). Example: $ a_n = \frac{n+1}{n} $ converges to 1. Subsequence Definition: A sequence formed by selecting terms from another sequence in order. Example: For $ a_n = 5n^2 + 1 $, subsequence $ b_n = a_{2n} = 5(2n)^2 + 1 $. Tools for Limits Sum/Difference: $ \lim (a_n \pm b_n) = \lim a_n \pm \lim b_n $ Product: $ \lim (a_n b_n) = \lim a_n \cdot \lim b_n $ Quotient: $ \lim (a_n / b_n) = \lim a_n / \lim b_n $ (if $ \lim b_n \neq 0 $) Sandwich Principle: If $ a_n \leq c_n \leq b_n $ and $ \lim a_n = \lim b_n = L $, then $ \lim c_n = L $. Example: $ c_n = \frac{\sin n}{n} \rightarrow 0 $ (since $ -\frac{1}{n} \leq \frac{\sin n}{n} \leq \frac{1}{n} $). Important Theorems If $ \lim a_n = L $, then $ \lim \frac{a_1 + ··· + a_n}{n} = L $. If $ \lim \frac{a_{n+1}}{a_n} = \ell $, then: If $ |\ell| < 1 $, $ \lim a_n = 0 $. If $ \ell > 1 $, $ \lim a_n = \infty $. Exercises Q5: $ a_n = \frac{5+3\sqrt{n}}{\sqrt{n}} \rightarrow 3 $ Q6: $ a_n = 5^{1/n} \rightarrow 1 $ Q7: $ a_n = \left(\frac{1}{2}\right)^n \rightarrow 0 $ Q8: $ a_n = \frac{(-1)^n}{2n} \rightarrow 0 $ Q9: If $ b_n \rightarrow 1 $, $ c_n \rightarrow \infty $, then $ \frac{b_n}{c_n} \rightarrow 0 $ 1.5 Limit of Function Definition: $ \lim_{x \to a} f(x) = L $ if $ f(x) $ gets close to $ L $ as $ x $ approaches $ a $. Left/Right Limits: $ \lim_{x \to a^-} f(x) $, $ \lim_{x \to a^+} f(x) $ Example: $ \lim_{x \to 1} x^2 = 1 $ Example: $ \lim_{x \to -1} \lfloor x \rfloor $ does not exist (left limit is -2, right limit is -1). Example: $ f(x) = 1 $ if $ x $ is rational, $ 0 $ otherwise. $ \lim_{x \to \sqrt{2}} f(x) $ does not exist. Limit at Infinity Definition: $ \lim_{x \to \infty} f(x) = L $ if $ f(x) $ approaches $ L $ as $ x $ becomes very large. Example: $ \lim_{x \to \infty} \frac{1}{x} = 0 $ Algebra of Limits Sum/Difference: $ \lim (f \pm g) = \lim f \pm \lim g $ Product: $ \lim (f \cdot g) = \lim f \cdot \lim g $ Quotient: $ \lim (f/g) = \lim f / \lim g $ (if $ \lim g \neq 0 $) Example: $ \lim_{x \to 2} (5x+9) = 19 $ Example: $ \lim_{x \to -3} x^4 = 81 $ Example: $ \lim_{x \to 5} \frac{25}{x^2} = 1 $ Sandwich Theorem If $ f(x) \leq h(x) \leq g(x) $ and $ \lim_{x \to a} f(x) = \lim_{x \to a} g(x) = L $, then $ \lim_{x \to a} h(x) = L $. Example: $ \lim_{x \to 0} x^2 \sin(1/x) = 0 $ Example: $ \lim_{x \to 0} \frac{\sin x}{x} = 1 $ Example: $ \lim_{x \to 0} \frac{\tan x}{x} = 1 $ Example: $ \lim_{x \to 0} \frac{1-\cos x}{x^2} = \frac{1}{2} $ 1.6 Continuity Definition: $ f $ is continuous at $ a $ if $ \lim_{x \to a} f(x) = f(a) $. Example: $ f(x) = |x| $ is continuous at $ x=0 $. Example: $ f(x) = \lfloor x \rfloor $ is not continuous at integers. Piecewise Example: $ f(x) = $$ \begin{cases} x+1 & -4 \leq x < 2 \\ x^2-4 & 2 \leq x \leq 3 \end{cases} $$ $ is not continuous at $ x=2 $. Theorems on Continuity Sum/Difference/Product/Quotient: If $ f $ and $ g $ are continuous at $ a $, so are $ f \pm g $, $ f \cdot g $, $ f/g $ (if $ g(a) \neq 0 $). Composition: If $ g $ is continuous at $ a $ and $ f $ is continuous at $ g(a) $, then $ f \circ g $ is continuous at $ a $. Exercises Q11: $ f(x) = $$ \begin{cases} 1 & x \geq 0 \\ -1 & x < 0 \end{cases} $$ $ Right limit at 0: $ \lim_{x \to 0^+} f(x) = 1 $ Left limit at 0: $ \lim_{x \to 0^-} f(x) = -1 $ Limit at 0 does not exist. Q12: $ \lim_{x \to \infty} \frac{1}{x} = 0 $ (Option 1) $ \lim_{x \to \infty} \frac{x^2}{1+x} = \infty $ $ \lim_{x \to -\infty} \frac{1+x}{x^2} = 0 $ (Option 3) $ \lim_{x \to \infty} \frac{1+x+x^2}{5x^2+1} = \frac{1}{5} $ (Option 4) Q14: $ \lim_{x \to -1} \frac{x^2-6x-7}{x^2+3x+2} = \lim_{x \to -1} \frac{(x+1)(x-7)}{(x+1)(x+2)} = \lim_{x \to -1} \frac{x-7}{x+2} = -8 $ (Option 1) $ \lim_{x \to 0} \frac{x^2-6x-7}{x^2+3x+2} = \frac{-7}{2} $ $ \lim_{x \to 3} \frac{x^2-6x+9}{x-3} = \lim_{x \to 3} (x-3) = 0 $ 2. Differentiation 2.1 Differentiability and the Derivative Definition: $ f $ is differentiable at $ a $ if $ \lim_{h \to 0} \frac{f(a+h)-f(a)}{h} $ exists. Example: $ f(x) = x $ is differentiable everywhere, derivative is 1. Example: $ f(x) = \sin x $ is differentiable at 0, derivative is 1. Example: $ f(x) = |x| $ is not differentiable at 0 (left and right derivatives differ). Example: $ f(x) = x^{1/3} $ is not differentiable at 0 (derivative tends to infinity). Example: $ f(x) = \lfloor x \rfloor $ is not differentiable at integers. Relation to Continuity Theorem: If $ f $ is differentiable at $ a $, then $ f $ is continuous at $ a $. Example: $ f(x) = \lfloor x \rfloor $ is not continuous at integers, so not differentiable. Derivative Rules Sum/Difference: $ (f \pm g)’ = f’ \pm g’ $ Product: $ (fg)’ = f’g + fg’ $ Quotient: $ (f/g)’ = \frac{f’g - fg’}{g^2} $ Chain Rule: $ (f(g(x)))’ = f’(g(x))g’(x) $ Example: $ f(x) = x^2 $, $ f’(x) = 2x $ Example: $ f(x) = \sin x $, $ f’(x) = \cos x $ Example: $ f(x) = e^x $, $ f’(x) = e^x $ Example: $ f(x) = \ln x $, $ f’(x) = 1/x $ Exercises Q27: $ f(x) = 5x $, derivative at $ x=2 $ is 5. Q28: $ f(x) = a $ (constant), derivative is 0. $ f(x) = x - c $, derivative is 1. $ f(x) = x^2 $, derivative at $ c $ is $ 2c $. $ f(x) = e^x $, derivative at $ c $ is $ e^c $. Q29: Check graphs for continuity and differentiability. Q30: If $ \lim_{h \to 0} \frac{f(a+h)-f(a)}{h} $ exists, $ f $ is differentiable at $ a $. If $ f $ is differentiable at $ a $, it is continuous at $ a $. There exist continuous functions not differentiable at some points (e.g., $ |x| $ at 0). 2.2 Indeterminate Limits and L’Hôpital’s Rule Indeterminate Form: $ \frac{0}{0} $ or $ \frac{\infty}{\infty} $. L’Hôpital’s Rule: If $ \lim_{x \to a} \frac{f(x)}{g(x)} $ is indeterminate, and $ f’ $, $ g’ $ exist near $ a $, then $ \lim_{x \to a} \frac{f(x)}{g(x)} = \lim_{x \to a} \frac{f’(x)}{g’(x)} $. Example: $ \lim_{x \to 0} \frac{\log(1+x)}{x} = 1 $ Example: $ \lim_{x \to 0} \frac{\sin x}{x} = 1 $ Example: $ \lim_{x \to \infty} \frac{a+be^x}{c+de^x} = \frac{b}{d} $ Example: $ \lim_{x \to 0} \frac{1-\cos x}{x^2} = \frac{1}{2} $ Exercises Q40: $ f(x) = \sqrt{9-x^2} $, $ \lim_{x \to 1} \frac{f(x)-f(1)}{x-1} = -\frac{1}{2\sqrt{2}} $, $ \sqrt{8} \times $ this is $-1$. Q42: $ \lim_{x \to \infty} x e^{-x} = 0 $ 2.3 Tangents and Linear Approximation Tangent Line: $ y = f’(a)(x-a) + f(a) $ Linear Approximation: $ L(x) = f(a) + f’(a)(x-a) $ Example: $ f(x) = \cos x $, tangent at $ x=\pi/3 $: $ y = -\frac{\sqrt{3}}{2}(x-\pi/3) + \frac{1}{2} $ Example: $ f(x) = x^3 $, linear approximation at 1: $ L(x) = 3x-2 $ Exercises Q44: $ f(x) = 4x^2 $, tangent at $ x=2 $: $ y = 16x - 16 $ Q45: $ f(x) = 2x+5 $, linear approximation at 0: $ L(x) = 2x+5 $ Q46: Tangent at $ (1,0) $, passes through $ (5,8) $, slope $ f’(1) = 2 $ Q47: $ f(x) = x^3 + 3x $, slopes at $ x=-1,0,1 $: $ m_1 + m_2 + m_3 = 15 $ Q48: Same as Q46, $ f’(1) = 2 $ Q49: Tangent at $ (1, f(1)) $ is $ y=3x+2 $, so $ f(1) = 5 $ 2.4 Finding Critical Points: Applications Critical Point: $ f’(a) = 0 $ or $ f $ not differentiable at $ a $. Local Max/Min: Use second derivative test: $ f’’(a) > 0 $: local min $ f’’(a) < 0 $: local max $ f’’(a) = 0 $: test fails (saddle or inflection) Example: $ f(x) = x^3 - 12x $, critical points at $ x=2 $ (local min), $ x=-2 $ (local max) Example: $ f(x) = \cos x $, critical points at $ x=k\pi $, local max at even $ k $, local min at odd $ k $ Example: $ f(x) = x^3 + x^2 - x + 5 $, critical points at $ x=-1 $ (local max), $ x=1/3 $ (local min) Global Max/Min Definition: Maximum/minimum value of $ f $ over an interval. Example: $ f(x) = x^2 $ on $[-1,1]$, global min at $ x=0 $, global max at $ x=-1 $ and $ x=1 $. Exercises Q51: $ f(x) = \frac{1}{3}x^3 - x^2 + x $, only one critical point at $ x=1 $, second derivative test inconclusive (saddle point). Q52: $ f(x) = $$ \begin{cases} -x^2 + 2x + 3 & 0 \leq x \leq 50 \\ x^3 + 3 & -50 \leq x < 0 \end{cases} $$ $ $ x=1 $ is local max. $ x=-50 $ is global min. $ x=50 $ is not global min. Q53: At local min $ x=2 $, slope $ f’(2) = 0 $. At local max $ x=5 $, slope $ f’(5) = 0 $. Q56: Minimum of $ (x-\alpha)(x-\beta) $ at $ x = \frac{\alpha+\beta}{2} $. Q57: Max of $ 2xy $ when $ x+y=50 $: $ 1250 $. 3. Integration 3.1 Introduction Concept: Integration is used to compute areas under curves, volumes, and more. Example: Area of rectangle is $ lb $. 3.2 Computing Areas Area of Parallelogram: $ bh $ Area of Triangle: $ \frac{1}{2}bh $ Area of Trapezium: $ \frac{1}{2}(a+b)h $ Area of Circle: $ \pi r^2 $ (using limits or integration) Exercises Q65: Area of trapezium $ ACDB $: $ 6 $ sq units Q66: Sequence of circles, radius $ r_n = \frac{2n-1}{2n+2} $, area of biggest circle $ \leq \pi $, smallest circle $ \frac{\pi}{16} $ 3.3 Riemann Sums and the Integral Partition: Divide interval $[a,b]$ into subintervals. Riemann Sum: $ S(P) = \sum_{i=1}^n f(x_i^*) \Delta x_i $ Definite Integral: $ \int_a^b f(x) dx = \lim_{||P|| \to 0} S(P) $ Example: $ \int_1^2 (2x-1) dx = 2 $ Exercises Q70: For $ f(x) = x $ on $2$, Riemann sum with $ x_i^* = x_i $: $ \frac{25(n+1)}{2n} $ Q71: $ \int_0^2 (3x+1) dx = 8 $ 3.5 Anti-derivatives (Indefinite Integrals) Definition: $ F $ is anti-derivative of $ f $ if $ F’(x) = f(x) $. Fundamental Theorem of Calculus: $ \int_a^b f(x) dx = F(b) - F(a) $ Integration Rules: $ \int x^n dx = \frac{x^{n+1}}{n+1} + C $ ($ n \neq -1 $) $ \int \sin x dx = -\cos x + C $ $ \int e^x dx = e^x + C $ $ \int \frac{1}{x} dx = \ln|x| + C $ Integration by Parts Formula: $ \int f(x)g(x) dx = f(x) \int g(x) dx - \int f’(x) (\int g(x) dx) dx $ Example: $ \int x^2 2^x dx = \frac{x^2 2^x}{\ln 2} - \frac{x 2^{x+1}}{(\ln 2)^2} + \frac{2^{x+1}}{(\ln 2)^3} + C $ Integration by Substitution Formula: $ \int f(g(x))g’(x) dx = \int f(u) du $ where $ u = g(x) $ Example: $ \int \sin(5x) dx = -\frac{1}{5} \cos(5x) + C $ Basic Properties of Definite Integrals Linearity: $ \int (cf + dg) = c \int f + d \int g $ Additivity: $ \int_a^b f = \int_a^c f + \int_c^b f $ Improper Integrals: $ \int_a^\infty f(x) dx = \lim_{b \to \infty} \int_a^b f(x) dx $ Example: $ \int_1^\infty e^{-x} dx = \frac{1}{e} $ Piecewise Defined Functions Example: $ f(x) = $$ \begin{cases} x & 0 \leq x \leq 1 \\ 3-x & 1 < x \leq 2 \end{cases} $$ $, $ \int_0^2 f(x) dx = 2 $ Exercises Q75: $ \int_2^3 x^2 dx = \frac{19}{3} $ Q76: $ \int_1^2 (3x^2 + \frac{1}{x}) dx = 7 + \ln 2 $ Q77: $ \int_2^3 x^2 dx = \frac{19}{3} $ $ \int_1^2 \frac{1}{x} dx = \ln 2 $ $ \int_0^{\pi/3} \tan x \sec x dx = 1 $ $ \int_0^2 \frac{1}{\sqrt{4-x^2}} dx = \frac{\pi}{2} $ Q78: $ \int_1^\infty e^{-x} dx = \frac{1}{e} $ $ \int_1^\infty \frac{1}{x} dx $ does not exist Q81: Area between $ 3x^2 $ and $ 4-x^2 $: $ 3A = 16 $ Summary Table Concept Key Points & Formulas Example/Question Answer/Explanation Function $ f: A \to B $, domain, codomain, range $ f(x) = x^2 $, $ R = {(1,a), (2,b), (3,a), (1,b)} $ $ R $ is not a function Bounded Function $ m \leq f(x) \leq M $ $ f(x) = \frac{1}{x^2+1} $ Bounded Monotonicity Increasing/Decreasing $ f(x) = x^2 $ on $[0,\infty)$ Increasing Composition $ (g \circ f)(x) = g(f(x)) $ $ f(x) = x^2 $, $ g(x) = 3x^3 + 2x $ $ (g \circ f)(x) = 3x^6 + 2x^2 $ Sequence Limit $ \lim_{n \to \infty} a_n = L $ $ a_n = \frac{n+1}{n} $ 1 Function Limit $ \lim_{x \to a} f(x) = L $ $ \lim_{x \to 1} x^2 = 1 $ 1 Continuity $ \lim_{x \to a} f(x) = f(a) $ $ f(x) = x Differentiability $ f’(a) = \lim_{h \to 0} \frac{f(a+h)-f(a)}{h} $ $ f(x) = x Derivative Rules Sum, Product, Quotient, Chain $ (x^3)’ = 3x^2 $ 3x² L’Hôpital’s Rule $ \lim \frac{f}{g} = \lim \frac{f’}{g’} $ $ \lim_{x \to 0} \frac{\sin x}{x} $ 1 Tangent Line $ y = f’(a)(x-a) + f(a) $ $ f(x) = x^3 $ at $ x=1 $ $ y = 3x - 2 $ Critical Points $ f’(a) = 0 $ or not differentiable $ f(x) = x^3 - 12x $ $ x=2 $ (min), $ x=-2 $ (max) Riemann Sum $ S(P) = \sum f(x_i^*) \Delta x_i $ $ f(x) = x $ on $2 $ $ \frac{25(n+1)}{2n} $ Definite Integral $ \int_a^b f(x) dx $ $ \int_0^2 (3x+1) dx $ 8 Anti-derivative $ F’(x) = f(x) $ $ \int x^n dx = \frac{x^{n+1}}{n+1} $ $ n \neq -1 $ Integration by Parts $ \int fg = f \int g - \int f’ (\int g) $ $ \int x^2 2^x dx $ See example Integration by Substitution $ \int f(g(x))g’(x) dx = \int f(u) du $ $ \int \sin(5x) dx $ $ -\frac{1}{5} \cos(5x) $ This structured approach covers all major concepts from the PDF with definitions, examples, questions, and answers for clarity and practice1.

  • M1_VOL3_GRAPHTHEORY 📈

    06 M1_VOL3_GRAPHTHEORY 📈

    explain all concepts from this pdf with detailed structure , examples, related questions & answers with ease to understandHere is a structured, detailed explanation of all major concepts in the PDF M1_VOL3_GRAPHTHEORY.pdf, including definitions, examples, related questions, and answers—all presented for easy understanding1. 1. Graphs and General Graph Problems 1.1 Introduction Concept: Graphs model pairwise relationships between objects. Example: Social networks (people as vertices, friendships as edges), communication networks (devices as vertices, links as edges)1. Key Idea: Graphs abstract real-world situations by focusing on connections rather than physical layout. 1.2 Graph Definition: A graph $ G = (V, E) $ consists of a set of vertices (nodes) $ V $ and a set of edges $ E $ connecting pairs of vertices. Example: $ V = {A, B, C, D, E, F, G} $, $ E = {(A,B), (A,C), (B,D), (B,E), (C,F), (C,G)} $1. Undirected Graph: Edges have no direction; if $(A, B)$ is present, so is $(B, A)$ implicitly. 1.3 Types of Graphs Simple Graph: No loops or multiple edges between the same pair of vertices. Directed Graph: Edges have direction; $(A, B)$ does not imply $(B, A)$. Undirected Graph: All edges are bidirectional. Complete Graph: Every pair of distinct vertices is connected by an edge. Example: A complete graph with 4 vertices has every vertex connected to every other vertex. 1.4 Paths and Reachability Path: A sequence of vertices connected by edges. Example: $ A \rightarrow B \rightarrow C \rightarrow D $ is a path from $ A $ to $ D $1. Reachability: Vertex $ u $ is reachable from $ v $ if there is a path from $ v $ to $ u $. Example: In a social network, if Alice is connected to Bob, who is connected to Charlie, Alice is reachable from Charlie via Bob. 1.5 More on Graphs 1.5.1 Graph Coloring Definition: Assign colors to vertices so that no two adjacent vertices have the same color. Chromatic Number: Minimum number of colors needed. Example: Scheduling classes so that conflicting classes (edges) are not at the same time (color). Result: 2 colors may suffice for some graphs1. Related Question: What is the minimum number of colors required for a given graph? Answer: Depends on the graph; for the example in the PDF, it is 2. 1.5.2 Vertex Cover Definition: A set of vertices such that every edge is incident to at least one vertex in the set. Example: In a graph, ${2,4,5}$ may be a vertex cover1. Related Question: Find a vertex cover for a given graph. Answer: For the example, ${2,4,5}$ is a vertex cover. 1.5.3 Independent Set Definition: A set of vertices where no two are adjacent. Example: ${1,4,6}$ may be a maximum independent set1. Related Question: Find a maximum independent set. Answer: For the example, ${1,4,6}$ is a maximum independent set. 1.5.4 Matching Definition: A set of edges without common vertices. Example: ${(1,2), (3,4), (5,6)}$ is a matching1. Related Question: Find a maximum matching. Answer: For the example, ${(1,2), (3,4), (5,6)}$ is a maximum matching. 1.6 Representing Graphs 1.6.1 Adjacency Matrix Definition: A square matrix where $ A_{ij} = 1 $ if there is an edge between vertices $ i $ and $ j $, else 0. Example: $$ A = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{pmatrix} $$ Related Question: Find the adjacency matrix for a given graph. Answer: See above matrix for the example. 1.6.2 Adjacency List Definition: For each vertex, list its neighbors. Example: $ A: {B} $ $ B: {A, C, D, E} $ $ C: {B, D} $ $ D: {B, C, E} $ $ E: {B, D} $ 1.7 Breadth-First Search (BFS) Algorithm: Explore all neighbors of a vertex before moving to the next level. Example: Starting from vertex 1, BFS visits: 1, 2, 4, 3, 5, 6, 71. Applications: Shortest path in unweighted graphs. Related Question: Draw the BFS tree starting from vertex $ E $. Answer: The tree will show $ E $ connected to its neighbors, then their neighbors, etc. 1.8 Depth-First Search (DFS) Algorithm: Explore as far as possible along each branch before backtracking. Example: Starting from vertex 4, DFS may visit: 4, 0, 1, 2, 31. Applications: Topological sorting, strongly connected components, maze solving. Related Question: Draw the DFS tree starting from vertex $ E $. Answer: The tree will show a path as deep as possible before backtracking. 1.9 Degree of a Vertex Definition: Number of edges incident to a vertex (undirected graph). Example: In a complete graph with 4 vertices, each vertex has degree 3. Related Question: What is the degree of each vertex in a given graph? Answer: For the complete graph, all degrees are 3. 1.10 Indegrees and Outdegrees Indegree: Number of edges entering a vertex (directed graph). Outdegree: Number of edges leaving a vertex (directed graph). Example: For a directed graph, sum of indegrees equals sum of outdegrees. Related Question: What are the indegree and outdegree of each vertex? Answer: For the example, indegree sequence is (1,1,1,0), outdegree is (1,2,1,0). 1.11 Problems Example Question: Find the shortest path connecting two people in a social network. Answer: Use BFS to find the shortest path. More Questions: Find adjacency matrix, vertex cover, independent set, BFS/DFS trees, chromatic number, etc. 2. DAGs, Topological Sorting, and Longest Path 2.1 Directed Acyclic Graph (DAG) Definition: Directed graph with no directed cycles. Example: Task dependencies in project scheduling. Related Question: Why is a given graph not a DAG? Answer: Because it contains a directed cycle. 2.2 Topological Sorting Definition: Linear ordering of vertices such that for every directed edge $(u, v)$, $u$ comes before $v$. Algorithm: Repeatedly pick vertices with indegree 0, remove them, and update indegrees. Example: For a DAG, one possible topological order is $A, B, D, E, C, F$1. Related Question: Find a topological sorting for a given DAG. Answer: $A, B, D, E, C, F$ is one possible order. 2.3 Longest Path in a DAG Algorithm: Topologically sort the graph, then for each vertex, update the longest path to its neighbors. Example: In a DAG, the longest path can be found using dynamic programming after topological sort1. 2.4 Transitive Closure Definition: A graph that includes an edge $(u, v)$ if there is a path from $u$ to $v$ in the original graph. Example: If there are paths $A \rightarrow B \rightarrow C$, then the transitive closure includes $A \rightarrow C$1. Related Question: Find the transitive closure of a given graph. Answer: Add edges for all reachable pairs. 2.5 Matrix Multiplication Adjacency Matrix: Represents graph connectivity. Reachability Matrix: $A^k$ gives paths of length $k$. Transitive Closure Matrix: $A + A^2 + A^3 + \ldots + A^n$. Example: For a graph, compute $A^2$ to find paths of length 21. Related Question: Compute $A^2$ for a given adjacency matrix. Answer: Multiply the matrix by itself. 2.6 Problems Example Question: Which relation represents the transitive closure? Answer: The relation that includes all reachable pairs. More Questions: Find matrix powers, topological sorting, longest path, etc. 3. Weighted Graphs and Shortest Path Algorithms 3.1 Weighted Graph Definition: Each edge has a weight (distance, cost, time). Example: Cities connected by roads with distances1. 3.2 Dijkstra’s Algorithm Algorithm: Finds shortest path from a source to all other vertices in a graph with non-negative weights. Example: Shortest path from $A$ to $D$: $A \rightarrow C \rightarrow D$ with total weight 31. Related Question: Find the shortest path from $A$ to $D$. Answer: $A \rightarrow C \rightarrow D$ with weight 3. 3.3 Bellman-Ford Algorithm Algorithm: Finds shortest paths from a source in graphs with negative weights (no negative cycles). Example: After iterations, shortest distances from $A$: $A(0), B(-1), C(2), D(1), E(4)$1. Related Question: What are the shortest distances after Bellman-Ford? Answer: As above. 3.4 Spanning Trees Definition: A subgraph that is a tree and connects all vertices. Example: A tree connecting all cities with minimum total road length1. 3.5 Prim’s Algorithm Algorithm: Greedily adds the shortest edge connecting a tree vertex to a non-tree vertex. Example: Starting from $A$, add edges $(A,C)$, $(C,E)$, etc., to form a minimum spanning tree1. Related Question: Find the minimum spanning tree using Prim’s algorithm. Answer: Add edges in order of smallest weight, avoiding cycles. 3.6 Kruskal’s Algorithm Algorithm: Adds edges in order of increasing weight, skipping those that form cycles. Example: Add edges $(B,D)$, $(A,C)$, $(A,F)$, etc., to form a minimum spanning tree1. Related Question: Find the minimum spanning tree using Kruskal’s algorithm. Answer: Add edges in order of increasing weight, skipping those that form cycles. 3.7 Problems Example Question: At what time will city $G$ start flooding if water spreads along weighted edges? Answer: 8 minutes1. More Questions: Find shortest paths, minimum spanning trees, order of edge addition, etc. 4. Answers to Selected Questions Graph Coloring: Minimum number of colors is 2 for the example graph. Vertex Cover: ${2,4,5}$ is a vertex cover. Independent Set: ${1,4,6}$ is a maximum independent set. Matching: ${(1,2), (3,4), (5,6)}$ is a maximum matching. BFS/DFS Trees: See above for examples. Degree/Indegree/Outdegree: See above for examples. Topological Sorting: $A, B, D, E, C, F$ is one possible order. Transitive Closure: Add edges for all reachable pairs. Dijkstra’s Algorithm: Shortest path from $A$ to $D$ is $A \rightarrow C \rightarrow D$ with weight 3. Bellman-Ford: Shortest distances from $A$ are $A(0), B(-1), C(2), D(1), E(4)$. Prim’s/Kruskal’s: Add edges in order of smallest weight, avoiding cycles. Summary Table Concept Definition/Algorithm Example/Question Answer/Explanation Graph $G = (V, E)$ Social network Vertices: people, edges: friendships Path/Reachability Sequence of connected vertices $A \rightarrow B \rightarrow C$ Path from $A$ to $C$ Graph Coloring Color vertices, no two adjacent same Scheduling classes 2 colors for example graph Vertex Cover Set covers all edges ${2,4,5}$ Covers all edges Independent Set No two vertices adjacent ${1,4,6}$ Maximum independent set Matching No two edges share a vertex ${(1,2), (3,4), (5,6)}$ Maximum matching Adjacency Matrix $A_{ij} = 1$ if edge $i-j$ See matrix above Represents graph connectivity BFS Explore level by level 1, 2, 4, 3, 5, 6, 7 Shortest path in unweighted DFS Explore as deep as possible 4, 0, 1, 2, 3 Topological sorting, etc. Degree Number of edges at vertex 3 in complete 4-vertex graph All degrees 3 Indegree/Outdegree Edges in/out (directed graph) Indegree: (1,1,1,0), Outdegree: (1,2,1,0) Sums equal DAG No directed cycles Task dependencies No cycles Topological Sorting Linear order, edges $u \rightarrow v$, $u$ before $v$ $A, B, D, E, C, F$ One possible order Longest Path (DAG) Dynamic programming after topo sort See example Longest path found Transitive Closure Add edges for all reachable pairs $A \rightarrow C$ if $A \rightarrow B \rightarrow C$ All reachable pairs Matrix Multiplication $A^k$ gives paths of length $k$ See matrix multiplication Paths of length $k$ Dijkstra’s Algorithm Shortest path, non-negative weights $A \rightarrow C \rightarrow D$ Shortest path, weight 3 Bellman-Ford Shortest path, negative weights $A(0), B(-1), C(2), D(1), E(4)$ Shortest distances Spanning Tree Tree connecting all vertices See example Connects all, no cycles Prim’s Algorithm Greedy, add smallest edge $(A,C), (C,E), \ldots$ Minimum spanning tree Kruskal’s Algorithm Add edges in order, avoid cycles $(B,D), (A,C), \ldots$ Minimum spanning tree This structured approach covers all major concepts in the graph theory PDF, with clear definitions, examples, and answers to related questions1.

  • Python - IITM 🐍

    07 Python - IITM 🐍

    Week 1 Lecture Notes 🗒️ PRINT 👨🏽‍💻 Numbers are treated as numbers only when put without apostrophe/speech marks Strings require either single or double quotes Uses only round brackets () Uses comma to separate strings/variables print("Hello world") print('Hello world', 'Hello mom', 'Hello nietzsche') print(10) VARIABLES 🔤 💡 Use well defined names for variables instead of a/b/c etc.

  • Python 3 Cheatsheet (Enhanced Edition) 🐍

    08 Python 3 Cheatsheet (Enhanced Edition) 🐍

    # Sample code demonstrating key concepts def main(): # String formatting example name = "Alice" age = 30 print(f"{name} is {age} years old") # Alice is 30 years old if __name__ == "__main__": main() Python 3 Cheatsheet (Enhanced Edition)Core Syntax Essentials 1.1 Variables & Data Types