Homework 9

Details

For each problem make sure you clearly and neatly show all of your work! Each part/problem is worth 5 points.

1. Sort the following list using Merge Sort.
   

       68, 25, 87, 39, 52, 14, 78, 46, 63, 31, 95, 22, 57, 10, 73, 5

   For simplicity, assume you have a parallel computer so that you can sort both halves at the same time. Show your work similarly to the last several slides we saw in class--a tree-like structure that branches out and then back together.
2. Use a table like we did in class to compute the edit distance from definitely to defiantly. Highlight the cells in the table that help determine what changes need to be made to go from one word to the other. Then show the steps to go from the first word to the second word.