CS 310 ‘Algorithms’ Assignment-2

IMPORTANT: Read the instructions at the end of this document and follow the naming

conventions.

Q1. [12 marks]

You are given an nxn square game board and positive integers row1

, row2

, … rown and col1

,

col2

, .. coln

. You have to place the game pieces in the squares in such a way that the number

of game pieces in i

th

row is equal to rowi and the number of game pieces in the i

th column is

equal to col

i

.

For example, let n=4. You are given as input a blank 4×4 board and the following integers:

row1=2, row2=2, row3=2, row4=3

col1=3, col2=2, col3=1, col4=3

One possible arrangement of game pieces on the board, satisfying the above row and

column values, is as follows:

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

code will take as input the value of ‘n’ and the row and column values. See the input

format below. [6+2]

2. Your algorithm should output the (row, column) indices where game pieces are

placed. See format below. If it is not possible to satisfy the row and column values

given in the input, then your algorithm should output “Not Possible”. [2]

3. 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 running time of your

algorithm? Your should include clear comments that explain your algorithm’s time

complexity. [2]

4. You should create at least three different input files to test your algorithm for different

scenarios (see format below). Creating test cases helps you think about the problem

and different corner cases. For testing your code, you may share your test cases with

other classmates. Your code should be able to scale up to larger input sizes.

Input :

n 4

Row 2 2 2 3

Col 3 2 1 3

Output :

(1,1) (1,4)

(2,1) (2,2)

(3,3) (3,4)

(4,1) (4,2) (4,4)

Q2. [12 marks]

Consider a large warehouse where the inventory items for storage are stacked in ‘n’ racks.

Assume all the racks are placed in a straight line as shown in the figure below. The racks are

of different lengths L1

, L2

, .. Ln

.

One type/category of items are placed together on one rack. Depending on the sales,

different items require replenishment more often than others. Each of the racks have

replenishment probabilities associated with them, which are denoted by p1

, p2

, … pn

.

A robot stands on the left of the first rack and when it receives a replenishment request, it

goes to the appropriate rack and fills it up. We want to come up with an ordering of the

racks, along a straight line, such that the expected replenishment time is minimized. That

is, for all the ‘n’ racks, you have to decide which rack should be placed where, starting from

the first position on the left to last on the right.

For example, suppose n=3 and rack3

is placed first, followed by rack1 and lastly rack2

. The

expected replenishment time is given by: p3 x L3 + p1

(L3+L1

) + p2

(L3+L1+L2

).

If we change the ordering in the above example to rack2

, rack3

, rack1

, then the expected

replenishment time will be p2 x L2 + p3

(L2+L3

) + p1

(L2+L3+L1

).

If the ordering is denoted by O1

, O2

, … On

, then the general formula for expected time is

given as follows:

pOx

( LOy ∑ )

x=n

x=1

∑

x

y=1

You have to come up with a greedy strategy for rack ordering that minimizes the expected

replenishment time.

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

code will take as input the value of ‘n’ and the lengths of the racks and their

replenishment probabilities. Your algorithm should output the ordering of the racks as

well as the expected time. See input and output formats below. [8+2]

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 running time of your

algorithm? Your should include clear comments that explain your algorithm’s time

complexity. [2]

3. You should create at least three different input files to test your algorithm for different

scenarios (see format below). Creating test cases helps you think about the problem

and different corner cases. For testing your code, you may share your test cases with

other classmates. Your code should be able to scale up to larger input sizes.

Input :

n 4

L 12 2 8 3

p 0.3 0.2 0.4 0.1

Output :

2 3 4 1

Expected Time 13.2

Q3a. [10 marks]

Consider a railway network that connects a large number of cities across the country. A big

oil company is laying pipelines along a rail network. The rail network has ‘n’ junctions and

the oil company has set up booster stations at each junction. They want to minimize the

total length of the pipes they have to lay such that there is a path for oil between every pair

of junctions. The engineers at the oil company have constructed an undirected, weighted

graph G(V,E) with ‘n’ vertices (i.e., junctions) and ‘m’ railway tracks. To minimize the total

pipe lengths along the rail tracks they have constructed a minimum spanning tree ‘T1

’ of G

and installed pipes along the edges of T1

.

One day, due to an earthquake, one of the railway tracks and also the pipe alongside it is

permanently damaged. The engineers have to quickly construct a new minimum spanning

tree T2 after removing the damaged rail track from the graph G. You have to help the

engineers. Note: if you say rerun a minimum spanning tree (MST) algorithm on the rail

network, you will not get any marks.

A. Code an efficient algorithm in C/C++ to solve the above problem. The input to your

program is a weighted undirected graph G. You will find T1 of G using any of the MST

algorithms. Now delete an edge ‘e’ from T1

(see input format) and find the new MST

(T2

) without re-running the MST algorithm. Your program should output the MST T1

,

the edge ‘e’ you have removed from T1

, and the new MST T2

. You should also print

the sum of all edge weights of the two MSTs. For outputting the MST, it is sufficient if

you list all its edges. Note: it is possible that a new spanning tree T2

, including all the

vertices of G, cannot be constructed after deletion of ‘e’ (think about why). In that

