For this assignment, you will create a Ruby source file containing a ruby function(s) implementing each of the problems described below. If you find it useful for any of the problems in this assignment, you may define additional helper functions that your primary function for that problem calls to solve a sub-problem. Definitions for these helper functions should be included in the same Ruby source file as the primary function they help. You should store a source file for each problem in a folder named pa9.
Note: You are responsible for protecting your solutions to these problems from being seen by other students either physically (e.g., by looking over your shoulder) or electronically. (More information can be found in the instructions for Programming Assignment 2.)
[4 points] Consider a process P to perform a task (e.g., do a load of laundry) that is split into \(n\) subprocesses \(p_{0}, p_{1}, p_{2}, \ldots, p_{n-1}\) (e.g., wash the load, dry the load, fold the load). Each process \(p_{i}\) must be completed after \(p_{i-1}\) and before \(p_{i+1}\), \(0 < i < n-1\). Each subprocess can be completed in time \(t_{0}, t_{1}, t_{2}, \ldots, t_{n-1}\), respectively.
Algorithm: First, compute the sum of the times in the array t and then return m multiplied by this sum.
Sample usage:
>> subtask_times = [30, 40, 20] => [30, 40, 20] >> nonpipelined(subtask_times, 5) => 450
Observation: The total time for the m tasks depends on the amount of time required for the longest subtask. For example, if the task is doing a load of laundry and the subtasks are washing (W), drying (D), and folding (F), with times of 30 minutes for washing, 40 minutes for drying, and 20 minutes for folding, then we can do five loads of laundry using pipelining (with one washer, one dryer and one folding table) in 250 minutes as follows:
1111111111222222 1234567890123456789012345 0000000000000000000000000 minutes ------------------------- WWWDDDDFF WWW DDDDFF WWW DDDDFF WWW DDDDFF WWW DDDDFF
In general, to compute the total time, we simply just have to compute m multiplied by the time for the longest subtask, and then add the time for all of the other subtasks once to get the final total. For example, for the five loads of laundry, the longest subtask is drying (40 minutes) so pipelining would take:
5*40 (drying) + 30 (washing) + 20 (drying) = 250 minutes
Algorithm: Find the maximum subtask time in the array of times. Then multiply this maximum by m and add to this all of the remaining times in the array.
Sample usage:
>> subtask_times = [30, 40, 20] => [30, 40, 20] >> pipelined(subtask_times, 5) => 250
[3 points] Consider the 8 X 8 sorting network shown below using a wire diagram.
This network starts with an array of 8 data elements and sorts the array by comparing two elements at a time. The elements that need to be compared are shown by the connections between the wires in the diagram. For example, the first comparison compares x_{0} with x_{1}. If they are not in the correct order, they are swapped. The next elements that are compared are x_{2} and x_{3}. If they are not in the correct order, they are swapped. This continues with x_{4} and x_{5}, etc. Additionally, the wire diagram shows that the first four comparisons can be done concurrently since they don't depend on each other. However, in this exercise, you will compute them sequentially using Ruby.
This function simulates a single comparator shown in the sorting network above.
Sample usage:
>> load "compex.rb" => true >> list = [6, 3, 4, 7] => [6, 3, 4, 7] >> list = compex(list, -3, 9) => [6, 3, 4, 7] >> list = compex(list, 0, 1) => [3, 6, 4, 7] >> list = compex(list, 1, 3) => [3, 6, 4, 7] >> list = compex(list, 1, 2) => [3, 4, 6, 7]
For this problem, you may assume that the length of the supplied list is exactly 8 and you do not have to check for this.
NOTE: Your function should NOT have 19 calls to the compex function. Look at the network to see where you can use loops to simplify some of the work.
Sample usage:
>> load "compex.rb" => true >> load "networksort.rb" => true >> list = ["cat", "pig", "dog", "bird", "lizard", "fish", "hamster", "horse"] => ["cat", "pig", "dog", "bird", "lizard", "fish", "hamster", "horse"] >> list = networksort(list) => ["bird", "cat", "dog", "fish", "hamster", "horse", "lizard", "pig"]
its minimum spanning tree (with a total cost of 19) would be:
We can represent the minimum spanning tree as an array where each position of the array represents a node in the graph and the value stored at index i in the array is the index of the parent of node i in the graph's minimum spanning tree. For example, for the MST tree above, we could represent this MST using the array:
[nil, 2, 4, 4, 0]
This means the parent of node 0 is nothing (it is the "root"), the parent of node 1 is 2, the parent of node 2 is 4, the parent of node 3 is 4, and the parent of node 4 is 0. (NOTE: A minimal spanning tree is not necessarily a binary tree.)
Write a function mst(graph) (in a file named mst.rb) that takes a weighted graph represented as a two-dimensional matrix (as discussed in class) and returns the minimum spanning tree for this graph as a one-dimensional array of parent nodes, as described above.
Follow this algorithm to compute the MST. (NOTE: Remember that some steps might require more than one line of code in Ruby.)
NOTES:
In Ruby, Infinity is represented as 1/0.0 .
To perform substep C in step V, you will need
to use the sort_by function. You can do this in Ruby
as follows:
pq = pq.sort_by { |x| cost[x] }
Sample usage: (output corrected)
>> load "mst.rb" => true >> inf = 1/0.0 => Infinity >> graph = [[0,8,inf,inf,4],[8,0,3,inf,6],[inf,3,0,9,5],[inf,inf,9,0,7],[4,6,5,7,0]] => [[0, 8, Infinity, Infinity, 4], [8, 0, 3, Infinity, 6], [Infinity, 3, 0, 9, 5], [Infinity, Infinity, 9, 0, 7], [4, 6, 5, 7, 0]] >> mst(graph) => [nil, 2, 4, 4, 0]
You should now have a pa9 directory that contains the required files, nonpipelined.rb, pipelined.rb, compex.rb, networksort.rb, and mst.rb, each—in turn—containing the corresponding function(s). Zip up your directory and upload it using the handin system. (The handin system will accept submissions beginning on Friday until the deadline Tuesday night.)