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?
- We may want to extrapolate the function that generates the two strings.
- 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
