# Discrete Mathematics Note Chapter 3

# Algorithm

## Algorithms

### Definition

An **algorithm** is a finite set of precise instructions for performing a computation or for solving a problem.

### Pseudo Code

Instructions in generic language similar to real computer languages.

1 | procedure max(a_1, a_2, ..., a_n: integers) |

### Common properties of algorithms

- Input
- Output
- Definiteness -- each step must be defined precisely
- Correctness -- outputs are correct
- Finiteness -- produce the desired output in finite steps
- Effectiveness -- each step must be executed exactly and in a finite amount of time
- Generality -- applicable for all problems of the desired form

### Searching Algorithm

#### Linear Search / Sequential Search

1 | procedure linear_search(x:integer, a_1, a_2, a_3, ..., a_n: integers) |

#### Binary Search

1 | procedure binary_search(x:integer, a_1, a_2, a_3, ..., a_n: integers) |

### Other Algorithms

#### Sorting

Sorting algorithms consist of bubble sort, insertion sort, selection sort, merge sort, quick sort and so on.

#### Greedy Algorithm

To solve problems like maximizing or minimizing some parameters.

Its strategy is to find partial best solutions, and construct the global best solution from them.

Pseudocode for change-making algorithm:

1 | procedure make_change(c_1, c_2, c_3, ..., c_r: integers, n: integer) |

## The Growth of Functions

### Asymptotic Analysis

The number of operations used by the algorithm as the input size approaches infinity is called **asymptotic running time**.

Asymptotic analysis is to roughly measure the running time of algorithms in a relative rate of growth of execution.

### Big-O Notation

\(f(x)\) is \(O(g(x))\) if \(\exist n_0, C, \forall n> n_0, f(n) \le Cg(n)\).

### Big-Omega Notation

\(f(x)\) is \(\Omega(g(x))\) if \(\exist n_0, C, \forall n> n_0, f(n) \ge Cg(n)\).

### Big-Theta Notation

\(f(x)\) is \(\Theta(g(x))\) if it's both \(O(g(x))\) and \(\Omega(g(x))\).

### Notations and Terms

- \(O(1)\) -- Constant
- \(O(\log N)\) -- logarithmic
- \(O(N)\) -- linear
- \(O(N \log N)\) -- \(N\) log \(N\)
- \(O(N^b)\) -- polynomial
- \(O(b^N) (b > 1)\) -- exponential
- \(O(n!)\) -- factorial

### Simple Rules

- \(O( (f_1 + f_2)(N) ) = O( \max(f_1(N), f_2(N)) )\).
- \(O( (f_1f_2)(N) ) = O( f_1(N) \cdot f_2(N) )\).

## Complexity of Algorithms

### Computational Complexity

**Space Complexity**: Approximate amount of memory required to solve a problem with size \(n\).**Time Complexity**: Approximate amount of instructions required to solve a problem with size \(n\).- Instruction (basic operations):
- searching -- comparisons
- sorting -- list component comparisons
- numerical operation -- floating point operations -- multiplications / division / addition / substraction

- Instruction (basic operations):

### Examples

- Finding the Maximum Element in a Finite Sequence

1 | procedure max(a_1, a_2, ..., a_n: integers) |

Solution:

Measure the number of comparisons.

There are exactly \(2(n - 1) + 1 = 2n - 1\) comparisons.

So the time complexity is \(\Theta(n)\).

- The Linear Search Algorithm

1 | procedure linear_search(x: integer; a_1, a_2, ..., a_n: integers) |

Solution:

Measure the number of comparisons.

If \(x = a_j\), \(2j + 1\) comparisons are used.

If the element is not in the list, there would be \(2n + 2\) comparisons.

So its time complexity is \(O(n)\).

### Different Types of Analysis

- Worst-case analysis
- Maximum number of operations
- Usually the most complicated cases

- Best-case analysis
- Average-case analysis
- Average number of operations assuming an input probability distribution

### Unsolvable or Intractable

Halting problem: given a program and an input to the program, whether the program will eventually halt when run.

Problems that can be shown that no algorithm exists for solving them are called **unsolvable**.

Problems that cannot be solved using an algorithm with polynomial worst-case time complexity are called **intractable**.

### P and NP

**Class P**: problems with polynomial time complexity solution.

**Class NP**: problems without polynomial solution, but its answer can be checked in polynomial time.

**Class NP-Hard**: there's a NP problem can be transfer into this problem in polynomial time.

**Class NP-Complete**: problems both NP and NP-hard.