Your cart is currently empty!
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…
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:
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 (Lā,Tā), (Lā,Tā), (Lā,Tā). 1ā 3ā 2ā 2ā 3ā 1ā
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 |
34 |
56 |
20 |
23 |
16 |
32 |
9 |
30 |
immune |
||||||||
cells |
||||||||
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(nlogān)ā.
2ā
Input format:
n 8
345620231632930
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.
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 |
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:
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] |
||
h |
|||
You are given a ācomplete binary tree of height h and n=2ā 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(x |
ā |
ā |
|||
) of a leaf nodes as the set of vertices including x |
and all its ancestors. |
||||
iā |
ā |
ā |
iā |
||
Ancestry(x |
āā ā |
||||
i, |
x ) of a pair of leaves is defined as union of their respective ancestries, i.e., |
||||
jā |
ā |
||||
Ancestry(x |
ā |
||||
) U Ancestry(x ) |
|||||
iā |
jā |
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 xāand xā
iā j
such that the āValueāof Ancestry (xā,xā) is āmaximumā.
iā jā
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 = 2hā 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 xāiand xājthat maximize
ā |
ā |
||
the value of Ancestry(x , x ). Your algorithm should print the following as output: the |
|||
iā |
jā |
ā |
ā |
ā |
ā |
||
nodes in Ancestry (x ), nodes in Ancestry (x ) and Value of Max Ancestry (x , x ). See |
|||
iā |
jā |
iā |
jā |
output format below. |
[10] |
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 n2 photos that belong to the same 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.
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 n2 photos belong to the
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] |
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.
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(nlogān)ā.
2ā
You algorithm should run for large values of āānāā. The example is only for illustration purposes.
Input format:
8 m 3
00120010
Output format:
Success
Dominant Species Count 5
Dominant Species Indices 0 1 4 5 7
Example 2
Input format:
16 m 6
3012343533233033
Output format:
Success
Dominant Species Count 9
Dominant Species Indices 0 4 6 8 9 11 12 14 15
Example 3
Input format:
16 m 6
0012341554232031
Output format:
Failure
Instructions and policies
When submitting, please ārename the folderāaccording to your āroll numberā.
Do ādelete all executablesāand ātest filesābefore submitting your assignment on LMS.
Folder convention āshould not be changed. If you make any changes, the auto grader will āgrade your assignment 0ā.
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.
You should name your code files using the following convention: qāxā.cpp
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.
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.
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.
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.
Do not make arbitrary assumptions about the input or the structure of the problem without clarifying them first with the Instructor or the TAs.
We will use automated code testing so pay close attention to the input and output formats.
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.
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.
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.