CS 215 Homework 3

1. Sort the following list of numbers using Quicksort. Show the steps of the algorithm that you follow.

   12 34 14 5 10 76 85 23 10 4 17 37 25 18 15 7

2. Your company has developed a program for use on a small parallel processing machine. According to the technical documentation, the program executes processes P1, P2, and P3 in parallel; these processes all need results from process P4, so they must wait for process P4 to complete execution before they begin. Processes P7 and P10 execute in parallel but must wait until processes P1, P2, and P3 have finished. Process P4 requires results from P5 and P6 before it can begin execution. Processes P5 and P6 execute in parallel. Processes P8 and P11 execute in parallel, but P8 must wait for process P7 to complete, and process P11 must wait for P10 to complete. Process P9 must wait for results from P8 and P11. You have been assigned to convert the software for use on a single processor machine.
   Draw the directed graph corresponding to this program and then follow the Topo-Sort algorithm (in Section 8.5.4) to give a topological ordering of this graph. Show your work.
3. Discuss what changes (if any) would need to be made to Dijkstra's algorithm (in Section 9.2.1) so that it works for undirected graphs.
4. Show the steps of Dijkstra's algorithm to find the shortest paths from vertex 1 to the other vertices.