ShareThis

ShareThis

Posted using ShareThis

C++ STL

• http://www.dinkumware.com/manuals/default.aspx
• http://www.sgi.com/tech/stl

Pumping Lemma

What is the importance of the Pumping Lemma?

Automata & Complexity Theory

Review the following:

• DFA
• NFA
• Regular Expressions
• Inductive proofs
• Constructive proofs
• CFGs
• Turing Machines
• Undecidability
• Computational Complexity

 

Eclipse & JDK Downloads

Eclipse 3.2

JDK 1.5

NFA vs. DFA

Theorem:  NFA, a DFA that recognizes the same language.

 Of course iff proofs require bi-direction, even when one direction is trivial.

Has it really been that long ago???  Just give me a state and a symbol so I can union it with the existing states…

 Don’t forget about transitions.

Worst Case & Asymptotic Analysis

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

is objectively better than

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

and

Divide & Conquer Review

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

Generalized Running Time of MergeSort

Design and Analysis of Algorithms Prelims

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

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

Equivalent Regular Expressions

The following two Regular Expressions (RE) are equivalent:

Drawing the Non-Deterministic Finite Automata (NFA) makes it easier to ferret out the RE than drawing the “strictly” Deterministic Finite Automata (DFA).

Chad Salinas find an equivalent RE example.