Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

Discrete Mathematics
Index:

Set Theory
Definition of a set
Set notation and operations (union, intersection, etc
...


The union of A and B, denoted by A U B, is the set of all elements that belong to A or B
...

The intersection of A and B, denoted by A ∩ B, is the set of all elements that belong to both A and B
...

The difference of A and B, denoted by A - B, is the set of all elements that belong to A but not to B
...


Example of Propositional Logic:
Consider the propositional logic statement "p ∧ q"
...


Example of Combinatorics:
Consider a group of 6 people, and suppose we want to know how many ways there are to select a
committee of 3 people from this group
...

In this case, the number of combinations is C(6, 3) = 6!/(3!3!) = 20
...

Graph Theory
Definition of a graph
Types of graphs (undirected, directed, weighted)
Graph traversal algorithms (depth-first search, breadth-first search)
Boolean Algebra
Definition of a Boolean algebra

Basic Boolean algebra operations (AND, OR, NOT)
Boolean functions and their truth tables
Number Theory
Definition of a prime number
The Euclidean algorithm for finding the greatest common divisor (GCD) of two numbers
The Fundamental Theorem of Arithmetic
Example of Graph Theory:

Consider the following undirected graph:

A -- B
|\ |
|\|
C -- D

This graph has 4 vertices (A, B, C, D) and 4 edges (AB, AC, AD, BD)
...
g
...
One possible traversal of this graph using depth-first search is: A, C, D,
B
...
g
...
One possible traversal of this graph using breadth-first
search is: A, B, C, D
...


The truth table for this function is:

x

y

z

f(x, y, z)

0

0

0

0

0

0

1

1

0

1

0

0

0

1

1

0

1

0

0

0

1

0

1

0

1

1

0

1

1

1

1

0

This function is true when either x'y or y'z is true (i
...
when either x is false and y is true, or y is false and
z is true)
...

To find the GCD of two numbers using the Euclidean algorithm, we can perform the following steps:
Divide the larger number by the smaller number and get the remainder
...

If the remainder is not 0, divide the smaller number by the remainder and repeat the process until the
remainder is 0
...

The Fundamental Theorem of Arithmetic states thatevery positive integer can be written as a unique
product of prime numbers
...

This theorem has many important consequences, such as the fact that the GCD of two numbers can be
found by finding the common prime factors of the numbers and the LCM (least common multiple) can
be found by multiplying the prime factors of the numbers together
...

To find the LCM of 60 and 48, we can multiply the prime factors of the numbers together:
LCM of 60 and 48: 2 x 2 x 2 x 2 x 3 x 5 = 120
...
g
...
g
...
Therefore, the general solution of the recurrence relation is:
a(n) = c1 x 2^n + c2 x 1^n
To find the particular solution that satisfies the initial conditions a(0) = 2 and a(1) = 7, we can plug
these values into the general solution:
a(0) = 2 = c1 x 2^0 + c2 x 1^0
a(1) = 7 = c1 x 2^1 + c2 x 1^1
Solving these simultaneous equations gives us c1 = -3 and c2 = 5
...

The identity matrix is a square matrix with 1s on the diagonal and 0s everywhere else
...

The determinant of a 2x2 matrix is given by:
det(A) = a x d - b x c
where a, b, c, and d are the elements of the matrix:
A = [a b]

[c d]
The adjugate of a 2x2 matrix is given by:
adj(A) = [d -b]
[-c a]
For example, let A = [2 3]
[1 2]
The determinant of A is: det(A) = 2 x 2 - 3 x 1 = 1
The adjugate of A is: adj(A) = [2 -3]
[-1 2]
Therefore, the inverse of A is: A^(-1) = (1/det(A)) x adj(A) = (1/1) x [2 -3] x [-1x [2] = [-2 1]

Systems of linear equations can be represented in matrix form as Ax = b, where A is the coefficient
matrix, x is the variable matrix, and b is the constant matrix
...

Find the inverse of the coefficient matrix (A^(-1))
...

Simplify to get the solution for the variables (x = A^(-1)b)
...

Example of Combinatorial Game Theory:
Nim is a combinatorial game in which players take turns removing objects from one or more piles
...

In Hackenbush, players take turns removing edges from a graph
...

To win at Nim, players can use the strategy of trying to leave their opponent with a position that is a
"Nim sum" of the remaining piles
...

To win at Hackenbush, players can use the strategy of trying to reduce the game to a "simple" position,
in which all the vertices are either red or blue, and the red vertices form a connected component (i
...
it
is possible to reach any red vertex from any other red vertex by following the edges)
...

Finite State Machines
Definition of a finite state machine
Examples of finite state machines (e
...
automata, computers)
Designing finite state machines
Boolean Functions and Circuit Design
Definition of a Boolean function
Minimization of Boolean functions using Karnaugh maps
Design of Boolean circuits using gates (AND, OR, NOT, NAND, NOR, XOR)
Error-Correcting Codes
Definition of an error-correcting code
Examples of error-correcting codes (e
...
Hamming codes, Reed-Solomon codes)
Decoding and correcting errors in coded messages

Example of Finite State Machines:

A finite state machine is a mathematical model of computation that consists of a finite number of states,
transitions between states, and input/output symbols
...

One example of a finite state machine is a vending machine, which has a finite number of states (e
...

idle, processing payment, dispensing product) and transitions between states (e
...
accepting payment,
dispensing product, returning change)
...
e
...

Karnaugh maps can be used to minimize Boolean functions by grouping together terms that can be
simplified
...

We can use a Karnaugh map to simplify this function:
x y z f(x, y, z)
--|---|---|---------0000
0010
0100
0111
1000
1011
1101
1111

The simplified form of the function is: f(x, y, z) = xy' + x'z + yz
Example of Error-Correcting Codes:

An error-correcting code is a type of code that is designed to detect and correct errors in transmitted
messages
...

Reed-Solomon codes are a type of error-correcting code that can detect and correct multiple-bit errors
in transmitted messages
...

Identify any errors in the message using the error-correcting code
...

Decode the corrected message to obtain the original message
...
g
...
g
...
g
...

Symmetric-key algorithms, also known as secret-key algorithms, use the same key for both encryption
and decryption
...

Public-key algorithms, also known as asymmetric-key algorithms, use a pair of keys for encryption and
decryption
...
Examples of public
-key algorithms include RSA and Diffie-Hellman
...

Example of Graph Algorithms:
A graph algorithm is an algorithm that takes in a graph as input and performs some operation on the
graph
...
One example of the shortest path algorithm is Dijkstra's algorithm
...
One example of the minimum spanning tree
algorithm is Kruskal's algorithm
...

Example of Algorithmic Complexity:
Algorithmic complexity is the study of how the resources (e
...
time, space) required by an algorithm
grow as the input size grows
...

The complexity class NP represents the set of problems for which a solution can be verified in
polynomial time
...

To analyze the time and space complexity of an algorithm, we can use big O notation to express the
upper bound on the resource usage of the algorithm as a function of the input size
...

Set Theory
Definition of a set
Set operations (union, intersection, difference, complement)
Venn diagrams and set notation
Applications of set theory (e
...
probability, counting)
Logic and Proofs
Definition of propositional logic
Formal proof techniques (e
...
direct proof, proof by contradiction, induction)
Applications of logic and proofs (e
...
problem solving, software verification)
Combinatorics
Definition of combinatorics
Counting techniques (permutations, combinations, pigeonhole principle)
Applications of combinatorics (e
...
combinatorial games, scheduling, data compression)
Example of Set Theory:

A set is a collection of objects (called elements or members) that are considered as a whole
...

Set operations are used to combine or modify sets
...
The union of A
and B is denoted by A U B
...
The
intersection of A and B is denoted by A intersect B
...
The
difference of A and B is denoted by A - B
...
The complement of A
is denoted by A'
...
For example, the Venn diagram
for the union of two sets A and B is:
ABAUB
|
|

Set theory has many applications, including probability and counting
...

Formal proof techniques are used to rigorously prove the validity of statements in propositional logic
...

Proof by contradiction: A proof by contradiction starts by assuming that the negation of the conclusion
is true and shows that this leads to a contradiction with the given premises
...
It involves proving the base case (usually n = 1) and the induction step (assuming
the statement is true for n and showing that it is also true for n + 1)
...

Example of Combinatorics:
Combinatorics is the study of finite collections of objects, often with an eye towards counting the
number of objects in the collection
...
Some common counting techniques are:
Permutations: A permutation is an arrangement of objects in a specific order
...


Combinations: A combination is a selection of objects without regard to order
...

Pigeonhole principle: The pigeonhole principle states that if n items are placed into m containers, with n
> m, then at least one container must contain more than one item
...

Generating Functions
Definition of a generating function
Examples of generating functions (e
...
generating functions for sequences, for recurrence relations)
Manipulating generating functions (e
...
addition, multiplication, differentiation)
Game Theory
Definition of game theory
Examples of game-theoretic situations (e
...
zero-sum games, non-zero-sum games)
Solution concepts in game theory (e
...
Nash equilibrium, dominant strategy)
Combinatorial Optimization
Definition of combinatorial optimization
Examples of combinatorial optimization problems (e
...
traveling salesman problem, knapsack problem)
Algorithms for solving combinatorial optimization problems (e
...
dynamic programming, branch and
bound)
Example of Generating Functions:
A generating function is a mathematical expression that encodes the information of a sequence of
numbers
...

There are two types of generating functions: ordinary generating functions (OGFs) and exponential
generating functions (EGFs)
...


An EGF for a sequence {a(n)} is a power series of the form:
A(e^x) = a(0) + a(1)x + a(2)x^2/2! + a(3)x^3/3! +
...

For example, consider the following two OGFs:
A(x) = 1 + x + x^2 + x^3 + x^4 +
...

We can add these two OGFs together to get:
C(x) = A(x) + B(x) = 2 + 3x + 5x^2 + 7x^3 +
...

And we can differentiate A(x) to get:
E(x) = A'(x) = 1 + 2x + 3x^2 + 4x^3 +
...
It involves modeling situations in which multiple
players make decisions that interact with each other
...

In a zero-sum game, one player's gain is equal to the other player's loss
...

In a non-zero-sum game, the total gain or loss of the players is not fixed
...

Solution concepts in game theory are used to predict the outcomes of games
...
Another example is the dominant strategy, which
is a strategy that is always the best choice for a player regardless of the strategies of the other players
...

The traveling salesman problem is a combinatorial optimization problem that involves finding the
shortest possible route that visits a given set of cities and returns to the starting city
...

Dynamic programming and branch and bound are two algorithms that can be used to solve
combinatorial optimization problems
...

Recursion
Definition of recursion
Examples of recursive algorithms (e
...
factorial, Fibonacci sequence)
Properties of recursive algorithms (e
...
time complexity, space complexity)
Number Theory
Definition of number theory
Examples of number-theoretic concepts (e
...
prime numbers, modular arithmetic)
Applications of number theory (e
...
cryptography, Diophantine equations)
Matrix Algebra
Definition of a matrix
Matrix operations (addition, multiplication)
Applications of matrix algebra (e
...
solving systems of linear equations, image processing)
Example of Recursion:

Recursion is a method of defining a function in terms of itself
...

An example of a recursive algorithm is the factorial function, which is defined as follows:
factorial(n) = 1 if n = 0

= n * factorial(n-1) if n > 0
The Fibonacci sequence is another example of a recursive algorithm:
fibonacci(n) = 1 if n = 1 or n = 2
= fibonacci(n-1) + fibonacci(n-2) if n > 2
The time complexity of a recursive algorithm is the number of function calls made as a function of the
input size
...

Example of Number Theory:
Number theory is the branch of mathematics that deals with the properties of integers
...
The first few prime numbers are
2, 3, 5, 7, 11,
...
For example, in the modular arithmetic system modulo 5, the numbers 0, 1, 2, 3, 4 are
considered equivalent to 0, 1, 2, 3, 4, respectively
...

Example of Matrix Algebra:
A matrix is a rectangular array of numbers (called elements or entries)
...

Matrix operations are used to manipulate matrices
...
For example, given the
following matrices:
A = [1 2]
[3 4]
B = [5 6]
[7 8]
Wecan add these two matrices together to get:
C = A + B = [6 8]
[10 12]

Multiplication: Matrices can be multiplied if the number of columns in the first matrix is equal to the
number of rows in the second matrix
...

Boolean Algebra
Definition of Boolean algebra
Boolean operations (AND, OR, NOT)
Applications of Boolean algebra (e
...
digital logic, computer science)
Combinatorial Game Theory
Definition of combinatorial game theory
Examples of combinatorial games (e
...
Nim, chess)
Solution concepts in combinatorial game theory (e
...
nim-value, grundy number)
Finite State Machines
Definition of a finite state machine
Examples of finite state machines (e
...
vending machines, traffic lights)
Applications of finite state machines (e
...
automata theory, computer science)
Example of Boolean Algebra:
Boolean algebra is a branch of algebra that deals with the manipulation of logical values (true and false)
...

Boolean algebra has three basic operations: AND, OR, and NOT
...
) and is true only if both operands are true
...

NOT: The NOT operation is denoted by a tilde (~) and negates the value of its operand
...

Example of Combinatorial Game Theory:
Combinatorial game theory is a branch of mathematics that deals with the analysis of two-player games
...
The player who
takes the last object loses
...
It is a strategic board game played by two players on
a 8x8 grid
...

Solution concepts in combinatorial game theory are used to predict the outcomes of games
...
Another example is the grundy number, which is a
measure of the relative value of a position in a game that satisfies certain mathematical properties
(called the Sprague-Grundy theorem)
...

Example of Finite State Machines:
A finite state machine (FSM) is a mathematical model of computation that defines a state machine in
terms of a finite set of states, a set of input symbols, and a set of transitions between states
...
A vending machine has a finite number of
states (e
...
idle, waiting for payment, dispensing product), and transitions between these states based
on input symbols (e
...
inserting coins, selecting a product)
...
A traffic light has three states (red, yellow,
green) and transitions between these states based on a fixed schedule
...

Graph Theory
Definition of a graph
Examples of graphs (e
...
directed graphs, undirected graphs, weighted graphs)
Applications of graph theory (e
...
network analysis, computer science)

Combinatorial Designs
Definition of a combinatorial design
Examples of combinatorial designs (e
...
block designs, Steiner systems)
Applications of combinatorial designs (e
...
experimental design, error-correcting codes)
Group Theory
Definition of a group
Examples of groups (e
...
permutation groups, matrix groups)
Applications of group theory (e
...
symmetry, abstract algebra)
Example of Graph Theory:

A graph is a mathematical structure that represents a set of objects (called vertices or nodes) and the
relationships between them (called edges)
...
In a directed graph, the edges
have a direction (e
...
from vertex A to vertex B)
...
g
...

Graphs can also be weighted, meaning that each edge has a numerical value associated with it (called a
weight)
...

Example of Combinatorial Designs:
A combinatorial design is a collection of subsets (called blocks) of a larger set, with the property that
every two elements of the larger set are contained in exactly one block
...
Steiner systems
are a type of combinatorial design in which the blocks are of different sizes
...

Example of Group Theory:
A group is a mathematical structure that consists of a set of elements (called the group's elements) and
a binary operation (called the group operation) that combines two elements to form a third element
...

Permutation groups are groups that consist of permutations (rearrangements of a set of elements)
...

Group theory has many applications, including symmetry and abstract algebra
...
g
...
g
...
g
...
g
...
Sets are denoted by capital letters (e
...
A,
B, C) and the elements of a set are listed inside curly braces (e
...
{1, 2, 3})
...
The union of sets A and
B is denoted by A U B
...
The
intersection of sets A and B is denoted by A intersect B
...
The difference of set A and set B is denoted by A - B
...


Example of Probability Theory:
Probability is a measure of the likelihood of an event occurring
...

There are several axioms and rules that govern probability:
Probability axioms: The probability of an event occurring is a non-negative number and the probability
of any event occurring is 1
...

Multiplication rule: The probability of two events occurring simultaneously is the product of their
probabilities
...

Example of Information Theory:
Information theory is the study of the representation, communication, and processing of information
...
It is often used
to quantify the amount of information contained in a message or signal
...

Information theory has many applications, including communication systems and data storage
...
g
...
g
...
g
...
g
...
g
...

Some examples of ordered sets include:
Real numbers: The real numbers are ordered by the less-than relation
...
e
...

Order theory has many applications, including sorting algorithms and data structures
...
It deals with the question of which
functions can be calculated by an algorithm
...
A function is non-computable
if there does not exist an algorithm that can calculate it
...

The Fibonacci function: Given an integer, this function returns the nth term of the Fibonacci sequence
...

Example of Topology:
Topology is the study of the properties of a space that are preserved under continuous deformations
(stretching, shrinking, and bending, but not tearing or gluing)
...

Compactness: A set is compact if it is "small" in some sense (e
...
it is finite or it can be covered by a
finite number of open sets)
...


Game Theory
Definition of game theory
Examples of game-theoretic concepts (e
...
Nash equilibrium, prisoners' dilemma)
Applications of game theory (e
...
economics, politics)
Formal Languages
Definition of a formal language
Examples of formal languages (e
...
regular languages, context-free languages)
Applications of formal languages (e
...
compiler design, artificial intelligence)
Automata Theory
Definition of an automaton
Examples of automata (e
...
finite automata, pushdown automata)
Applications of automata theory (e
...
compiler design, artificial intelligence)
Example of Game Theory:
Game theory is the study of strategic decision making
...
e
...

Some concepts in game theory include:
Nash equilibrium: A Nash equilibrium is a situation in which no player has an incentive to change their
behavior, given the behavior of the other players
...
It involves two players who must decide whether to cooperate or defect
...

Example of Formal Languages:
A formal language is a set of strings (sequences of symbols) that can be generated by a particular set of
rules
...
They are the
most basic type of formal language
...
They are more powerful than regular languages and can describe the structure of
context-free grammars
...

Example of Automata Theory:
An automaton is a machine that follows a predetermined set of rules to perform a task
...
They
consist of a finite set of states and a set of transitions between states
...
They have a finite set of states, a set of transitions between states, and a stack
for storing symbols
...

Combinatorics
Definition of combinatorics
Examples of combinatorial concepts (e
...
permutations, combinations)
Applications of combinatorics (e
...
counting, probability)
Number Theory
Definition of number theory
Examples of number-theoretic concepts (e
...
prime numbers, divisibility)
Applications of number theory (e
...
cryptography, algebra)
Calculus
Definition of calculus
Examples of calculus concepts (e
...
derivatives, integrals)
Applications of calculus (e
...
optimization, physics)
Example of Combinatorics:

Combinatorics is the branch of mathematics that deals with the study of combinations and
arrangements of objects
...

Combinations: A combination is a selection of objects from a larger set, without regard to order
...

Example of Number Theory:

Number theory is the branch of mathematics that deals with the properties of integers (positive and
negative whole numbers)
...

Divisibility: An integer is divisible by another integer if it can be evenly divided by it with no remainder
...

Example of Calculus:
Calculus is the branch of mathematics that deals with the study of change and motion
...

Some examples of calculus concepts include:
Derivatives: The derivative of a function is a measure of how the function is changing at a given point
...

Calculus has many applications, including optimization and physics
...
e
...
It has many applications in computer science and
other fields, and includes a wide range of topics such as combinatorics, graph theory, automata theory,
and more
...
Understanding these concepts is important for understanding the foundations of
computer science and for solving many real-world problems

---