Cheatsheet Engineering for Computer Science Engineering - RRB JE for Computer

2. Calculus

2.1 Limits and Continuity

2.2 Differentiation

2.2.1 Key Derivatives

• d/dx(xⁿ) = nx^n-1; d/dx(e^x) = e^x; d/dx(a^x) = a^xln(a)
• d/dx(ln x) = 1/x; d/dx(sin x) = cos x; d/dx(cos x) = -sin x
• d/dx(tan x) = sec²x; d/dx(cot x) = -csc²x
• d/dx(sin^-1x) = 1/√(1-x²); d/dx(tan^-1x) = 1/(1+x²)

2.3 Mean Value Theorems

2.4 Taylor and Maclaurin Series

2.5 Integration

2.5.1 Standard Integrals

• ∫xⁿdx = xⁿ⁺¹/(n+1) + C (n ≠ -1); ∫(1/x)dx = ln|x| + C
• ∫e^xdx = e^x + C; ∫a^xdx = a^x/ln(a) + C
• ∫sin x dx = -cos x + C; ∫cos x dx = sin x + C
• ∫sec²x dx = tan x + C; ∫csc²x dx = -cot x + C
• ∫dx/(x²+a²) = (1/a)tan^-1(x/a) + C
• ∫dx/√(a²-x²) = sin^-1(x/a) + C

2.6 Definite Integrals

