Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2012:journals:carrie:ch6 [2012/03/25 17:52] – hopkinsc | courses:cs211:winter2012:journals:carrie:ch6 [2012/04/02 01:38] (current) – hopkinsc | ||
|---|---|---|---|
| Line 57: | Line 57: | ||
| * (AGAIn need to do post back work to get the solution.) | * (AGAIn need to do post back work to get the solution.) | ||
| There is an expansion section on the knapsack problem that looks at a different restriction on weight. | There is an expansion section on the knapsack problem that looks at a different restriction on weight. | ||
| + | |||
| + | ===== 6.6 Sequence alignment ===== | ||
| + | Problem: | ||
| + | suppose I type provlem in google as opposed to problem. google looks for problem as the match. So basically matching sequences of letters to find workds. | ||
| + | - we can either have a match, or a gap. If it is a match it can be correct or a mismatch or a gap can be on the x word or the y word. | ||
| + | - we give weights to each option | ||
| + | then we have figure out the optimal sequence from that. | ||
| + | - see 6.16 | ||
| + | - see page 282 or the algorithm | ||
| + | - the graph image on 283 makes it really easy for me to understand. | ||
| + | |||
| + | ===== 6.7 Sequence Alignment in LInear Space via ===== | ||
| + | * changing sequence alignment using divide and conquer | ||
| + | * algorithm on 285 | ||
| + | * split the graph into two different sections and then go forward from your start point and then backwards from your final point to the midel. | ||
| + | * find the path that minimizes the weight | ||
| + | |||
| + | ===== 6.8 Shortest path in a Graph===== | ||
| + | * weighted graph with negative weights | ||
| + | * have to adjust to use dijkstras | ||
| + | * note if there is negative cycles then we will never have a shortest path | ||
| + | * algorithm on page 294 | ||
| + | * implementation O(mn) | ||
| + | |||
| + | |||
