CMSC 351 (JWG) Homework 9 Given the list of 45 distinct elements: 3, 43, 29, 41, 32, 59, 85, 7, 60, 4, 31, 11, 20, 8, 80 , 66, 22, 50, 16, 90, 26, 79, 2, 96, 6, 54, 81, 93, 53, 99 , 61, 36, 62, 14, 40, 17, 30, 95, 34, 74, 5, 98, 64, 72, 87 Separate the list into columns containing five elements each and sort each column

CMSC 351 (JWG) Homework 9

1. Given the list of 45 distinct elements:

3, 43, 29, 41, 32, 59, 85, 7, 60, 4, 31, 11, 20, 8, 80 ,

66, 22, 50, 16, 90, 26, 79, 2, 96, 6, 54, 81, 93, 53, 99 ,

61, 36, 62, 14, 40, 17, 30, 95, 34, 74, 5, 98, 64, 72, 87

1. 1. Separate the list into columns containing five elements each and sort each column. Keep [5 pts] the same order so the first column will be 3,43,29,41,32 (sorted), the second 59,85,... and so on. Solution:
   2. Identify the medians of each column and the median of medians.               [5 pts]
   3. Draw a table identifying the values guaranteed to be less than or equal to the MOM                [5 pts]
   4. Draw a table identifying the values guaranteed to be greater than or equal to the MOM        [5 pts]
2. In determining the median of medians of a list containing n distinct elements suppose n is an [10 pts] even multiple of 5. Consequently the median of medians will not actually be an element in the list so instead we choose the “lower median” which is the largest value below the median. Show that the MOM is still greater than or equal to

   

   elements in the original list but the less than or equal to bound is slightly better.

Solution:

3. In determining the median of medians of a list containing n distinct elements suppose n is [10 pts] an even multiple of 5 plus 1. We group the elements into an even number of groups of five elements plus a single group of one element and proceed as before. Show that the MOM is still greater than or equal to

   

   elements.

Solution:

4. In the “General Argument, Nice Case” for the median of medians we assumed n to be an [15 pts] odd multiple of 5 and obtained

   

   . Calculate the bounds by modifying the argument for the case in we choose an odd multiple of 7 instead.

Solution:

5. Suppose a graph G has adjacency list:     [10 pts]

AL = [[7],[2,4],[1,4],[6,7],[1,2,6,7],[],[3,4],[0,3,4]]

Draw a picture of G and write down its adjacency matrix.

Solution:

6. For a graph G with n vertices write the pseudocode for an algorithm which takes the adjacency [10 pts] matrix AM for G and produces the corresponding adjacency list AL. What is the Θ(n) time complexity of your pseudocode? Assume it takes Θ(1) time to allocate any fixed size list or array full of zeros.

Solution: