15110 Fall 2011 [Cortina/von Ronne]

Programming Assignment 9 - due Tuesday, November 15

Overview

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.)

Problems

  1. [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.

    1. Write a Ruby function nonpipelined(t, m) (in a file named nonpipelined.rb) that takes an array t containing the times required to complete the subprocesses and the number m of tasks that need to be performed. This function should return the total amount of time it takes to perform the m tasks if a pipeline is NOT used. (That is, the first task must be completely finished before we can start the second task, etc.)

      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
      

    2. Write a Ruby function pipelined(t, m) (in a file named pipelined.rb) that takes an array t containing the times required to complete the subtasks and the number m of complete tasks that need to be performed. This function should return the total amount of time it takes to perform the m tasks if pipelining is used. (That is, after the first subtask of the first task is done, we can start the first subtask of the second task while the second subtask of the first task is being performed, etc.)

      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
      

  2. [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 x0 with x1. If they are not in the correct order, they are swapped. The next elements that are compared are x2 and x3. If they are not in the correct order, they are swapped. This continues with x4 and x5, 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.

    1. Write a function compex(list, i, j) (in a file named compex.rb) that takes a list (array) of elements and two indices i and j. The function should compare the elements in the list at index i to see if it is less than or equal to the element in the list at index j. If not, it should exchange them. The function should return the list as its result in either case. If either index is invalid, you should just return the current list instead. (NOTE: You will have to check this special situation first.)

      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]
      

    2. Write a Ruby function networksort(list) (in a file named networksort.rb) that takes a list of 8 elements and sorts it based on the sorting network shown above. You will not be performing the comparison/exchanges concurrently. You should perform them one at a time, making sure to perform the ones to the left first before moving on to the right (due to the dependencies in the network). Return the list once all of the comparison/exchanges have been done.

      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"]
      

  3. [3 points] Recall that a minimum spanning tree for a weighted graph G is a graph that contains only those edges that are necessary to connect the all of the nodes and has a minimum total weight. For example, for the graph below:

    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.)

    1. Set n equal to the number of nodes in graph.
    2. Set pq equal to a new array of size n. Then initialize each element at the index \(i\) to the value \(i\). (That is, set pq[0] = 0, pq[1] = 1, etc.)
    3. Set cost equal to a new array of size n. Then initialize each element in this array to Infinity. (See NOTES below.)
    4. Set parent equal to a new array of size n. You do not need to initialize this array.
    5. While the length of the array pq is greater than 1, do the following:
      1. Remove the first element from the array pq and set current equal to this value.
      2. For every element i in array pq do the following:
        1. Set w equal to the weight (stored in graph) of the edge from current to i.
        2. Set c equal to cost[i] (the cost for connecting node i to the spanning tree).
        3. If w < c then do the following:
          1. Set parent[i] equal to current.
          2. Set cost[i] equal to w.
      3. Sort the elements of pq according to the value obtained, for each element x of pq, by calculating cost[x]. Set pq equal to this sorted array. (See NOTES below.)
    6. Return the array parent as the final result.

    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]
    

Submission

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.)