case, simply print that T2 cannot be constructed. [4+4]

B. 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 running time of your

algorithm? Your should include clear comments that explain your algorithm’s time

complexity. [2]

C. You should create at least three different input files to test your algorithm for different

scenarios (see format below). Creating test cases helps you think about the problem

and different corner cases. For testing your code, you may share your test cases with

other classmates. Your code should be able to scale up to larger input sizes.

An example of a graph G is below. You will read input from a file. The first line of the input

contains ‘n’, the number of vertices in the graph. The format is similar to one described in

Assignment-1, except that the graph is weighted and the weights are indicated after a

semicolon. E.g. in the following example, there is an edge from node 0 to node 1 with weight

3 and an edge from node 0 to node 2 with weight 4, etc. The last line of the input file

contains the edge you will delete.

Input :

n 5

0 : 1;3 2;4

1 : 0;3 3;5 4;2

2 : 0;4 3;4

3 : 1;5 2;4 4;2

4 : 1;2 3;2

(1,4)

Output :

MST1: (0,1) (0,2) (1,4) (4,3)

Sum MST1: 11

Edge Removed: (1,4)

MST2: (0,1) (0,2) (2,3) (4,3)

Sum MST2: 13

Q3b. [10 marks]

This is a continuation of Q3a. You have the same initial rail network G(V,E) described in

Q3a. This time there is no earthquake but the railway company has added a new railway

track between two of the junctions (there was no direct track between these junctions

previously). The railway engineers want to know what the new MST T2

looks like after the

addition of this new link. As in Q3a, you are not allowed to rerun the MST algorithm to

find T2

.

A. Code an efficient algorithm in C/C++ to to find T2

. The input to your program is

similar to that in Q3a. A new link to G will be added between two vertices that did not

have an edge previously (the last line in the input file will now be the new edge

added). Your program should output the original MST T1

(reuse code from Q3a), the

edge ‘e’ you have added to G and the new MST T2

. You should also print the sum of

all edge weights of the two MSTs. For outputting the MST, it is sufficient if you list all

its edges. [4+4]

B. 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 running time of your

algorithm? Your should include clear comments that explain your algorithm’s time

and space complexity. [2]

C. Reuse the input files you created in Q3a to test your algorithm for different scenarios.

Output format for the above question is similar to Q3a. Change ‘Edge Removed’ to ‘Edge

Added’

Q4. [14 marks]

You are standing in a hallway that has ‘n’ rooms. Each of the rooms has a double door. To

enter the room you can open either the right-side of the double door or the left-side or both

sides. Each of the sides of the double doors are labeled. See Figure-3 below, which shows

three rooms in the hallway. The same label (for example da2) can appear on more than one

door.

Figure-3

The architect, who designed the rooms loved puzzles, so he created what we’ll call an “anti”

door. In Figure-3, we denote the “anti” door by an extra symbol ‘a’. If a door (say) d1 is

opened then its anti-door (denoted by da1) will automatically lock and da1 cannot be

opened until d1 is closed. Similarly, if da1 is opened, then d1 will close. Note that a door

label can appear more than once, so if you open (say) da2 in one room then all door-sides

with the same label in other rooms will also open automatically.

We want to find out if it’s possible to open all rooms at the same time. Note that opening a

room means that at least one side of the double-door is open. See some examples below:

Example-1

In Example-1, we can open d2, d1 and da0, and hence all three rooms will be open at the

same time.

Example-2

In Example-2, we can open d0 and da1, and hence all three rooms will be open at the same

time.

Example-3

In Example-3, it is not possible to open all four rooms at the same time.

1. Code an efficient algorithm in C/C++ that determines if it’s possible to open all ‘n’

doors at the same time. If yes, then you should identify which door-sides should be

opened. See the given output format. [10+2]

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 running time of your

algorithm? You should include clear comments that explain your algorithm’s time

complexity. [2]

3. You should create at least three different input files to test your algorithm for different

scenarios (see format below). Creating test cases helps you think about the problem

and different corner cases. For testing your code, you may share your test cases with

other classmates. Your code should be able to scale up to larger input sizes.

As you can see in the examples above, integer values are used for the door labels starting

from 0. E.g. in Example-1, we have three labels: 0, 1 and 2 to identify the doors and the

corresponding anti-doors. In Example-2 we have two labels: 0 and 1. Let ‘k’ be the number

of door labels.

Your code will read input from a text file. The file will have the value of n on the first line. The

second line will have value of ‘k’. This will be followed by n lines (one for each of the n

rooms) and each line will contain the labels of its two doors. For example, Example-1 is

represented as below.

Input (for Example-1):

n 3

k 3

da1 d2

d1 da2

da0 da2

Output (for Example-1):

Yes

0

1

1

NOTE: The above output prints values assigned to doors in increasing order of their

labels. (i.e., the values you have assigned to d0, d1 and d2 respectively, each on a separate

line). A value of 0 to d0 means that d0 is closed (and hence da0 is open). A value of 1 to d1

means door d1 is open and similarly value of 1 to d2 means door d2 is open.

Output (for Example-3):

No

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.