CSCE 121 Algorithm

« previous | Friday, December 3, 2010 | next »

Set of steps that define how a task is to be performed.

Pseudocode

Generalization of a programming language to jot down main idea of an algorithm

• Assignment (typically written :=)
• Common control structures (if-then-else, while, for, repeat)
• English phrases when convenient:
  • If we already know how to do something, or
  • we haven't figured out how to do something yet

Finding Algorithms

No automatic way

Requires:

• trial and error
• familiarity
• insight and creativity

General approaches:

reduction

find similar problem and adapt it to this problem

step-wise refinement / divide and conquer

break problem down

recursion often used to solve subproblems

Example: Search

Given a sequence of elements, is a particular element actually in the sequence?

Sequential search $O(n)$

scan sequence from beginning to end looking for desired target element:

Binary search $O({\log }_{2}n)$

check middle element of sorted sequence.

If target is smaller, it will be in first half, if larger it will be in second half.

Recurse

Which is better (faster)?

depends on hardware, but more importantly the underlying (abstract) algorithm that program implements

Asymptotic Analysis

Describe running time as $\underset{n\to \mathrm{\infty }}{\lim }f\left(n\right)$ where $n$ is input size;

Can also be described as the number of basic steps of the algorithm according to pseudocode description

All of the definitions of Big-O, Big-Ω, and Big-Θ below have something to do with existentially (∃) bound constants (generally $C$ and $n_0$) that make definition true. These constants are referred to in the discrete mathematics textbook as witnesses.

Definition of Dominance

Also referred to as asymptotic comparison

In general, we say $f$ is asymptotically less than or equal to ($\preccurlyeq$) $g$ if and only if there exists a natural number $n_0$ such that $f(n)\ge g(n)$ for all $n>n_0$

$f\preccurlyeq g⟷\mathrm{\exists }{n}_0\in \mathbb{\mathbb{N}}\mathrm{\forall }n(n\ge n_0\to f(n)\le g(n))$

Conversely, we say $g$ is asymptotically greater than or equal to ($\succcurlyeq$) $f$.

Example

Let $f(n)=5n$ and $g(n)=n^2$:

• When $n<5$, $f(n)>g(n)$
• Asymptotically, $g$ "grows faster" than $f$, so $g(n)$ ≥ $f(n)$ when $n>5$
• Given the definition above, we can say that $5n\preccurlyeq n^2$

Big O

An upper bound on a function $f$:

$f(n)\in O(n)\to f(n)\le Cn\to f(n)\preccurlyeq n$

Precise Definition: $f(n)$ is big oh of $g(n)$ if and only if there exists a constant $C$ and a natural number $n_0$ such that $|f(n)|$ ≤ $C|g(n)|$ for all $n>n_0$ $f(n)\in O(g(n))⟷\mathrm{\exists }C\in \mathbb{ℝ}\mathrm{\exists }{n}_0\in \mathbb{\mathbb{N}}\mathrm{\forall }n(n\ge n_0\to |f(n)|\le C|g(n)|)$

Common Order of Dominance

1. $O(n^n)$ exponential
2. $O(n!)$ factorial
3. $O(n^2)$ polynomial
4. $O(n\log n)$
5. $O(n)$ linear
6. $O(\sqrt{n})$
7. $O(\log n)$ logarithmic
8. $O(1)$ constant

Big Ω

A lower bound on a function $f$ :

$f(n)\in \mathrm{\Omega }(n)\to f(n)\ge Cn\to f(n)\succcurlyeq n$

Precise Definition: $f(n)$ is big omega of $g(n)$ if and only if there exists a constant $C$ and a natural number $n_0$ such that $|f(n)|$ ≥ $C|g(n)|$ for all $n>n_0$ $f(n)\in \mathrm{\Omega }(g(n))⟷\mathrm{\exists }C\in \mathbb{ℝ}\mathrm{\exists }{n}_0\in \mathbb{\mathbb{N}}\mathrm{\forall }n(n\ge n_0\to |f(n)|\ge C|g(n)|)$

