COMPSCI 170 Study Guide - Midterm Guide: Linear Programming, Directed Graph, Flow Network
Document Summary
The number of points indicate the amount of time (in minutes) each problem is worth spending. Not all parts of a problem are weighted equally. Write in the space provided, and use the back of the page for scratch. Only attempt these questions at the very end. When an explanation is required, answer with one or two short sentences. (25 points: consider the following directed graph with all edge capacities equal to 1. In the rst step of maximum-flow algorithm, we increase the ow along s a d b c t by one unit. (a) draw the residual graph after this step. 0. 125: on a weirdly designed keyboard, every insertion takes 2 keystrokes, every deletion takes 3 key strokes and every substitution takes 4 keystrokes. Write the recurrence relation for the edit distance (minimum number of key strokes needed to edit a string x[1, . , m] in to a string y[1, .
