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.

procedure max(a_1, a_2, ..., a_n: integers)
maxa := a_1
for i from 1 to n begin
    if maxa < a_i then begin
        maxa := a_i
    end
end
return maxa

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

procedure linear_search(x:integer, a_1, a_2, a_3, ..., a_n: integers)
i := 1
while i <= n and x != a_i then i := i + 1
if i <= n then location := i
else then location := n + 1
return location

Binary Search

procedure binary_search(x:integer, a_1, a_2, a_3, ..., a_n: integers)
l := 1
r := n
while l < r begin
    mid := floor((l + r) / 2)
    if x > a_mid then l := mid + 1
    else then r := mid
end
if x == a_l then location := l
else then location := n + 1
return location

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:

procedure make_change(c_1, c_2, c_3, ..., c_r: integers, n: integer)
for i from 1 to r
    d_i := 0
while(n >= c_i) begin
    d_i := d_i + 1
    n := n - c_i
end
return d

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

Examples

1. Finding the Maximum Element in a Finite Sequence

procedure max(a_1, a_2, ..., a_n: integers)
maxa := a_1
for i from 1 to n begin
    if maxa < a_i then begin
        maxa := a_i
    end
end
return maxa

Solution:

Measure the number of comparisons.

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

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

2. The Linear Search Algorithm

procedure linear_search(x: integer; a_1, a_2, ..., a_n: integers)
i := 1
while i <= n and x != a_i begin
    i := i + 1
end
if i <= n then location := i
else location := 0
return location

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.