Note: $f(n)=\mathrm{\Omega }(g(n))\iff g(n)=O(f(n))$

Big Θ

Means that function has same asymptotic growth as another function up to multiplication by constants. Similar to squeeze theorem in Calculus for proof of convergence.

$f(n)\in \mathrm{\Theta }(g(n))⟶\mathrm{\exists }L<\mathrm{\infty }(\underset{n\to \mathrm{\infty }}{\lim }\frac{|f(n)|}{|g(n)|}=L)$

Precise Definiton: $f(n)$ is big theta (same order) of $g(n)$ if and only if there exists constants $L$ and $U$ and a natural number $n_0$ such that $|f(n)|$ is between$L|g(n)|$ and $U|g(n)|$ for all $n>n_0$. $f(n)\in \mathrm{\Theta }(g(n))⟷\mathrm{\exists }L,U\in \mathbb{ℝ}\mathrm{\exists }{n}_0\in \mathbb{\mathbb{N}}\mathrm{\forall }n(n\ge n_0\to L|g(n)|\le |f(n)|\le U|g(n)|)$

In other words,

$f(n)\in \mathrm{\Theta }(g(n))\leftrightarrow (f(n)\in O(g(n))\wedge f(n)\in \mathrm{\Omega }(g(n)))$

In this case, $n_0$ for Big-Θ takes the larger value of the $n_0$'s used in Big-O and Big-Ω.

Examples

Example 1

• Claim $5n=O\left(n^2\right)$
• Choose witnesses $C=5$ and $n_0=1$ (can be derived mathematically to fit the form of the definition of Big-O: $|5n|\le 5|n^2|$ for all $n\ge 1$)
• $\left\{\begin{array}{ccc}5n& <& 5n^2\\ \left|5n\right|& \le & 5\left|n^2\right|\end{array}\right\}\text{true}\mathrm{\forall }n\ge 1$

Example 2

When Joe implements algorithm A in Java and runs it on his home PC. Running time is

$f_1\left(n\right)=7n+52$

When Sue implements algorithm A in Fortran and runs it on dilbert.cs.tamu.edu, the running time is

$f_2\left(n\right)=2n+25$

Resulting speed of both algorithms is $O\left(n\right)$

Example 3

$\begin{array}{rl}7n^2+6n+2& =O(n^2)\\ n^3-3n+2& =O(n^3)\\ (7n^2+6n+2)(n^3-3n+2)& =O(n^2\cdot n^3)=O\left(n^5\right)\end{array}$

Example 4

(See Wikipedia:Binomial coefficient→)

$\begin{array}{rl}(\genfrac{}{}{0ex}{}{n}{2})& =\frac{n(n-1)}{2}\\ & =\frac{n^2}{2}-\frac{n}{2}\\ & =\frac{n^2}{2}+O\left(n\right)\\ & =O\left(n^2\right)\end{array}$

Example: Sort

Sorting Algorithm Animations

Merge sort

sort(A, start, end) {
  if A.size = 1 then return A
  mid = (end-start)/2;
  A1 = sort(A, start, mid);
  A2 = sort(A, mid+1, end);
  A3 = merge(A1, A2);
  return A3;
}

Speed: $O(n\log n)$ (better than $O\left(n^2\right)$)

Numerical analysis: Bisection Method

$\sqrt{k}=?$

Where $f\left(x\right)=x^2-k$ crosses $x$-axis (solve for $f\left(x\right)=0$)

sqrt2() {
  // choose starting interval [x1, x2] carefully
  x1 := 0
  x2 := 2

  // evolving estimate of sqrt(2)
  x3 := 0

  // desired error
  e = .000001

  while(abs(x1-x2) >= e) {
    x3 := (x1+x2)/2
    if (f(x1) * f(x3) < 0) {  // opposite signs
      x2 := x3
    } else {
      x3 := x2
    }
  }
}