MATH 250 • Midterm II + Final • Discrete Mathematics for Engineering

What is an algorithm?

Algorithm and Pseudocode 1

Algorithm and Pseudocode 2

Linear Search Algorithm

Binary Search Algorithm

Bubble Sort Algorithm

Insertion Sort Algorithm

Big-O Notation

Example 1

Example 2

Sum Property of Big-O Notation

Multiplication Property of Big-O Notation

Example 1

Example 2

Big-Omega Notation

Big-Theta Notation

Example 1

Definition of Divisibility

Example

Example

Division Algorithm

Definition of Modular Arithmetic

Example

Properties of Modular Arithmetic

Example

Example

Prime Numbers

Example

GCD Greatest Common Divisor

LCM Least Common Multiple

Example

Euclidian Algorithm

Example

Bezout Identity

Example

Example

Example

Growth of Functions

Growth of Functions

Growth of Functions

Growth of Functions

Growth of Functions

Growth of Functions

Algorithms

Algorithms

Algorithms

Algorithms

Algorithms

Algorithms

Algorithm and Complexity

Algorithm and Complexity

Algorithm and Complexity

Algorithms and Complexity

Algorithms and Complexity

Algorithms and Complexity

Algorithms and Complexity

Algorithms and Complexity

Algorithms and Complexity

Euclidian Algorithm

Euclidian Algorithm & Bezout Theorem

Euclidian Algorithm & Bezout Theorem

Euclidian Algorithm & Bezout Theorem

Euclidian Algorithm & Multiplicative Inverse

Euclidian Algorithm & Multiplicative Inverse

Introduction

Proof of Formulas by Induction

Example 1

Example 2

Proof of Divisibility by Induction

Example 1

Example 2

Proof of Inequality by Induction

Example 1

Example 2

Example 3

Induction Related to Fibonacci

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

Induction for Formulas

Induction for Formulas

Induction for Formulas

Induction for Formulas

Induction for Divisibility

Induction for Divisibility

Induction for Divisibility

Induction for Inequality

Induction for Inequality

Induction for Inequality

Induction for Fibonacci

Induction for Fibonacci

Recursion and Induction

Recursive Algorithm

Recursive Algorithm and Complexity

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

Example 5

Example 6

Creating Recurrence Relations

Example 7

Example 8

Example 9

Counting

Counting

Counting

Counting

Counting

Counting

Counting

Counting

Counting

Pigeonhole Principle

Pigeonhole Principle

Pigeonhole Principle

Pigeonhole Principle

Pigeonhole Principle

Pigeonhole Principle

Pigeonhole Principle

Recurrence Relations

Recurrence Relations

Recurrence Relations

Recurrence Relations

Recurrence Relations

Recurrence Relations

Recurrence Relations

Recurrence Relations

Recurrence Relations

Recurrence Relations

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

Handshaking Theorem

Handshaking Theorem

Handshaking Theorem

Degree Sequence

Number of Graphs

Graph Theory - Basics

Bipartite Graphs

Complete Bipartite

Adjacency Matrices

Incidence Matrices

Isomorphism

Isomorphism

Isomorphism

Isomorphism

Isomorphism

Euler Path & Circuit

Euler Path & Circuit

Euler Path, Incidence Matrix & Induced Subgraph

Euler Path, Incidence Matrix & Bipartite

Graph Theory - Proof

Graph Theory - Proof

Graph Theory - Proof

Graph Theory - Proof

Graph Theory - Proof

Graph Theory - Proof

Graph Theory - Proof

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