Mathematics for BCA — Sem 2 (Discrete Maths & Statistics)

BCA Mathematics — Introduction

Discrete Mathematics: Countable, distinct structures — sets, logic, graphs (vs continuous calculus).

Relevance to BCA:

Set Theory     → Database design, SQL
Logic          → Programming conditions, Boolean circuits
Graphs         → Networks, algorithms, data structures
Combinatorics  → Algorithm analysis, cryptography
Probability    → AI/ML, software testing
Statistics     → Data analysis, testing, quality

---

1. Set Theory

Basic Operations:

A = {1, 2, 3, 4, 5}
B = {3, 4, 5, 6, 7}

Union:        A ∪ B = {1,2,3,4,5,6,7}
Intersection: A ∩ B = {3,4,5}
Difference:   A - B = {1,2} (in A but not B)
Complement:   A' = U - A (universal set minus A)
Symmetric Diff: A △ B = (A-B) ∪ (B-A) = {1,2,6,7}

Cartesian Product:
A = {1,2}, B = {a,b}
A × B = {(1,a), (1,b), (2,a), (2,b)}  |A×B| = |A|×|B|

Set Laws:

Commutative:  A ∪ B = B ∪ A
Associative:  (A ∪ B) ∪ C = A ∪ (B ∪ C)
Distributive: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
De Morgan's:  (A ∪ B)' = A' ∩ B'
              (A ∩ B)' = A' ∪ B'
Identity:     A ∪ ∅ = A,  A ∩ U = A
Idempotent:   A ∪ A = A,  A ∩ A = A

Venn Diagrams — important for exam!

---

2. Mathematical Logic

Propositions: True or false statements.

Connectives:
p ∧ q   — AND (conjunction): true only if both true
p ∨ q   — OR (disjunction): true if any true
¬p      — NOT (negation)
p → q   — Implication: false only if p=T, q=F
p ↔ q   — Biconditional: true if both same

Truth Table: p → q (If p then q):
p | q | p→q
T | T |  T
T | F |  F    ← only false case!
F | T |  T
F | F |  T

Important Equivalences:

