Motivating Application

1.  The Internet is a graph [vertices = end hosts + routers, directed edges = direct physical or wireless connections].

 

2.  Web graph. [vertices = web pages, edges = hyperlinks].

 

3.  Social networks. [vertices = people, edges = friend/follow relationships].

 

4.  If use Dijkstra's algorithm for routing, a router needs to know entire Internet!

    Solution: the Bellman-Ford algorithm (bonus: also handles negative edge costs).

 

5.  Sequence alignment problem ( useful for computational genomics ):

     Input: 2 strings over {A,C,G,T}.

         - Penalty Pen(gap) >= 0 for each gap.

         - Penalty Pen(AT) >= 0 for mismatching A and T.

         - etc.

     Output: Alignment of the strings that minimizes the total penalty. ( Needleman-Wunsch score A.K.A. editorial distance)

     Solution: Straightforward dynamic programming.