Numbers PDF

# Numbers ## Real Numbers - **Natural numbers:** 1, 2, 3, 4,... - **Integers:** -3, -2, -1, 0, 1, 2, 3,... consists of the natural numbers with their negatives and 0. - **Rational numbers:** Ratios of numbers: $\frac{3}{7}$, $\frac{46}{46}$, 46, 0.17, $\frac{17}{100}$ - **Irrational numbers:** √3...

# Numbers ## Real Numbers - **Natural numbers:** 1, 2, 3, 4,... - **Integers:** -3, -2, -1, 0, 1, 2, 3,... consists of the natural numbers with their negatives and 0. - **Rational numbers:** Ratios of numbers: $\frac{3}{7}$, $\frac{46}{46}$, 46, 0.17, $\frac{17}{100}$ - **Irrational numbers:** √3, √5, 3√2 - Numbers cannot be expressed as a ratio of integers. ## Properties of Real Numbers - **Commutative:** - *Addition*: a + b = b + a - *Multiplication*: ab = ba - **Associative:** - *Addition*: (a+b)+c = a+(b+c) - *Multiplication*: (ab)c= a(bc) - **Distributive:** a(b+c) = ab+ac (b+c)a = ab+ac - **Additive Identity:** a + 0 = a (0 is the additive identity) - **Multiplicative Identity:** a x 1 = a (1 is the multiplicative identity) - **Absolute Value:** |a| - a to 0 on the real number line, is the distance from 0. - **Distance:** is always positive or zero, so we have |a|≥0 for every number a. - **If a is a real number then the absolute value of a is:** - |a| = a if a ≥ 0 - |a| = -a if a < 0 - If a & b are real numbers then the distance between the points a & b on the real line is d(a,b) = |b-a| - If a≠0 is any real number & n is a positive integer, then: - a⁰ = 1 - a⁻ⁿ = $\frac{1}{aⁿ}$ ## Scientific Notation - Scientific Notation eg: 56290 = 5.6 x 10⁴ - Floating point numbers are numbers with a decimal point or exponent notation ## Properties of Fractions 1. $\frac{a}{b}$ x $\frac{c}{d}$ = $\frac{ac}{bd}$ 2. $\frac{a}{b}$ ÷ $\frac{c}{d}$ = $\frac{a}{b}$ x $\frac{d}{c}$ 3. $\frac{a}{c}$ + $\frac{b}{c}$ = $\frac{a+b}{c}$ 4. $\frac{a}{b}$ + $\frac{c}{d}$ = $\frac{ad+bc}{bd}$ 5. $\frac{ac}{b}$ ÷ $\frac{a}{b}$ = c 6. If $\frac{a}{b}=\frac{c}{d}$ then ad = bc (cross multiplication) ## Properties of Absolute Value - |a| ≥ 0 - |a| = |-a| - |ab| = |a||b| - |$\frac{a}{b}$| = $\frac{|a|}{|b|}$ ## Properties of Exponents 1. aᵐ * aⁿ = aᵐ⁺ⁿ 2. aᵐ ÷ aⁿ = aᵐ⁻ⁿ 3. (aᵐ)ⁿ = aᵐⁿ 4. (ab)ⁿ = aⁿbⁿ 5. ($\frac{a}{b}$ )ⁿ = $\frac{aⁿ}{bⁿ}$ ## Real Numbers - **Rational numbers:** - **Integers:** - **Whole numbers** - **Natural numbers** - **Irrational numbers** ## Sources: - **imbd** movies - **NBA** sports - **google scholar** and **journals** etc. - **Kaggle** ## Numbers - (1,2,3): **natural numbers** - (-3,-2): **integers** - (11, 2/3): **rational** - (π, never ending number): **irrational** **irrational** is not inside **rational**. All of these combined make **real numbers**. ## Properties - **a % b** is not commutative: a % b ≠ b % a - **ab** is commutative: ab = ba ### Identity Properties - 0 = **additive identity** because you can add anything to it, but the answer will still be 0. - 1 = **multiplicative identity** because you can multiply anything by 1, and the answer will still be the same. ## Decimal Numbers - Decimal numbers in python are **float** - If any one is a **float**, the output will always be a **float** - There is a difference between 1.0 & 0.4 & 1. # Propositional Logic - A proposition is a declarative sentence that can be true or false, but not both. ## Logic Connectives - **Negation:** `¬p` - **Opposite** e.g. `¬p` is negation of `p` - **Conjunction:** `p∧q` - **Everyone** True = T - **Anyone** False = F - **Disjunction:** `pVq` - **Everyone** True = T - **And:** `p∧q` - **Anyone** False = F - **Or:** `pVq` - **Anyone** True = T - **Exclusive or:** `p⊕q` - **Only** 1 can be true, not both - **Conditional:** `p→q` - **Only** true if both `p` & `q` are true - **Converse:** Reverse the hypothesis & conclusion (e.g. `¬p → ¬q`) - **Contrapositive:** Negate both & reverse the order (e.g. `¬q → ¬p`) - **Inverse:** Negate both but keep the same order (e.g. `¬p → ¬q`) ## Logical Equivalencies - **Tautology:** Always true (e.g. `p V ¬p`) - **Contradiction:** Always false (e.g. `p ¬¬p`) - **Contingency:** Neither always true nor always false ## De Morgan's Laws - ¬(pVq) = ¬p∧¬q - ¬(p∧q) = ¬pV¬q ## Proofs - **Theorem:** A statement proven to be true. - **Direct proof:** Assume `p` is true & show `q` follows. - **Indirect proof:** Use the contrapositive (¬q → ¬p) or proof by contradiction (assume both `p` & `¬q`). # Predicates - Predicates are statements involving variables like x is > 3. - **Universal Quantifier (∀x):** Means “for all x”. - **Existential Quantifier (∃x):** Means “there exists an x”. # Sets - **Types of sets:** - **N:** {0,1,2,3...} = natural numbers - **Z:** {-2, -1, 0, 1, 2, 3...} = integers - **Z⁺:** {1, 2, 3...} = positive integers - **Q:** {p/q | p ∈ Z, q ∈ Z} = rational numbers - **R:** Real numbers - **R⁺:** Positive real numbers - **C:** Complex numbers - **Set equality:** Two sets are equal if & only if they have the same elements. ### Notation - **Element in set:** a ∈ A - **Element not in set:** a ∉ A - **Roster method:** {a, b, c} - **Set-builder method:** {x/x has property p} ## Set Operations - ****Union(A∪B):**** Elements in A or B or both - **Intersection(A∩B):** Elements in both A & B - **Difference(A-B):** Elements in A but not in B - **Complement(¬A):** Elements not in set A. - **Symmetric Difference(A⊕B):** Elements in either A or B but not both. ### Subsets - **Subset:** A⊆B if all elements are in B. - **Proper Subset:** A⊂B if A⊆B & A≠B. ### Empty Set (Ø) - Contains no elements. ### Cartesian Products - The set of ordered pairs from 2 sets: AxB = {(a, b) | a ∈ A, b ∈ B} ## Power Set - The set of all subsets of a given set S (P(S)) ## Multisets - A collection where elements can appear more than once. - **Operations:** - **Union:** Maximum multiplicities - **Intersection:** Minimum multiplicities - **Difference:** Subtract multiplicities **Operations supported:** Membership tests, iteration, length check, union/difference/intersection using hash tables ### Commutative Laws - **Addition :** a + b = b + a - **Multiplication:** a x b = b x a ## Multisets: - A ∪ (B ∪ C) = (A ∪ B) ∪ C - A ∩ (B ∩ C) = (A ∩ B) ∩ C ## Functions - A function is a mapping of elements from set A (domain) to set B (codomain), where each element in A is assigned exactly one element in B. - A function can also be referred to as a mapping or transformation. ## Components of a Function: - **Domain:** The set of inputs (a) - **Codomain:** The set of possible outputs (b) - **Range:** The actual set of outputs from the function, which is a subset of the codomain. ## Types of Functions: - **One-to-one (injective):** No two elements in the domain map to the same element in the codomain - **Onto (surjective):** Every element in the codomain is the image of at least one element in the domain. - **Bijective:** A function that is both injective & surjective. ## Operations on Functions: - **Addition:** Addition or multiplication of functions. - If f(x) = x² & g(x) = x - x², then: - *(f₁ + f₂)*(x) = x² + x - x² = x - *(f₁. f₂)*(x) = x² . (x - x²) = x³ - x⁴ ## Inverse Functions - A function is invertible if it is bijective (both one-to-one & onto). - The inverse function `f⁻¹` reverses the mapping of `f`, such that `f⁻¹(b) = a` when `f(a) = b`. ## Composition of Functions - The composition `(f ∘ g)(x)` means applying function `g` first, followed by applying function `f` to the result, and then applying function `f`. - e.g. f(x) = 2x + 3, g(x) = 3x + 2 - *(f ∘ g)*(x) = 6x + 7 - *(g ∘ f)*(x) = 6x + 11 ## Special Functions - **Floor function:** Assigns to x the largest integer less than or equal to x, denoted as `[x]`. - **Ceiling function:** Assigns to x the smallest integer greater than or equal to x, denoted as `[x]`. - **Factorial function:** `f(n) = n!`, where `n!` is the product of all positive integers up to n. e.g. `f(3) = 3! = 3x2x1 = 6` ## Functions in Python - You can pass data into a function (domain). - A function can return data using the return keyword. - A function is defined using `def`. ### Fibonacci Sequence - S_n = S_(n-1) + S_(n-2) - S_1 = 1 - S_2 = 1 # Sequences - A sequence is a function from a subset of integers to a set {a_n} where a_n is a term of a sequence. - A sequence is denoted by {a_n}, where a_n is a term of the sequence. ## Geometric Progression - A sequence of the form a, ar, ar²,..., where a = initial term & r = common ratio, which is discrete. - Analogue of the exponential function. - e.g. {b_n} = (-1)ⁿ + 1 ## Arithmetic Progression - A sequence of the form a, a + d, a + 2d..., where d = common difference. - Discrete analogue of a linear function. - e.g. {S_n} = -1 + 4n ## Recurrence Relations - Recurrence relations define a sequence in terms of its previous terms. ### Fibonacci Sequence: - Defined by the recursive relation F_0 = 0, F_1 = 1 & for n ≥ 2: F_n = F_(n-1) + F_(n-2) ## Summations - Notation used to express summation: Σ; e.g. Σ x_i - Supports arithmetic laws like commutativity and distributive. - **Geometric series summation:** - S_n = a(1 - r^(n+1)) / (1 - r) ## Python Sequences - Types include strings, tuples, lists, bytes, arrays, etc. - Python sequences support indexing, slicing, membership testing. ### Built-in Python Sequences - **Indexing:** Access individual elements. - **Slicing:** Access a range of elements. - **Summation:** `sum()` function - **Membership testing:** `in` operator # Graphs - Graphs are represented by vertices (nodes) and edges (connections between nodes). ## Types of Graphs - **Simple graph:** A graph with no loops or multiple edges. - **Multigraphs:** A graph that allows multiple edges between the same pair of vertices. - **Pseudographs:** Graphs may include loops (edges connecting a vertex to itself) and/or multiple edges. - **Directed graphs:** Edges have direction, represented by arrows. - **Directed multigraphs:** Directed graphs with multiple directed edges between vertices. ## Graph Terminology - **Vertices & edges:** Fundamental components. - **Adjacent vertices:** Vertices connected directly by an edge. - **Degree of a vertex:** Number of edges connected to a vertex. - **Path:** A sequence of edges connecting vertices. - **Cycle:** A path that starts and ends at the same vertex without repeating edges. ## Special Graphs - **Complete graphs:** Every pair of vertices is connected by an edge. - **Cycles:** Graphs where vertices form a closed loop with no cycles. - **Trees:** A connected graph with no cycles. ## Bipartite Graphs - A graph is bipartite if its vertices can be divided into two sets. - Such that no two vertices in the same set are adjacent. - **Bipartite graph theorem:** A graph is bipartite if and only if it's possible to assign one of two colors to each vertex so that no two adjacent vertices have the same color. ## Applications of Special graphs: - **LAN:** Graphs model network topologies, like star, ring, and hybrid topologies. ## Subgraphs - A subgraph is a portion of the original graph. - A subgraph is a subset of the vertices and/or a subset of the edges. ## Operations on Graphs - **Removing edges/vertices:** Delete an edge or vertex. - **Adding edges/vertices:** Add an edge or vertex. - **Edge contraction:** Combining 2 vertices connected by an edge. ## Representing Graphs 1. **Edge list:** A simple list of all edges in the graph, where each edge is represented as a pair (or tuple) of vertices. - E.g. [(A,B), (B,C), (C,A)] 2. **Adjacency list:** A collection of lists or arrays, where each index represents a vertex and stores a list of its adjacent vertices. - E.g. A → [B], B → [C], C → [A] 3. **Adjacency matrix:** A square matrix where rows and columns correspond to vertices. The entry at position (i, j) is 1 if there is an edge from vertex i to vertex j, and 0 if there is no edge. - Suitable for dense graphs or when quick lookup for adjacency is needed. - E.g. A B C: - A: [0 1 0] - B: [0 0 1] - C: [1 0 0] 4. **Incidence matrix:** A matrix where rows represent edges and entries are 1 if the vertex is incident on that edge, and 0 otherwise. - Used when you want to focus on the relationship between vertices and edges. - E.g. Edge (a, b) (b, c) - A: [1 0] - B: [1 1] - C: [0 1] ## Isomorphism of Graphs - Two graphs are isomorphic if their structures are identical under a relabeling of vertices. - Criteria for isomorphism: - Same number of vertices. - Same number of edges. - Same degree for corresponding vertices. ## Applications of Isomorphic Graphs: - Chemistry (molecular graphs for compounds) - Electronic circuit design ## Paths - A path is a sequence of edges that connects a series of vertices. - E.g. Modeling connectivity, routing problems in networks. ## Shortest Path Problems - **Weighted graphs:** Graphs where edges have weights. - E.g. Airline systems: - Cities = vertices - Flights = edges - Weights = distance, time - **Shortest-path algorithm:** Identify the minimum-weight path between two vertices. - Applications include transportation, communication networks, and logistics. ## Applications of Graphs: - **Vulnerability detection in programming** - **Code property graphs** used for **static analysis of source code**. ## Simple Graphs - E.g. A computer network ## Multigraphs - E.g. A computer network with multiple links between data centers. ## Pseudographs - E.g. A computer network with diagnostic links. ## Directed Graphs - E.g. A communication network with one-way communication links. ## Directed Multigraphs - E.g. A computer network with multiple one-way links. ## Degrees - **Isolated vertex:** A vertex is called isolated if its degree is 0. - **Pendant vertex:** A vertex is pendant if it has degree 1. ## Operations on Graphs - **Simple graph** - Multiple edges allowed: No - Loops allowed: No - **Multigraph** - Multiple edges allowed: Yes - Loops allowed: No - **Pseudograph** - Multiple edges allowed: Yes - Loops allowed: Yes - **Simple directed graph** - Multiple edges allowed: No - Loops allowed: No - **Directed multigraph** - Multiple edges allowed: Yes - Loops allowed: Yes - **Mixed graph** - Multiple edges allowed: Yes - Loops allowed: Yes ## Operations on a Graph: - **G - (b, c):** Removing edge (b, c) - **G + (e, d):** Adding edge (e, d) - **G contracted by replacing (b, c) by f:** Contracting edge (b, c) by `f`. - **a:** Removing edge - **b:** Adding edge - **c:** Edge contraction - **d:** Removing vertex ## Combinatorics - **Basic counting principle:** - **Sum rule:** For disjoint events A & B, the total number of outcomes is n_a + n_b. - E.g. Choosing between 2 disjoint sets. - **Product rule:** For sequential events with n_1, n_2,...n_k outcomes, the total number of outcomes is n_1 x n_2 x... x n_k. - E.g. Cartesian product interpretation for combined choices. - **Subtraction rule:** `(Inclusion-exclusion principle)` - Avoid counting overlapping sets. - E.g. Job applications overlapping between CS (220), BS (147) and both (51). ### Pigeonhole Principle - **Core principle:** If k+1 objects are placed in k boxes, at least one box holds ≥2 objects. - E.g. Among 367 people, at least 2 share a birthday. - **Generalized principle:** At least `⌊(n-1)/k⌋ + 1` objects in `n` objects distributed among k boxes. - E.g. Among 5 integers, at least 2 share the same remainder when divided by 4. ### Permutations - Ordered arrangement of distinct elements: - P(n, k) = n! / (n - k)! - E.g. Traveling to 3 cities in any order. ### Combinations - Unordered selection of elements: - C(n, k) = n! / (k! * (n - k)!) - E.g. Forming committees. ## Generalized Permutations 3 Combinations - **Allow repetition** - Permutations of elements with repetition: nᵏ for k-length strings. - Combinations with repetition: C(n + k - 1, k) ## Types of Combinations - **Repetition allowed:** - Permutations: nʳ - Combinations: (n + r - 1)! / (r! * (n - 1)!) - **Repetition not allowed:** - Permutations: n! / (n - r)! - Combinations: n! / (r! * (n - r)!) # Discrete Probability ## Probability - **P(A)** = **|A| / |S|** ## Probability of Complements - **P(¬A)** = **1 - P(A)** (probability of not A) ## Union of Events - **P(AUB)** = **P(A) + P(B) - P(A∩B)** ## Conditional Probability - **P(A | B)** = **P(A ∩ B) / P(B)** ## Independence - **P(A ∩ B)** = **P(A) x P(B)** ## Bernoulli Trials - **P(x=k)** = **(n choose k)** pᵏ (1-p)⁽ⁿ⁻ᵏ⁾ ## Bayes' Theorem - **P(A | B)** = **P(B | A) x P(A) / P(B)** ## Random Variables - A random variable (r.v) is a numerical outcome of a random process. - **Discrete r.v:** Countable outcomes (eg. rolling a dice) ## Expected Value (E[x]) - The average value of a random variable over repeated trials: - **E[x]** = **Σx * P(x)** (x ∈ S) ### Linearity of Expectation - **E[ax + b]** = **a E[x] + b** ## Variance (Var[x]) - Measures the spread of a random variable around its mean: - **Var[X]** = **E[(X - μ)²]** = **E[X²] - (E[X])²** - **Standard deviation (σ):** **σ = √Var[x]** ## Normal Distribution - Probability function: **f(x) = 1 / (√(2π)σ) * e ^(-1/2 * ((x - μ) / σ)²)** ## Key Concepts - **Bayes' theorem:** Informs on probabilities given new evidence. - **Random variables:** Describe outcomes numerically over many trials. - **Expected value:** Mean outcome. - **Variance:** Spread around the mean. - **Normal distribution:** Common in natural phenomena. # Matrices ## Systems of Linear Equations - A set of linear equations with the same variables. - E.g. 2x + 3y = 5 & 4x - y = 1 ## Matrix - A rectangular array of numbers organized into rows and columns. - E.g. [1 2 3, 4 5 6] - A matrix with m rows and n columns is an m x n matrix. - **Entries:** Each value in the matrix. Entry's position is specified by its row and column. ## Augmented Matrix - Representing a system of linear equations. Can be represented by one augmented matrix, which includes only the coefficients of the variables. - E.g. - 2x + 3y = 5 - 4x - y = 1 - Augmented matrix = \[3 5, 2 4, -1] ## Algebra of Matrices - **Operations:** - **Addition/Subtraction:** Only for matrices with the same dimensions. - **Scalar multiplication:** Multiply every entry of a matrix by a scalar. - E.g. 2 x \[3 4; 1 2] = \[6 8; 2 4] **Properties of Matrices:** - **Addition:** - Commutative: A + B = B + A - Associative: A + (B + C) = (A + B) + C - **Scalar Multiplication:** - Distributive: c(A + B) = cA + cB - Associative: (cd)A = c(dA) - **Matrix Multiplication:** - Non-commutative: AB ≠ BA - Associative: (AB)C = A(BC) - Distributive: A(B + C) = AB + AC ## Inverse of a Matrix - If a matrix A has an inverse matrix A⁻¹, then: - A x A⁻¹ = A⁻¹ x A = I (This is similar to a reciprocal of a number: a x a⁻¹ = 1) **Conditions for Inverse:** - Only square matrices (same number of rows & columns) - A matrix has an inverse if det(A) ≠ 0 & A⁻¹ = \[d -b; -c a] / (ad - bc) ## Determinant - The determinant of a 2x2 matrix: - det(A) = ad - bc ### Determinant of a 3x3 Matrix - A = \[a b c; d e f; g h i] - det(A) = a(ei - fh) - b(di - fq) + c(dh - eg) ## Cramer's Rule - Cramer's rule provides a way to solve a system of linear equations using determinants. - x_i = det(A_i) / det(A) - Where A_i is the matrix formed by replacing the i-th column of A with the column vector B. ## Key Concepts: - **Identity matrix:** A matrix with 1s on the diagonal & 0s elsewhere. - **Inverse matrix:** A matrix that, when multiplied with the original matrix, gives the identity matrix. - **Determinants:** Scalar values associated with a matrix that help solve systems of equations & determine whether a matrix has an inverse. ### Identity Matrix - 2x2: \[1 0; 0 1] - 3x3: \[1 0 0; 0 1 0; 0 0 1] ## Inverse of Identity Matrix - 2x2: \[1 0; 0 1] - 3x3: \[1 0 0; 0 1 0; 0 0 1]