CENG 213 • Final • Discrete Computational Structures

Introduction

Proof of Formulas by Induction

Example 1

Example 2

Example 3

Example 4

Proof of Divisibility by Induction

Example 1

Example 2

Proof of Inequality by Induction

Example 1

Example 2

Induction Related to Fibonacci

Strong Induction

Introduction

Recursively Defined Functions

Example 1

Recursively Defined Sets

Example 2

Recursively Defined Strings

Example 3

Structural Induction

Example 4

Example 5

Induction for Formulas 1

Induction for Formulas 2

Induction for Formulas 3

Induction for Formulas 4

Induction Proof for Divisibility 1

Induction Proof for Divisibility 2

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

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

Introduction

Homogenous Recurrence Relations

Example 1

Example 2

Example 3

Example 4

Non Homogenous Recurrence Relations

Example5

Example 6

Creating Recurrence Relations

Example 7

Example 8

Example 9

Definition of Relation

Example 1

Example 2

Reflexive Relations

Example 3

Example 4

Symmetric Relations

Antisymmetric Relations

Example 5

Transitive Relations

Example 6

Properties of Relations

Example 7

Example 8

Composition of Relations

Equivalence Relation

Example 9

Example 10

Recurrence Relations 1

Recurrence Relations 2

Recurrence Relations 3

Recurrence Relations 4

Recurrence Relations 5

Recurrence Relations 6

Recurrence Relations 7

Recurrence Relations 8

Recurrence Relations 9

Properties of Relation

Properties of Relation

Equivalence Relation 1

Equivalence Relation 2

Equivalence Relation 3

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

Introduction

Rooted Tree

Terminology for Rooted Trees

Full m-ary Trees

Some Formulas

Adjacency Matrices

Incidence Matrices

Bipartite Graphs & Euler Circuits

Euler Path, Induced Subgraph & Incidence Matrix

Isomorphism 1

Isomorphism 2

Isomorphism 3

Isomorphism 4

Isomorphism 5