Worst Case & Asymptotic Analysis

July 5, 2007

Guiding Principles of Worst Case and Asymptotic Analysis  

1. Worst Case is useful for the following reasons:

  • Gives a bounded running time for large inputs n
  • Hard to define a “normal” input
  • Easier to analyze

7n \log n is objectively better than 1/2n^2

2. Asymptotic Analysis

  • Don’t care about coefficients
  • Discard lower order terms
  • Don’t lose any predictive power
  • Constants are machine-dependent

Goal: Find algorithms as close to order n as possible

f(n) \in O(g(n)) \exists c > 0 and n_0>0 s.t.

(\forall n>n_0)(0\le f(n)\le cg(n))

1 Comment | Design and Analysis of Algorithms | Permalink
Posted by Chad Salinas

Divide & Conquer Review

June 30, 2007

MergeSort

Input: a list of n numbers

Output: same n numbers in sorted order

Algorithm:

  • Recursively sort 1st half
  • Recursively sort 2nd half
  • Merge 2 sorted lists together (tricky part)

When merging the 2 sorted lists the head of each list is the only candidate element for the head node of the final list.

Specific pseudo-code Running Time of MergeSort \Rightarrow \leq 7n \log n \forall n > 2

Generalized Running Time of MergeSort \Rightarrow \bigcirc (n^2)

Leave a Comment » | Design and Analysis of Algorithms | Permalink
Posted by Chad Salinas

Design and Analysis of Algorithms Prelims

June 29, 2007

1) The Internet is a graph!

Think about how you would send a packet from one network to another on a given web-graph.  What makes a path “good”?  Good path could be any of the following:

  • the one with the least number of hops,
  • shortest path,
  • lowest probability of errors,
  • cheapest path,
  • a working path…

Don’t forget about your tools:

  • Dijkstra’s Algorithm
  • Floyd’s Algorithm
  • Hedetniemi’s Algorithm
  • Bellman-Ford’s Algorithm
  • Prim’s Algorithm
  • Kruskal’s Algorithm

You need to know the all-pairs shortest path minimally. 

2) Sequence Alignment

In computational biology, your input is two strings of DNA code over \Sigma = \{A, B, C\}

What is similar about the two strings:

  • Almost similar sequences?
  • % error rate?
  • edit distance?

Why do we care if two strings are similar?

  1. We may want to extrapolate the function that generates the two strings.
  2. Maybe similar correlates positively with proximity and the evolutionary tree, i.e. two similar genomes yield some inferences.

Forewarned is forearmed! If you don’t have a strong background in statistics and discrete math, you will not survive.

Chad Salinas Design & Analysis of Algorithms

Leave a Comment » | Design and Analysis of Algorithms | Permalink
Posted by Chad Salinas