CMPE 201 • Midterm II + Final • Discrete Mathematics for Engineering

What is an algorithm?

Algorithm and Pseudocode 1

Algorithm and Pseudocode 2

Exam Like Question 1

Linear Search Algorithm

Binary Search Algorithm

Bubble Sort Algorithm

Insertion Sort Algorithm

Insertion Sort Algorithm - Code

Big-O Notation

Example 1

Example 2

Example 3

Example 4

Sum Property of Big-O Notation

Multiplication Property of Big-O Notation

Example 1

Example 2

Big-Omega Notation

Big-Theta Notation

Example 1

Example 2

Definition of Divisibility

Example 1

Example 2

Division Algorithm

Definition of Modular Arithmetic

Example 1

Properties of Modular Arithmetic

Example 1

Example 2

Prime Numbers

Example 1

Example 2

GCD Greatest Common Divisor

LCM Least Commun Multiple

Example 1

Euclidian Algorithm

Example 1

Bezout Identity

Example 1

Introduction

Proof of Formulas by Induction

Example 1

Example 2

Exam-like Question 1

Exam-like Question 2

Proof of Divisibility by Induction

Example 1

Example 2

Exam-like Question 1

Exam-like Question 2

Proof of Inequality by Induction

Example 1

Example 2

Example 3

Exam-like Question 1

Exam-like Question 2

Exam-like Question 3

Induction Related to Fibonacci

Exam-like Question 1

Strong Induction

Example 1

Introduction

Recursively Defined Functions

Example 1

Recursively Defined Sets

Example 2

Recursively Defined Strings

Example 3

Structural Induction

Example 4

Example 5

Growth of Functions 1

Growth of Functions 2

Growth of Functions 3

Growth of Functions 4

Algorithms 1

Algorithms 2

Algorithms 3

Number Theory 1

Number Theory 2

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 1

Induction for Inequalities 2

Counting 1

Counting 2

Counting 3

Counting 4

Counting 5

Counting 6

Counting 7

Pigeonhole Principle 1

Pigeonhole Principle 2

Pigeonhole Principle 3

Basic Principles of Counting

Counting Examples

Permutations

Permutations Example

Groups and Circular Permutation Example

Identical Objects Example

Combination

n choose r

Committee Example

Ball Example

Pigeonhole Principle

Pigeonhole Principle Example 1

Pigeonhole Principle Example 2

Pigeonhole Principle Example 3

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

Counting 1

Counting 2

Counting 3

Counting 4

Counting 5

Counting 6

Counting 7

Pigeonhole Principle 1

Pigeonhole Principle 2

Pigeonhole Principle 3

Pigeonhole Principle 4

Pigeonhole Principle 5

Recurrence Relations 1

Recurrence Relations 2

Recurrence Relations 3

Recurrence Relations 4

Recurrence Relations 5

Recurrence Relations 6

Recurrence Relations 7

Recurrence Relations 8

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

Example 10

Adjacency Matrices

Incidence Matrices

Bipartite Graphs & Euler Circuits

Euler Path, Induced Subgraph & Incidence Matrix

Isomorphism 1

Isomorphism 2

Isomorphism 3

Isomorphism 4

Isomorphism 5

What is a network?

Shortest Path Problems

Dijkstra's Algorithm

Djikstra's Algorithm Example 1

Djikstra's Algorithm Example 2

Shortest Path Problem Example 1

Shortest Path Problem Example 2

Problem Definition

Solving Problem

Enumeration

Example 1

Nearest Neighbor Algorithm

Example 2

Example 3

Finite State Machines with Output

Example 1

Example 2

Finite State Machines with NO Output

Example 3

Example 4

Example 5

Turing Machine

Example 6

Example 7

Djikstra's Algorithm

Shortest Path Problem 1

Shortest Path Problems 2

Shortest Path Problems 3

Shortest Path Problems True/False 1

Shortest Path Problems True/False 2

Traveling Salesperson Problem 1

Traveling Salesperson Problem 2

Traveling Salesperson Problem 3

Finite State Machines with Output

Finite State Machines with NO Output 1

Finite State Machines with NO Output 2

Turing Machine

Growth of Functions

Euclidian Algorithm & Bezout Theorem

Recursion and Induction

Pigeonhole Principle

Counting

Graph Theory - Incidence Matrix