CENG 115 • Final • Discrete Structures

Definition of Divisibility

Example 1

Example 2

Division Algorithm

Definition of Modular Arithmetic

Example 1

Properties of Modular Arithmetic

Example 1

Example 2

GCD Greatest Common Divisor

LCM Least Commun Multiple

Euclidian Algorithm

Example 1

Bézout Identity

Example 1

Example 2

Example 3

Inverse of a Number in Modular Arithmetic

Fermat's Little Theorem

Solving Linear Congruences

Example 1

Example 2

Chinese Remainder Theorem

Example 1

Example 2

Ceasar Cipher

Affine Cipher

Example 1

Example 2

Example 3

Example 4

RSA Algorithm

Example 1

Example 2

Example 3

Exam-like Question 1

Exam-like Question 2

Introduction

Proof of Formulas by Induction

Example 1

Example 2

Example 3

Proof of Divisibility by Induction

Example 1

Proof of Inequality by Induction

Example 1

Induction Related to Fibonacci

Strong Induction

Introduction to Recursion

Recursively Defined Functions

Example 1

Recursively Defined Sets

Example 2

Recursively Defined Strings

Example 3

Number Theory 1

Number Theory 2

Number Theory 3

Number Theory 4

Number Theory 5

RSA Algorithm 1

RSA Algorithm 2

RSA Algorithm 3

Induction for Formulas 1

Induction for Formulas 2

Induction for Formulas 3

Induction for Formulas 4

Induction Proof for Divisibility 1

Induction for Inequalities

Induction with Fibonacci

Recursion and Induction

Recursive Algorithm

Basic Principles of Counting

Counting Examples

Permutations

Permutations Example

Groups and Circular Permutation Example

Identical Objects Example 1

Identical Objects Example 2

Identical Objects Example 3

Combination

n choose r

Committee Example 1

Committee Example 2

Ball Example 1

Ball Example 2

Principle Inclusion-Exclusion

Example

Distributing Objects into Boxes 1

Distributing Objects into Boxes 2

Example 1

Example 2

Example 3

Pigeonhole Principle

Example 1

Example 2

Example 3

Recurrence Relations

Homogenous Recurrence Relations

Example 1

Example 2

Non Homogenous Recurrence Relations

Example 3

Example 4

Creating Recurrence Relations

Example 5

Example 6

Definition of Relation

Example 1

Example 2

Example 3

Reflexive Relations

Example 4

Symmetric Relations

Antisymmetric Relations

Example 5

Transitive Relations

Example 6

Properties of Relations

Example 7

Example 8

Composition of Relations

Example 9

Example 10

Combining Relations

Inverse and Complementary of a Relation

Example 11

Matrix Representation of a Relation 1

Matrix Representation of a Relation 2

Example 12

Operations on Zero - One Matrices

Example 13

Reflexive Closure

Symmetric Closure

Example 14

Transitive Closure & Connectivity Relation

Equivalence Relation

Example 15

Partially Ordered Set

Example

Example

Example

Totally Ordered Set

Example

Hasse Diagram

Example

Maximal and Minimal Elements

Greatest and Least Elements

Example

Upper and Lower Bound

Least Upper and Greatest Lower Bound

Example

Introduction

Graph Terminology

Handshaking Theorem

Example 1

Special Graphs

Example 2

Bipartite Graphs

Example 3

Example 4

Complete Bipartite Graph

Matching

Subgraph

Example 5

Subgraph Induced

Edge Contraction

Example 6

Complementary Graph

Adjacency Matrices - Undirected Graphs

Adjacency Matrices - Directed Graphs

Example 1

Example 2

Incidence Matrices

Example 3

Isomorphism of Graphs

Example 4

Example 5

Example 6

Example 7

Definition of Paths and Circuits

Connected Graphs

Euler Paths and Circuits

Example 8

Hamilton Paths and Circuits

Example 9

Counting 1

Counting 2

Counting 3

Counting 4

Counting 5

Counting 6

Principle Inclusion Exclusion 1

Principle Inclusion Exclusion 2

Distributing Objects into Boxes 1

Distributing Objects into Boxes 2

Pigeonhole Principle 1

Pigeonhole Principle 2

Pigeonhole Principle 3

Pigeonhole Principle 4

Recurrence Relations 1

Recurrence Relations 2

Recurrence Relations 3

Recurrence Relations 4

Recurrence Relations 5

Recurrence Relations 6

Properties of Relation

Properties of Relation

Equivalence Relation 1

Equivalence Relation 2

Equivalence Relation 3

Hasse Diagram

Hasse Diagram

Adjacency Matrices

Incidence Matrices

Bipartite Graphs & Euler Circuits

Euler Path, Induced Subgraph & Incidence Matrix

Isomorphism 1

Isomorphism 2

Isomorphism 3

Isomorphism 4

Isomorphism 5