CS 310 ‘Algorithms’ Assignment-3

Stable Matching

Q1. [10 marks]

The archeological department is organizing an excavation and there are n teams

participating in it. This excavation is spread over ‘n’ different locations and the teams move

from one location to another after finishing work at the previous location. The organizers

want that no two teams should visit the same location at the same time. They have made

different visiting schedules for these teams. Due to lack of funds, they want to stop the

movement of the teams and assign each of them to one location for a year. Remember that

the teams will be moving according to their schedules and we want to find where each of the

teams should finally stop, while fulfilling the following conditions:

1. No two teams can be at the same location at the same time. For example, if a team

T1 has chosen location L3 as its final stopping destination then no other team can visit

L3 after that.

2. Each team should be assigned a different final destination.

You have to do the following:

1. Design an efficient C/C++ algorithm that takes as input the location schedules for

each of the teams and outputs a final destination for each of the teams, while fulfilling

the conditions mentioned above. [8]

2. In the comments at the beginning of your code, describe how your algorithm works

and terminates. What is the running time of your algorithm? Your should include

clear comments that explain your algorithm’s time. Hint: Use your knowledge of the

stable Gale-Shapley matching algorithm to solve this problem. You can think of these

schedules as location preference lists for the teams. [2]

EXAMPLE: Suppose following is the time schedule for the teams. This schedule is given to

you as input.

Day 1 Day 2 Day 3 Day 4 Day 5 Day 6

Team 1 (T1

) L1 __ L2 __ L3 __

Team 2 (T2

) __ L1 __ L2 __ L3

Team 3 (T3

) L2 __ L3 __ L1 __

The correct final destinations of each of the teams is (L1

,T3

), (L2

,T2

), (L3

,T1

).

As you can see in the example, the teams are moving from one location to another according

to the schedule prepared by the organizers. The dashes ‘ _’ indicate that the teams are

travelling (i.e. in transit) on that day. No two teams are allowed to be at the same location on

the same day (this condition is ensured in the schedule).

Each of the ‘n’ teams have to select exactly one of the ‘n’ locations as their final destination.

Again, no two teams can select the same final destination. In the above example, T1 has

chosen L3 as its final destination on Day 5. Now, no other team can go to location L3 on or

after Day 5. You can see T2 stops at L2, because it cannot go past L2 towards L3 because

T1 is already stopping there.

Your code will read input from a text file. The format of the file is as follows. The first line

contains the value of ‘n’, followed by the schedule of each of the teams. The input of the

above example is shown below.

Input :

n 3

T1 : L1 – L2 – L3 –

T2 : – L1 – L2 – L3

T3 : L2 – L3 – L1 –

Output:

Final Destinations: L1 T3, L2 T2, L3 T1

Divide and Conquer

Q2. [10 marks]

A group of scientists are investigating the effect of a new drug on boosting immune cells in

an organism. They have set up a controlled experiment where they count the number of

immune cells on each day. The experiment takes ‘n’ days to complete.

Suppose following is the result of their measurements for an experiment that ran for n=8

days.

Days Day 0 Day 1 Day 2 Day 3 Day 4 Day 5 Day 6 Day 7

No of

immune

cells

34 56 20 23 16 32 9 30

If on any day ‘x’ the number of immune cells fall below half the count on any of the previous

days then that indicates a failed trial. We need to count the number of failed trials. For

example, in the above table, on Day-2, the count has fallen below half that of Day-1. This is

counted as 1 failed trial. On Day-4 the count has fallen below half of the counts of Day-0 and

Day-1. This is counted as 2 failed trials. On Day-6 the count has fallen below half of those of

Day-0, Day-1, Day-2, Day-3 and Day-5. This means 5 failed trials. The total failed trials in the

above experiment are 1+2+5=8.

1. Code an efficient Divide and Conquer algorithm in C/C++ that reads the experiment

data and prints the number of failed trials. See I/O format below. [8+2]

2. The time complexity of your algorithm should not be more than O(nlog2n).

Input format:

n 8

34 56 20 23 16 32 9 30

Output format:

Failed Trials 8

(2,1)

(4,0) (4,1)

(6,0) (6,1) (6,2) (6,3) (6,5)

Note: (4,1) means that count on Day-4 was less than half the count on Day-1.

Q3. [11 marks]

In this question you will implement a board game using the Divide and Conquer approach.

You are given an nxn square board, where n is a power of 2. One of the squares on the

board is blank and you have to fill the remaining squares with boomerangs. Each boomerang

occupies three squares that form a right angle. See the illustration below. The greyed

square is blank and all the remaining squares should be completely filled with boomerangs.

No boomerangs will share any squares.

1. Code an efficient algorithm in C/C++ that reads the value of ‘n’ and the row and

column indices of the blank square. Your program should then fill all the remaining

squares with boomerangs. You will use integers to represent boomerangs as shown

in the nxn matrix below, where each boomerang is assigned a different number.

The colors are for illustration only. [8]

1 1 2 2 4 4 5 5

1 3 3 2 4 6 6 5

11 3 10 10 8 8 6 7

11 11 10 9 9 8 7 7

12 12 13 13 9 14 15 15

12 20 13 14 14 18 15

21 20 20 19 17 18 18 16

21 21 19 19 17 17 16 16

2. Give a clear description of your algorithm and data structures used to implement it in

the comments at the beginning of your code. What is the recurrence relation of

your algorithm? What is the running time of your algorithm? Your should include

clear comments that explain your algorithm’s time complexity. [3]

Input format:

n 8

(5,0)

Note: (5,0) means the blank is in fifth row and 0th column. The row and column indices start

from zero.

Output format:

1 (0,0) (0,1) (1,0)

2 (0,2) (0,3) (1,3)

3 (1,1) (1,2) (2,1)

…

Note: 2 (0,2) (0,3) (1,3) means the boomerang represented by number 2 is placed at indices

(0,2) (0,3) (1,3) in the matrix.

Q4. [13 marks]

You are given a complete binary tree of height h and n=2

h

leaves. Each vertex in the tree

has an integer value associated with it. We have numbered the leaves from x1

to xn

starting from left to right. An ancestor of a vertex is its parent, grandparent etc., up to the

root of the tree. We define the following:

Ancestry(xi

) of a leaf nodes as the set of vertices including xi and all its ancestors.

Ancestry(xi, xj

) of a pair of leaves is defined as union of their respective ancestries, i.e.,

Ancestry(xi

) U Ancestry(xj

)

The value of an Ancestry is defined as the sum of integer values associated with the nodes

in that set. The following examples illustrate this for the binary tree shown in Figure-1 below.

Figure 1

Example 1:

Ancestry(x2

) = {x2

, v1

, root}

Ancestry(x4

) = {x4

, v2

, root}

Ancestry(x2

,x4

) = Ancestry(x2

) U Ancestry(x4

) = {x2

, v1

, root, v2

, x4

}

Value of Ancestry(x2

) = 37+15+27

Value of Ancestry(x4

) = 4+3+27

Value of Ancestry(x2,x4

) = 37+15+27+3+4 = 86

Example 2:

Ancestry (x1

) = {17, 15, 27}

Ancestry (x2

) = {37, 15, 27}

Value of Ancestry (x1

, x2

) = 96 /* NOTE: 17+37+15+27 = 96. Common ancestors v1 and

root are only counted once since it is a union of sets. */

You have to describe a Divide and Conquer (D&C) algorithm that finds two leaves xi

and xj

such that the Value of Ancestry (xi

,xj

) is maximum.

1. Code an efficient algorithm in C/C++ that solves the above problem. Your code will

read the value of the height of the complete binary tree ‘h’ from the input file. This is

followed by 2n-1 values associated with the nodes of the tree (note that the number

of leaves = n = 2

h and the number of internal nodes is n-1). The node values are

listed in breadth-first order from left to right, starting from the root (see input format

below).

Your code will then run the D&C algorithm on the tree to find xi and xj

that maximize

the value of Ancestry(xi

, xj

). Your algorithm should print the following as output: the

nodes in Ancestry (xi

), nodes in Ancestry (xj

) and Value of Max Ancestry (xi

, xj

). See

output format below. [10]

2. Give a clear description of your algorithm and data structures used to implement it in

the comments at the beginning of your code. What is the recurrence relation of

your algorithm? What is the running time of your algorithm? Your should include

clear comments that explain your algorithm’s time complexity. [1]

3. You algorithm should run for large values of ‘n’. The above example is only for

illustration purposes.

4. You will get partial credit if you design a O(nlog2n) D&C algorithm. It is possible to

design a D&C algorithm for this problem that runs in O(n) time. [2]

Input format (for Figure 1):

h 2

27 15 3 17 37 7 4 /* NOTE: node values are listed in breadth-first order from left to right,

starting from the root. */

