Introduction to Discrete Mathematics

• Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous
• It deals with objects that can have distinct, separated values
• A branch of mathematics that deals with countable sets

Topics in Discrete Math

• Logic: The study of reasoning and argumentation, including propositional and predicate logic
• Set Theory: The study of collections of objects, including basic set operations, relations, functions, and cardinality
• Number Theory: The study of integers and their properties, including divisibility, prime numbers, congruences, and cryptography
• Combinatorics: The study of counting and arranging objects, including permutations, combinations, and generating functions
• Graph Theory: The study of graphs, which are mathematical structures used to model pairwise relations between objects
• Algorithm Analysis: The study of the efficiency and complexity of algorithms
• Discrete Probability: The study of probability in discrete sample spaces

Algorithm Analysis

• Algorithm analysis is the process of determining the computational complexity of algorithms
• Computational complexity refers to the amount of resources (time, space) required to execute an algorithm

Time Complexity

• Time complexity is a measure of the amount of time required for an algorithm to complete
• It is often expressed using Big O notation, which describes the upper bound of the growth rate of the algorithm's execution time as a function of the input size
• Common time complexities:
  • O(1): Constant time
  • O(log n): Logarithmic time
  • O(n): Linear time
  • O(n log n): Linearithmic time
  • O(n^2): Quadratic time
  • O(2^n): Exponential time
  • O(n!): Factorial time
• Big O notation focuses on the dominant term and ignores constant factors and lower-order terms

Space Complexity

• Space complexity is a measure of the amount of memory space required for an algorithm to complete
• It is also often expressed using Big O notation

Techniques for Algorithm Analysis

• Iterative algorithms: Analyze loop structures to determine how the number of iterations depends on the input size
• Recursive algorithms: Use recurrence relations to describe the algorithm's time or space complexity
• Amortized analysis: Determines the average time or space complexity per operation over a sequence of operations

Number Theory

• Number theory is a branch of mathematics that studies integers and their properties

Divisibility

• An integer 'a' is divisible by an integer 'b' if there exists an integer 'k' such that a = bk
• 'b' is a divisor or factor of 'a', denoted as b | a

Prime Numbers

• A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself
• Examples: 2, 3, 5, 7, 11, 13, etc.
• The fundamental theorem of arithmetic states that every integer greater than 1 can be uniquely represented as a product of prime numbers, up to the order of the factors

Greatest Common Divisor (GCD)

• The greatest common divisor (GCD) of two or more integers is the largest positive integer that divides all of the integers
• Euclidean algorithm: An efficient method for computing the GCD of two integers
  • gcd(a, b) = gcd(b, a mod b) until b = 0
  • When b = 0, gcd(a, 0) = a

Least Common Multiple (LCM)

• The least common multiple (LCM) of two or more integers is the smallest positive integer that is divisible by all of the integers
• Relationship between GCD and LCM: lcm(a, b) = |a * b| / gcd(a, b)

Modular Arithmetic

• Modular arithmetic is a system of arithmetic for integers where numbers "wrap around" upon reaching a certain value, called the modulus
• If a and b are integers, a is congruent to b modulo m (written as a ≡ b (mod m)) if m divides a - b
• Properties of congruence:
  • If a ≡ b (mod m) and c ≡ d (mod m), then a + c ≡ b + d (mod m) and a * c ≡ b * d (mod m)

Applications of Number Theory

• Cryptography: Number theory is the foundation for many cryptographic algorithms
• RSA (Rivest–Shamir–Adleman): A widely used public-key cryptosystem based on the difficulty of factoring large integers
• Primality testing: Determining whether a given number is prime
• Error correction codes: Using number theory to design codes that can detect and correct errors in data transmission