Assignment 01 Solution

Description

Q1. [14 marks]

You are given a set of ‘n’ chemical compounds which have to be packed in two boxes. Some of the chemicals may react with other chemicals and should not be packed in the same box.

1. Code an ​efficient algorithm in C/C++ that determines if it is possible to safely pack these chemicals in two boxes and if so, then print which chemicals should go in

Box-1 and which in Box-2.

[6]

2. If it is not possible to safely pack the chemicals in two boxes then print at least one

sequence of chemical interactions that prevents such a division.

[6]

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? You 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 .

Your code will read input from a text file. The format of the file is as follows. The first line contains the number of chemicals. This will be followed by n lines (one for each of the n chemicals) and each line will contain the chemical number followed by a colon and a list of chemicals with which it reacts. Some examples are given below.

Input :

n 6

0:12

1:035

2 : 0

3:41

4 : 3

5 : 1

Output Format:

Yes

0 3 5

1 2 4

—————————

Input :

n	6
0	: 1 2

1:035

2:04

3:41

4:32

5 : 1

Output Format:

No

0->1->3->4->2->0

Q2. [14 marks]

Suppose there exists a large transportation road network in a country that is prone to flooding. This road network is modeled as a connected graph, where the cities are represented as vertices and the bi-directional roads as undirected edges. Some roads in this transportation network are especially vulnerable, because they form the ​only connection between one part of the network with another and if they are damaged the network will become disconnected. You, as a computer scientist, are given the task of identifying ​all such vulnerable roads in this large network. See some examples below.

Figure-1

In Figure-1, ​two​edges (1,3) and (7,8) are vulnerable edges.

Figure-2

In Figure-2, ​none​of the edges are vulnerable.

Your code will read input from a text file. The problem will be modeled as an undirected graph, where the vertices represent cities and the edges represent the roads that connect the cities. The graph nodes are numbered from V​ to V​ . The file will have the value of n on

0 n-1​

the first line. This will be followed by n lines (one for each of the n nodes in the graph) and

each line will contain a node number (say V​) followed by a colon and a list of nodes to which

i​

node i has an edge. For example, if there is an edge between node V​ and node V​ and edge

0 1

between node V​ and node V​, then that will be represented as 0:1 3

0​ 3​

For example, the input graph in Figure-2 will be represented as below.

Input (for Figure-2):

n 5

0:13

1:023

2:134

3:0124

4:23

Output (for Figure-2):

0

Output (for Figure-1):

2

(1,3)

(7,8)

1. Code an ​efficient O(|V|+|E|) algorithm in C/C++ that determines the number of vulnerable edges in the given graph. You also have to output all such vulnerable

edges, if they exist. See the given output format.

[12]

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 .

Q3a. [12 marks]

A group of world leaders are attending a United Nations meeting. Some of the leaders hold a grudge against some of the others. You are given the set of world leaders and a set of

​		​	​		​
ordered pairs (L , L ) of leaders such that L holds a grudge against L					Note that the feeling is
i​		j​	i ​	​	j. ​
not mutual, i.e., L	​
	j	does not have a grudge against L . The UN organizers have to take them
				i​

to the meeting hall and they will be walking in a line down a passage. The organizers are

afraid that L	​			​
	i	might try to throw something at L ’s back while they are in the line and want that
		​	​	j​
				​
those that hold a grudge (L ) are not somewhere behind those they grudge (L ) in the line
		i​		j​

(note the phrase “somewhere behind in the line”). The organizers have asked you for help.

1. Code an ​efficient algorithm in C/C++ that prints a safe ordering of the leaders in the

line or lets the organizers know that it is not possible.

[5]

2.	If a safe ordering is not possible then print at least one sequence of grudges to
	illustrate that.	[5]
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? You 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 .

Your code will read input from a text file. The format of the file is as follows. The first line contains the number of leaders. This will be followed by n lines (one for each of the n leaders) and each line will contain the leader number followed by a colon and a list of leaders they hold a grudge against. Some examples are given below.

Input :

n 5

0:123

1 : 3

2 : 1

• :

4 : 0

Output Format:

Yes

40213

————————-

Input :

n 5

0	:123
1	: 3 4
2	: 1

• :

4 : 0

Output Format:

No

4->0->1->4

Q3b. [10 marks]

This part is a continuation of Q3a. Instead of lining up the leaders, you have to seat the leaders in rows while they are on the stage. Let’s call the front row of the stage as Row-1

and second row as Row-2 and so-on. If L​holds a grudge against L​then L​​must be in a

i ​ j i

lower numbered row than L​. Note: lengths of different rows (i.e. number of people sitting in

j​

that row) need not be the same. The organizers have asked you for help.

1. Code an ​efficient algorithm in C/C++ that finds the ​minimum number of rows

needed. You have to print the number of rows and the order in which the leaders are seated in rows. If it is not possible to safely place the leaders in rows then mention

that in the output.

[8]

2. Give a clear description of your algorithm and data structures used to implement it in the comments at the beginning of your code. ​The running time should not exceed

that of Q3a. ​You should include clear comments that explain your algorithm’s time

complexity. [2]

3. You may reuse the input files you created in Q3a above to test your algorithm.

Input :

n 5

0:123

1 : 3

• :

3 :

4 : 0

Output Format:

Yes

• 4

4

0

1 2

3

———————–

Input :

n 5

0	:123
1	: 3 4
2	: 1

• :

4 : 0

Output Format:

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: q​x​.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.