[SOLVED] CSE551 Midterm- Foundations of Algorithms

Closed Books, Closed Notes Time:
Each question carries 25 pts.
Important Note: For the purpose of grading your answers, significant emphasis will be given to the process through which you arrive at the answer. In other words, points will be deducted if you do not provide proper justification for your answer, even when you provide the correct answer. If the question asks for finding the answer following a specific technique, points will be deducted if you don’t follow that technique but still provide the correct answer.
Problem 1: Suppose there is a set A of men and a set B of women. Each set contain n elements. There exist two n × n arrays P and Q such that P(i,j) is the preference of man i for woman j and Q is the preference of woman i for man j . Give an algorithm which finds a pairing of men and women such that the following condition is not satisfied. There is an element ai ∈ A that has a higher preference for an element bk ∈ B over the element bj ∈ B with which ai is paired, and bk ∈ B has a higher preference for ai ∈ A over the element al ∈ A with which bk is paired.
Prove the correctness of your algorithm (i.e., it ensures that the given condition isn’t satisfied).

Problem 2: Compute the best case and worst case complexity of the following algorithm. Show all your work.
Algorithm XYZ(S) if |S| = 2 then compare the two numbers and return (min,max) else begin
1. Pick an arbitrary element sk of the sequence S.
2. Divide S into parts S1, S2,S3 such that the elements of S1, S2, and S3 are less than, equal to and greater than sk respectively.
3. return (XYZ(S1),S2,XYZ(S3)) end

Problem 3: Using Dynamic Programming technique, find the optimal solution to the Traveling Salesman Problem for the folowing data set (Distance Matrix).
10 0
13
8 15
9
0
9 20  10   12 
 20
Show all your work. Also show the node ordering in the optimal tour.

Problem 4: Consider the following job scheduling problem. Given a set of jobs J = {J1,…,Jn}.
Is this strategy always going to minimize the total processing cost? If your answer is “yes” then provide arguments to substantiate your claim. If your answer is “no” then provide an example where this strategy fails to minimize the total processing cost.