p → q  ≡  ¬p ∨ q
p ↔ q  ≡  (p→q) ∧ (q→p)
¬(p ∧ q) ≡ ¬p ∨ ¬q    (De Morgan's)
¬(p ∨ q) ≡ ¬p ∧ ¬q    (De Morgan's)

Predicates & Quantifiers:

Universal: ∀x P(x)  — "For all x, P(x) is true"
Existential: ∃x P(x) — "There exists x such that P(x)"

Example:
∀x (x > 0 → x² > 0)  — True for real numbers
∃x (x + 1 = 0)        — True (x = -1)

Negation:
¬(∀x P(x)) ≡ ∃x ¬P(x)
¬(∃x P(x)) ≡ ∀x ¬P(x)

---

3. Relations & Functions

Relation R on A × B: Subset of Cartesian product.

A = {1,2,3}, R = {(1,1),(2,2),(3,3),(1,2),(2,3)}

Properties:
Reflexive:   (a,a) ∈ R ∀a ∈ A  → (1,1),(2,2),(3,3) ✅
Symmetric:   (a,b)→(b,a) ∈ R   → (1,2) ∈ R but (2,1) ∉ R ❌
Transitive:  (a,b),(b,c) → (a,c) ∈ R  → (1,2),(2,3)→(1,3)? ❌

Equivalence Relation: Reflexive + Symmetric + Transitive
Partial Order: Reflexive + Antisymmetric + Transitive

Functions:

f: A → B  (domain A, codomain B)

Injective (one-to-one): f(a)=f(b) ⟹ a=b  (no two inputs same output)
Surjective (onto): every b ∈ B has some a with f(a)=b
Bijective: both injective and surjective → invertible

Examples:
f(x) = x² on R: not injective (f(2)=f(-2)=4), not surjective (negative values)
f(x) = 2x+1 on R: bijective ✅

---

4. Combinatorics

Counting Principles:

Addition Rule: mutually exclusive events
  |A ∪ B| = |A| + |B|  (disjoint)

Multiplication Rule: sequential independent choices
  |A × B| = |A| × |B|

Permutations (order matters):
P(n,r) = n!/(n-r)!
5 students, 3 prizes: P(5,3) = 5×4×3 = 60

Combinations (order doesn't matter):
C(n,r) = n! / (r! × (n-r)!)
5 students, choose 3: C(5,3) = 10

Binomial Theorem:
(a+b)ⁿ = Σ C(n,k) aⁿ⁻ᵏ bᵏ
(a+b)³ = a³ + 3a²b + 3ab² + b³

Pigeonhole Principle:
n+1 items in n containers → at least one container has ≥2

---

5. Graph Theory

Graph G = (V, E)
V = vertices (nodes), E = edges

Types:
Undirected: edges have no direction
Directed (Digraph): edges have direction
Weighted: edges have values
Simple: no self-loops, no multiple edges
Complete (Kₙ): every pair of vertices connected

Terminology:
Degree: number of edges at a vertex
Path: sequence of vertices connected by edges
Cycle: path that returns to start vertex
Connected: path exists between every pair
Tree: connected, acyclic graph (N-1 edges)

Graph Representations:

Adjacency Matrix:
     1 2 3 4
  1 [0 1 1 0]
  2 [1 0 1 1]
  3 [1 1 0 0]
  4 [0 1 0 0]

Adjacency List:
1 → [2, 3]
2 → [1, 3, 4]
3 → [1, 2]
4 → [2]

Matrix: O(V²) space, O(1) edge lookup
List: O(V+E) space, O(degree) edge lookup — better for sparse graphs

Graph Traversals:

BFS (Breadth First Search):
  Queue-based, level by level
  Shortest path in unweighted graph
  
DFS (Depth First Search):
  Stack/recursion, go deep
  Topological sort, cycle detection, connected components

---

6. Probability

P(A) = favourable outcomes / total outcomes

P(A ∪ B) = P(A) + P(B) - P(A ∩ B)  (addition rule)
P(A ∩ B) = P(A) × P(B)  (if A,B independent)

Conditional: P(A|B) = P(A ∩ B) / P(B)

Bayes' Theorem:
P(A|B) = P(B|A) × P(A) / P(B)

Example: Test for disease
P(disease) = 0.01 (prior)
P(positive|disease) = 0.95 (sensitivity)
P(positive|no disease) = 0.05 (false positive)

P(disease|positive) = 0.95×0.01 / (0.95×0.01 + 0.05×0.99)
                    = 0.0095 / (0.0095 + 0.0495)
                    = 0.161  ← only 16%! (base rate matters)

Random Variables:

Discrete: P(X=x) = probability mass function
  Binomial: P(X=k) = C(n,k) pᵏ(1-p)ⁿ⁻ᵏ
  Mean = np, Variance = np(1-p)

Continuous: f(x) = probability density function
  Normal: bell curve, μ±σ contains 68%, μ±2σ = 95%

---

7. Statistics Basics

import statistics, numpy as np

data = [85, 90, 78, 92, 88, 76, 95, 82]

# Central Tendency
mean   = np.mean(data)         # 85.75
median = np.median(data)       # 86.5
mode   = statistics.mode(data) # no repeat in this case

# Spread
variance = np.var(data)         # population variance
std_dev  = np.std(data)         # standard deviation
range_   = max(data) - min(data)

# Correlation
x = [1,2,3,4,5]
y = [2,4,5,4,5]
correlation = np.corrcoef(x, y)[0,1]  # -1 to +1

---

Exam Important Questions

1. Set operations — A=5, B=7: union, intersection, A-B, A△B
2. Truth table banao: p→q, ¬p∨q, p↔q
3. P(n,r) aur C(n,r) formulas — solved examples
4. Graph kya hai? Types explain karo
5. BFS aur DFS algorithm explain karo
6. Bayes theorem — example ke saath
7. Relation kab equivalence relation hoti hai?
8. De Morgan's law prove karo (truth table se)

---

Viva Questions

Q: Computer Science mein induction principle kaise use hota hai? A: Algorithm correctness prove karne ke liye — base case (n=0/1 pe sahi), inductive step (agar n=k pe sahi hai to n=k+1 pe bhi sahi). Loop invariants prove karna bhi induction hai.

Q: Euler path aur Hamilton path mein kya fark hai? A: Euler path: har EDGE exactly once traverse karo (graph mein exactly 2 odd-degree vertices). Hamilton path: har VERTEX exactly once visit karo (NP-complete problem — no efficient algorithm known).

Q: Modular arithmetic ka cryptography mein use kya hai? A: RSA encryption: C = Mᵉ mod n, decrypt M = Cᵈ mod n. Large prime factorization ki difficulty pe based. Modular exponentiation fast hai (O(log e)), reverse (discrete log) slow hai.