Output format:

(xi,xj) = (x1,x2)

Ancestry x1 = {17, 15, 27}

Ancestry x2 = {37, 15, 27}

Value of Max Ancestry (x1,x2) = 96

Q5. [12 marks]

You are given ‘n’ encrypted photos. The images in the photos belong to different biological

species. You have to determine if there are more than photos that belong to the same 2

n

species or not. Since the photos are encrypted, you can’t examine them directly and have to

call a function that takes as input two photos and tells you if they belong to the same

species or not. Assume there can be at most ‘m’ different species, where m<n. The ‘m’

species are identified using integer values from 0 to m-1.

3. Code an efficient Divide & Conquer (D&C) algorithm in C/C++ that solves the above

problem. Your code reads positive integer values of ‘n’ and ‘m’ from the input file.

This is followed by the species of each of the ‘n’ photos (see input format below). You

will also write a helper function decode(), that takes two photos as parameters and

returns “Y” if they belong to the same species, otherwise returns “N” (decode() is

only allowed to compare two photos at a time and there is no way to inspect or

compare them except through this function). If more than photos belong to the 2

n

same species, then your D&C algorithm will report “success” and lists the indices of

those photos, otherwise reports “failure” (see output format below). [10]

4. Note that the species values in the input can only be used by the decode() function.

You will get a zero if your algorithm reads it directly and counts the species.

5. Give a clear description of your algorithm and data structures used to implement it in

the comments at the beginning of your code. What is the recurrence relation of

your algorithm? What is the running time of your algorithm? Your should include

clear comments that explain your algorithm’s time. [2]

6. The time complexity of your algorithm should not be more than O(nlog2n).

7. You algorithm should run for large values of ‘n’. The example is only for illustration

purposes.

Example 1

Input format:

n 8

m 3

0 0 1 2 0 0 1 0

Output format:

Success

Dominant Species Count 5

Dominant Species Indices 0 1 4 5 7

Example 2

Input format:

n 16

m 6

3 0 1 2 3 4 3 5 3 3 2 3 3 0 3 3

Output format:

Success

Dominant Species Count 9

Dominant Species Indices 0 4 6 8 9 11 12 14 15

Example 3

Input format:

n 16

m 6

0 0 1 2 3 4 1 5 5 4 2 3 2 0 3 1

Output format:

Failure

Instructions and policies

1. When submitting, please rename the folder according to your roll number.

2. Do delete all executables and test files before submitting your assignment on LMS.

3. Folder convention should not be changed. If you make any changes, the auto

grader will grade your assignment 0.

4. You must submit your own work. You may discuss the problems with other

classmates but must not reveal the solution to others or copy someone’s work.

Remember to acknowledge other classmates if discussions with them has helped

you.

5. You should name your code files using the following convention: qx.cpp

6. If the assignment includes any theoretical questions, then type your answer to those

questions and submit a separate pdf file for each using the naming convention above.

7. Upload all your files in the corresponding assignment folder on LMS. There will be a

20% deduction for assignments submitted up to one day late (the late

deduction is only applicable to the questions submitted late, not on the whole

assignment). Assignments submitted 24 hours after the deadline will not be

marked.

8. There will be vivas during grading of the assignment. The TAs will announce a

schedule and ask you to sign up for viva time slots. Failure to show up for vivas will

result in a 70% marks reduction in the assignment.

9. In the questions where you are asked to create test cases. Think carefully about good

test cases that check different conditions and corner cases. The examples given in

the assignment are for clarity and illustration purposes. You should not assume that

those are the only test cases your code should work for. Your code should be able to

scale up to larger input sizes and more complex scenarios.

10. Do not make arbitrary assumptions about the input or the structure of the problem

without clarifying them first with the Instructor or the TAs.

11. We will use automated code testing so pay close attention to the input and

output formats.

12. Make sure that your code compiles and runs on Ubuntu. You may choose to

develop your code in your favourite OS environment, however, the code must

be properly tested on Linux before submission. During vivas, your code should

not have any compatibility issues. It’s a good idea to use gcc -Wall option flag

to generate the compiler’s warnings. Pay attention to those warnings as fixing

them will lead to a much better and robust code.

13. For full credit, comment your code clearly and state any assumptions that you have

made. There are marks for writing well-structured and efficient code.

14. Familiarize yourself with LUMS policy on plagiarism and the penalties associated with

it. We will use a tool to check for plagiarism in the submissions.