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.

LaTex Equation Test01

LaTex has to be easier than Word Equation Editor for quick and dirty equation postings:

Chad Salinas LaTex Equation free form test — seems to be the most straight-forward.

Word Equation Editor Test01

Here is my test which is just an image created when you save Word as htm:

 

You can then import the image from a subfolder of the Word & htm file into WordPress.  Then, you can move the image to wherever you need to in the WordPress blog.

Chad Salinas Word Equation Editor test in WordPress.

Test Math Formula

Can you use the equation editor in Word 2007 or do you have to use Latex? 

Chad Salinas test from searching on "equation" in WordPress