• Fundamental Theorem: ∫_a^b f(x)dx = F(b) - F(a) where F'(x) = f(x)
• ∫_a^b f(x)dx = -∫_b^a f(x)dx
• ∫_a^b f(x)dx = ∫_a^c f(x)dx + ∫_c^b f(x)dx
• If f is even: ∫_-a^a f(x)dx = 2∫₀^a f(x)dx
• If f is odd: ∫_-a^a f(x)dx = 0
• ∫₀^a f(x)dx = ∫₀^a f(a-x)dx (King's property)

2.7 Multivariable Calculus

2.8 Multiple Integrals

• Double integral: ∫∫_R f(x,y) dA = ∫_a^b ∫_c^d f(x,y) dy dx
• Change of variables: ∫∫_R f(x,y) dx dy = ∫∫_S f(g(u,v), h(u,v)) |J| du dv
• Jacobian: J = ∂(x,y)/∂(u,v) = x_uy_v - x_vy_u
• Polar coordinates: dx dy = r dr dθ; x = r cos θ, y = r sin θ

3. Differential Equations

3.1 First Order ODEs

3.2 Second Order Linear ODEs

3.3 Laplace Transform

3.3.1 Laplace Transform Properties

• Linearity: L{af(t) + bg(t)} = aL{f(t)} + bL{g(t)}
• First derivative: L{f'(t)} = sL{f(t)} - f(0)
• Second derivative: L{f''(t)} = s²L{f(t)} - sf(0) - f'(0)
• Integration: L{∫₀^t f(τ)dτ} = L{f(t)}/s
• First shifting: L{e^atf(t)} = F(s-a)
• Second shifting: L{f(t-a)u(t-a)} = e^(-as)F(s), where u(t-a) is the unit step function.
• Convolution: L{f*g} = L{f}·L{g}

4. Probability and Statistics

4.1 Probability Basics

4.2 Random Variables

4.3 Probability Distributions

4.4 Statistical Inference

4.5 Hypothesis Testing

• Null hypothesis H₀: statement to be tested
• Alternative hypothesis H₁: statement accepted if H₀ rejected
• Type I error: reject H₀ when true (α = significance level)
• Type II error: fail to reject H₀ when false (β)
• Power = 1 - β
• p-value: probability of observing test statistic as extreme as observed, given H₀ true
• Reject H₀ if p-value < α (significance level).

5. Graph Theory

5.1 Basic Definitions

5.2 Special Graphs

5.3 Graph Representations

5.4 Graph Traversal

• BFS (Breadth-First Search): uses queue; explores level by level; O(V+E)
• DFS (Depth-First Search): uses stack/recursion; explores depth first; O(V+E)
• BFS finds shortest path in unweighted graph
• DFS used for cycle detection, topological sorting

5.5 Shortest Path Algorithms

5.6 Minimum Spanning Tree

5.7 Graph Properties

• Chromatic number: minimum colors needed to color vertices (no adjacent same color)
• For a connected planar graph, Euler's formula holds: V - E + F = 2.
• Bipartite graph is 2-colorable
• Clique: complete subgraph
• Independent set: vertices with no edges between them
• Vertex cover: set of vertices incident to all edges

6. Combinatorics

6.1 Basic Counting

6.2 Binomial Theorem

• (x+y)ⁿ = Σ C(n,k)x^n-ky^k for k=0 to n
• C(n,0) + C(n,1) + ... + C(n,n) = 2ⁿ
• C(n,0) - C(n,1) + C(n,2) - ... = 0
• C(n,r) = C(n,n-r)
• C(n,r) + C(n,r+1) = C(n+1,r+1) (Pascal's identity)

6.3 Pigeonhole Principle

• If n items placed in m containers and n > m, at least one container has > 1 item
• Generalized: if n items in m containers, at least one has ≥ ⌈n/m⌉ items

6.4 Inclusion-Exclusion Principle

• |A∪B| = |A| + |B| - |A∩B|
• |A∪B∪C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|
• General: |A₁∪...∪A_n| = Σ|A_i| - Σ|A_i∩A_j| + Σ|A_i∩A_j∩A_k| - ...

6.5 Generating Functions

6.6 Recurrence Relations

6.6.1 Master Theorem Cases

• Case 1: f(n) = O(n^log_ba-ε) → T(n) = Θ(n^log_ba)
• Case 2: f(n) = Θ(n^log_ba) → T(n) = Θ(n^log_ba log n)
• Case 3: f(n) = Ω(n^log_ba+ε) and af(n/b) ≤ cf(n) → T(n) = Θ(f(n))

7. Mathematical Logic

7.1 Propositional Logic

7.2 Logical Equivalences

• De Morgan's Laws: ¬(p∧q) ≡ ¬p∨¬q; ¬(p∨q) ≡ ¬p∧¬q
• Commutative: p∧q ≡ q∧p; p∨q ≡ q∨p
• Associative: (p∧q)∧r ≡ p∧(q∧r); (p∨q)∨r ≡ p∨(q∨r)
• Distributive: p∧(q∨r) ≡ (p∧q)∨(p∧r); p∨(q∧r) ≡ (p∨q)∧(p∨r)
• Identity: p∧T ≡ p; p∨F ≡ p
• Domination: p∨T ≡ T; p∧F ≡ F
• Idempotent: p∧p ≡ p; p∨p ≡ p
• Double negation: ¬¬p ≡ p
• Implication: p→q ≡ ¬p∨q
• Contrapositive: p→q ≡ ¬q→¬p

7.3 Predicate Logic

7.4 Rules of Inference

7.5 Proof Techniques

• Direct Proof: assume p, derive q to prove p→q
• Proof by Contrapositive: prove ¬q→¬p instead of p→q
• Proof by Contradiction: assume ¬conclusion, derive contradiction
• Proof by Cases: divide into exhaustive cases, prove each
• Mathematical Induction: prove P(1), prove P(k)→P(k+1)
• Strong Induction: prove P(1), prove [P(1)∧...∧P(k)]→P(k+1)

8. Set Theory and Relations

8.1 Set Operations

8.2 Set Identities

• De Morgan's: (A∪B)' = A'∩B'; (A∩B)' = A'∪B'
• Absorption: A∪(A∩B) = A; A∩(A∪B) = A
• Distributive: A∩(B∪C) = (A∩B)∪(A∩C); A∪(B∩C) = (A∪B)∩(A∪C)
• |A∪B| = |A| + |B| - |A∩B|
• |A×B| = |A|×|B|

8.3 Relations

8.4 Functions

8.5 Equivalence Relations and Partitions

• Equivalence class [a] = {x : (x,a)∈R}
• Equivalence classes partition the set
• Each element belongs to exactly one equivalence class
• Partition: collection of disjoint non-empty subsets whose union is the entire set

9. Number Theory

9.1 Divisibility

9.2 Prime Numbers

• Prime: integer p > 1 divisible only by 1 and p
• Fundamental Theorem of Arithmetic: every integer > 1 has unique prime factorization
• Infinitely many primes exist
• Sieve of Eratosthenes: algorithm to find all primes up to n
• If p is prime and p|ab, then p|a or p|b

9.3 Modular Arithmetic

9.4 Euler's Totient Function

• φ(n) = count of integers k where 1 ≤ k ≤ n and gcd(k,n) = 1
• φ(p) = p-1 if p is prime
• φ(p^k) = p^k - p^k-1 = p^k(1 - 1/p)
• φ(mn) = φ(m)φ(n) if gcd(m,n) = 1
• φ(n) = n∏(1 - 1/p) over all prime divisors p of n

9.5 Chinese Remainder Theorem

• System: x ≡ a₁ (mod n₁), x ≡ a₂ (mod n₂), ..., x ≡ a_k (mod n_k)
• If n₁, n₂, ..., n_k are pairwise coprime, unique solution mod N where N = n₁n₂...n_k
• Solution: x = Σ(a_iM_iy_i) mod N where M_i = N/n_i and y_i = M_i^-1 mod n_i

10. Boolean Algebra

10.1 Basic Laws

10.2 Normal Forms

10.3 Karnaugh Maps

• Graphical method for Boolean function simplification
• Adjacent cells differ by exactly one variable
• Group 1s (for SOP) or 0s (for POS) in powers of 2: 1, 2, 4, 8, 16
• Larger groups yield simpler expressions
• Don't care conditions (X) can be treated as 0 or 1 for optimization

10.4 Logic Gates

10.5 Universal Gates

• NAND gate is universal: can implement NOT, AND, OR
• NOT: A NAND A = (A·A)' = A'
• AND: (A NAND B) NAND (A NAND B)
• OR: (A NAND A) NAND (B NAND B)
• NOR gate is also universal

11. Complex Numbers

11.1 Basic Operations

11.2 Polar Form

• z = r(cos θ + i sin θ) = re^iθ (Euler's formula)
• r = |z|, θ = arg(z)
• Multiplication: r₁e^iθ₁ · r₂e^iθ₂ = r₁r₂e^{i(θ₁+θ₂)}
• Division: r₁e^iθ₁ / r₂e^iθ₂ = (r₁/r₂)e^{i(θ₁-θ₂)}
• De Moivre's Theorem: (cos θ + i sin θ)ⁿ = cos(nθ) + i sin(nθ)

11.3 Properties

• z + z̄ = 2Re(z); z - z̄ = 2i·Im(z)
• z·z̄ = |z|²
• |z₁z₂| = |z₁||z₂|
• |z₁/z₂| = |z₁|/|z₂|
• arg(z₁z₂) = arg(z₁) + arg(z₂)
• arg(z₁/z₂) = arg(z₁) - arg(z₂)
• e^iπ + 1 = 0 (Euler's identity)

11.4 Roots of Complex Numbers

• n-th roots of z = re^iθ: z_k = r^1/ne^i(θ+2πk)/n for k = 0,1,...,n-1
• n-th roots of unity: e^2πik/n for k = 0,1,...,n-1
• Sum of n-th roots of unity = 0

12. Numerical Methods

12.1 Root Finding

12.2 Interpolation

12.3 Numerical Integration

12.4 Numerical Differentiation

• Forward difference: f'(x) ≈ [f(x+h) - f(x)]/h
• Backward difference: f'(x) ≈ [f(x) - f(x-h)]/h
• Central difference: f'(x) ≈ [f(x+h) - f(x-h)]/(2h)
• Second derivative: f''(x) ≈ [f(x+h) - 2f(x) + f(x-h)]/h²

12.5 Solution of Linear Systems