1. Introduction to Discrete Mathematics

Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous. Unlike calculus, which deals with continuous change, discrete mathematics deals with distinct, separate values.

Discrete mathematics forms the foundation for computer science and is essential for understanding programming, data structures, algorithm design, and cryptography.

2. Set Theory

Set theory is the mathematical theory of collections of objects called sets. It forms the foundation for most of modern mathematics.

2.1 Basic Definitions

A set is a well-defined collection of distinct objects. The objects in a set are called elements or members of the set.

2.2 Types of Sets

• Empty Set (∅): A set with no elements
• Singleton Set: A set with exactly one element
• Finite Set: A set with a finite number of elements
• Infinite Set: A set with an infinite number of elements
• Universal Set (U): Set containing all elements under consideration

2.3 Set Operations

2.4 Set Identities

2.5 Power Sets and Cartesian Products

• Power Set: P(A) is the set of all subsets of A
• Cartesian Product: A × B = {(a, b) | a ∈ A and b ∈ B}

3. Logic and Proof Techniques

Logic is the study of principles of valid reasoning and inference. It provides the foundation for understanding mathematical proofs.

3.1 Propositional Logic

A proposition is a declarative statement that is either true or false, but not both.

3.2 Truth Tables

Truth tables show the logical outcome of statements based on the truth values of their components.

3.3 Logical Equivalences

3.4 Predicates and Quantifiers

A predicate is a statement that contains variables and becomes a proposition when values are assigned to the variables.

3.5 Proof Techniques

• Direct Proof: Assume the hypothesis and directly derive the conclusion
• Proof by Contraposition: Prove ¬q → ¬p instead of p → q
• Proof by Contradiction: Assume the statement is false and derive a contradiction
• Mathematical Induction: Prove for base case and then show that if true for k, it's true for k+1

4. Number Theory

Number theory is the study of integers and their properties, particularly focusing on divisibility, prime numbers, and modular arithmetic.

4.1 Divisibility and Division Algorithm

An integer a divides another integer b (denoted a | b) if there exists an integer c such that b = ac.

4.2 Greatest Common Divisor (GCD) and Least Common Multiple (LCM)

The GCD of two integers a and b is the largest integer that divides both a and b.

The LCM of two integers a and b is the smallest positive integer that is divisible by both a and b.

4.3 Euclidean Algorithm

The Euclidean Algorithm is an efficient method for computing the GCD of two integers.

4.4 Prime Numbers and Fundamental Theorem of Arithmetic

A prime number is a positive integer greater than 1 that has no positive integer divisors other than 1 and itself.

4.5 Modular Arithmetic

Modular arithmetic is arithmetic for integers where values "wrap around" after reaching a certain value (the modulus).

5. Combinatorics

Combinatorics is the study of counting, arrangement, and combination of objects.

5.1 Counting Principles

5.2 Permutations

A permutation is an ordered arrangement of objects. The number of permutations of n distinct objects is:

5.3 Combinations

A combination is a selection of objects without regard to order. The number of ways to select r objects from a set of n distinct objects is:

5.4 Binomial Theorem

5.5 Pigeonhole Principle

6. Graph Theory

Graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects.

6.1 Basic Definitions

A graph G = (V, E) consists of a set V of vertices and a set E of edges, where each edge connects a pair of vertices.

6.2 Graph Representations

Graphs can be represented using adjacency matrices, adjacency lists, or edge lists.

6.3 Graph Traversals

There are two main ways to traverse a graph:

• Breadth-First Search (BFS): Explores all neighbors at the current depth before moving to nodes at the next depth level
• Depth-First Search (DFS): Explores as far as possible along each branch before backtracking

6.4 Euler and Hamilton Paths/Circuits

An Euler path is a path that visits every edge exactly once. If it starts and ends at the same vertex, it's an Euler circuit.

A Hamilton path is a path that visits every vertex exactly once. If it starts and ends at the same vertex, it's a Hamilton circuit.

6.5 Trees

A tree is a connected, acyclic graph. A forest is a disjoint union of trees.

6.6 Planar Graphs

A graph is planar if it can be drawn in the plane without crossing edges.

7. Recurrence Relations

A recurrence relation is an equation that defines a sequence based on previous terms in the sequence.

7.1 Linear Recurrence Relations

A linear recurrence relation of order k is of the form:

7.2 Solving Linear Homogeneous Recurrence Relations

For a homogeneous linear recurrence relation (where f(n) = 0), we form the characteristic equation:

7.3 Fibonacci Numbers

The Fibonacci sequence is defined by the recurrence relation:

8. Algorithms

An algorithm is a step-by-step procedure for solving a problem or accomplishing a task.

8.1 Algorithm Analysis

The efficiency of an algorithm is typically measured in terms of its time complexity and space complexity, expressed using Big O notation.

8.2 Sorting Algorithms

Sorting algorithms arrange elements in a specific order (usually ascending or descending).

InsertionSort(A):
  for i = 1 to A.length - 1
    key = A[i]
    j = i - 1
    while j ≥ 0 and A[j] > key
      A[j+1] = A[j]
      j = j - 1
    A[j+1] = key
      

8.3 Searching Algorithms

Searching algorithms find the position of a target value within a data structure.

BinarySearch(A, target):
  low = 0
  high = A.length - 1
  
  while low ≤ high
    mid = (low + high) / 2
    if A[mid] == target
      return mid
    else if A[mid] < target
      low = mid + 1
    else
      high = mid - 1
  
  return -1  // Not found
      

8.4 Graph Algorithms

Graph algorithms solve problems related to graph structures.

Dijkstra(G, source):
  Initialize dist[source] = 0 and dist[v] = ∞ for all other vertices
  Initialize priority queue Q with all vertices
  
  while Q is not empty
    u = vertex in Q with minimum dist[u]
    Remove u from Q
    
    for each neighbor v of u
      alt = dist[u] + weight(u, v)
      if alt < dist[v]
        dist[v] = alt
        Update v's position in Q
  
  return dist
      

8.5 Greedy Algorithms

Greedy algorithms make the locally optimal choice at each step in the hope of finding a global optimum.

Kruskal(G):
  Initialize a forest T with each vertex as a separate tree
  Sort all edges of G in non-decreasing order of weight
  
  for each edge (u, v) in the sorted order
    if adding (u, v) does not create a cycle in T
      Add edge (u, v) to T
  
  return T
      

8.6 Dynamic Programming

Dynamic programming solves complex problems by breaking them down into simpler subproblems and storing the results to avoid redundant computations.

Fibonacci(n):
  Initialize F[0] = 0 and F[1] = 1
  
  for i = 2 to n
    F[i] = F[i-1] + F[i-2]
  
  return F[n]
      

9. Master Quiz

Test your knowledge of discrete mathematics with this comprehensive quiz covering all topics.