COMP3600-6466 -  Algorithms - Assignment 3 - Solved

1.    [5 pts] In a max-heap where all elements are distinct, where is the smallest element located? Please explain.

2.    [5pts] Ms RB would like to transform a red-black tree into a black-only tree by setting the children of the red nodes to become the children of the parent of the red nodes, and then removing the red nodes. What can you say about the leaves’ depth of the resulting tree? Please explain.

3.    [10pts] Suppose you need to represent a set of data whose keys are: 1, 2, 3, 4, 5, 6, 7, 8, 9 as an AVL tree.

(a)    [5pts] Draw an instantiation of the shallowest AVL tree that you can construct for the above data set and explain why it is indeed the shallowest AVL tree possible for the data set.

(b)    [5pts] Draw an instantiation of the deepest AVL tree that you can construct for the above data set and explain why it is indeed the deepest AVL tree possible for the data set.

4.    [5 pts] Mr H argues that for a hash table with chaining and simple universal uniform hashing, the expected time complexity to search for an item can be made to be O(n1). He suggested that this time complexity is achievable simply by setting the number of slots in the hash table to be n2 (n is the number of elements in the table) because this setting will lead to a load factor α = 1n. Is Mr H correct? Please explain why or why not.

[35 pts] Part B

5.    [5 pts] Mr B said that he found a comparison-based method to construct a Binary Search Tree in O(n), where n is the number of elements in the data set. Could this be true? Please provide a proof or counter-example to support your argument.

6.    [10 pts] Consider a hash table T with m slots. Suppose T contains a single element, and this element has key k. Ms Search has been searching for r keys that are different from k in hash table T. Assuming T uses simple uniform hashing and chaining, what is the probability that at least one of the r searches collide with the m slot containing key k? Please provide the derivation.

7.    [10 pts] Recall the matrix chain multiplication problem we discussed in class (week-8 Tuesday, based on [CLRS] 15.2). Mr SP says that we can compute the optimal solution to this problem faster, simply by recursively splitting the (sub-)chain of matrices As · As+1 ··· Ae at Ak, where 1 ≤ s ≤ e, the size of Ai for i ∈ [s,e] is pi−1× pi, and k is selected to minimise the value pi−1× pk × pj (i.e., k = argmini∈[s,e−1] pi). To make it clearer, below is the pseudo-code of the algorithm Mr SP proposed. The output of the pseudo-code is a string of the chain of matrices together with their parenthesis.

 

Algorithm 1 SP-MatrixChainMult(A chain of matrices As, As+1,··· , Ae)

 

1: if s == e then

2:           Return “As”

3: Let k = argmini∈[s,e−1] pi

4: Return “(SP-MatrixChainMult(As,··· Ak)) · (SP-MatrixChainMult(Ak+1,··· Ae))”

 

Is Mr SP’s algorithm correct? Please explain your answer by either providing a proof or a counter-example.

8.    [10 pts] As a program manager at a large company, Mr PM is overseeing multiple projects. As a good program manager, he needs to foresee whether there will be delays in each of his projects. To this end, he asked your help to develop a Dynamic-Programming approach to compute an estimated longest duration to finish a project.

To compute the above estimate, you can assume a project is divided into multiple tasks, starting from an initial task and ending at a final task. The dependencies between tasks can be represented as a weighted directed graph, called the task graph. The vertices of a task graph represent the tasks, an edge from a vertex v to another vertex v0 in a task graph means the task represented by v must be completed first before the task represented

 

by v0 can start, and the weight associated with with vertex vv0 indicates the time duration to complete the task represented by v. One can then compute the estimated longest duration to finish a project by finding the longest path from the vertex representing the initial task to the vertex representing the final task in the task graph.

In this question, you need to provide the sub-problems and recursive definition of the optimal value function (i.e., step-1 and step-2 of Dynamic Programming development steps, as discussed in class in week8 Tuesday lecture based on [CLRS] 15.Intro and 15.3) to find the longest path in the task graph.

[40 pts] Part C

9. Ms C has been preparing to start her own restaurant —a TCA Burger franchise— in her city, Arrebnac. She has finalised all the necessary franchising agreement and licensing for the restaurant, as well as signed the lease and finished refurbishing her TCA Burger shop in a strategic location at the Arrebnac City Centre. Now, she needs to start hiring her staff.

Ms C plans to fill n positions, and hires exactly one person for each position. She budgeted a total of at most

B × $10,000 per year to pay the salaries of the people she will hire. In this problem, we use the term salary to include everything an employee will receive (ie, including superannuation and other benefits). For each position-i (i ∈ [1,n]), Ms C receives ki applicants. Each applicant stated the salary they requested. Let’s denote sij × $1,000 as the yearly salary that applicant-j for position-i requested. You can assume Ms C pays the requested salary without negotiation, and that higher salary equals better performance. Ms C would like to hire her staff, such that the total yearly salary she will need to pay is the highest possible not exceeding her budget.

To simplify the problem, you can assume B and sij for all i ∈ [1,n], j ∈ [1,ki] are all positive integers, with 10 ≤ B ≤ 300 and 10 ≤ sij ≤ 100. Furthermore, the number of positions and applicants are limited too, with 1 ≤ n ≤ 25 and 1 ≤ ki ≤ 150 for i ∈ [1,n].

Your task is to help Ms C makes the hiring decision by developing a dynamic-programming algorithm to find the applicants to hire, so that each position is filled by exactly one person, and the total salary is the highest possible not exceeding B × $10,000. To this end, please answer the following questions.

(a)    [10 pts] Please provide step-1 and step-2 of the dynamic programming development steps (the steps are as discussed in class in week8 Tuesday lecture based on [CLRS] 15.Intro and 15.3).

(b)    [4 pts] Please show that for the sub-problems you have defined in Q9, the sub-problem graph is a directed acyclic graph.

(c)     [6 pts] Please provide the pseudo-code for top-down and bottom-up dynamic programming to help Ms C.

(d)    [5] Please derive the asymptotic time complexity of your bottom-up dynamic programming solution.

(e)    [10 pts] Please implement the bottom-up dynamic programming algorithm you have developed above.

Input to the Program. The program will accept a single argument, which is the name of the input file. The input is a text file containing n + 1 lines, where n is the number of positions to be filled. The first line consists of two numbers, separated by a white space. The first number is B and the second number is n. Each line-(i + 1) in the next n lines consists of ki + 1 numbers, separated by a white space. The first number represents the number applicants for position-i, while the next ki numbers represent the requested salaries sij of each applicant, indexed from 1 to ki.

Example:

17 2

3 100 50 70

2 95 75

The above input means that Ms C’s budget is $170,000 and two positions are to be filled. For the first position, 3 applicants apply, with the requested yearly salary for the first, second, and third applicants being $100,000, $50,000, and $70,000 respectively (i.e., s1,1 = 100, s1,2 = 50, s1,3 = 70). For the second position, there’s only two applicants, with their yearly requested salary being $95,000 and $75,000.

Output to the Program. The program should output to standard output. If the problem has one or more solution, the program should output a single line containing of n + 1 numbers separated by a white space. The first number is the total salary cost of the people selected to be hired. The next n numbers are the indices of the selected applicant, starting from the selected applicant for the first position, then the second, etc.. If the same total salary cost can be achieved by selecting more than one set of selected applicants, any set of them will be acceptable. If the problem has no solution, the program should output “no solution”.

Output example for the example input scenario: 165000 3 1