Assignment 1: Graph Algorithms

CS 310 ‘Algorithms’ Assignment-1
 [Total Marks = 90]
Graph Algorithms
IMPORTANT: Read the instructions at the end of this document and follow the naming
conventions.
Marks for writing well structured and efficient code. [5 marks]
Q1. [22 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. [8]
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. [8]
3. Give a clear description of your algorithm and the data structures used to implement
it in the comments at the beginning of your code. What is the running time of your
algorithm and how much space does it use? Your should include clear comments
that explain your algorithm’s time and space complexity. [2+1]
4. You should create at least three different input files to test your algorithm for different
scenarios (see format below). [3]
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 comma
separated list of chemicals with which it reacts. Some examples are given below.
Input :
n 6
C0: C1, C2
C1: C0, C3, C5
C2: C0
C3: C4, C1
C4: C3
C5: C1
Output Format:
Yes
C0, C3, C5
C1, C2, C4
---------------------------
Input :
n 6
C0: C1, C2
C1: C0, C3, C5
C2: C0, C4
C3: C4, C1
C4: C3, C2
C5: C1
Output Format:
No
C0-C1-C3-C4-C2-C0
Q2a.
[22 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 (Li
, Lj
) of leaders such that Li holds a grudge against Lj. Note that the feeling is
not mutual, i.e., Lj does not have a grudge against Li
. The UN organizers have to take them
to the meeting hall and they will be walking in a line down a passage. The organizers are
afraid that Li might try to throw something at Lj
’s back while they are in the line and want that
those that hold a grudge (Li
) are not somewhere behind those they grudge (Lj
) in the line
(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. [8]
2. If a safe ordering is not possible then print at least one sequence of grudges to
illustrate that. [8]
3. Give a clear description of your algorithm and the data structures used to implement
it in the comments at the beginning of your code. What is the running time of your
algorithm and how much space does it use? Your should include clear comments
that explain your algorithm’s time and space complexity. [2+1]
4. You should create at least three different input files to test your algorithm for different
scenarios (see format below). [3]
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 comma
separated list of leaders they hold a grudge against. Some examples are given below.
Input :
n 5
L0: L1, L2, L3
L1: L3
L2: L1
L3:
L4: L0
Output Format:
Yes
L4, L0, L2, L1, L3
-------------------------
Input :
n 5
L0: L1, L2, L3
L1: L3, L4
L2: L1
L3:
L4: L0
Output Format:
No
L4-L0-L1-L4
Q2b. [10 marks]
This part is a continuation of Q2a. 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 Li holds a grudge against Lj
then Li must be in a
lower numbered row than Lj
. Note: lengths of different rows (i.e. number of people sitting in
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. [7+1]
2. Give a clear description of your algorithm and the data structures used to implement
it in the comments at the beginning of your code. The running time should not exceed
that of Q2a. Your should include clear comments that explain your algorithm’s time
and space complexity. [2]
3. You may reuse the input files you created in Q2a above to test your algorithm.
Input :
n 5
L0: L1, L2, L3
L1: L3
L2:
L3:
L4: L0
Output Format:
Yes
4
L4
L0
L1, L2
L3
-----------------------
Input :
n 5
L0: L1, L2, L3
L1: L3, L4
L2: L1
L3:
L4: L0
Output Format:
No
Q3. [16 marks]
Consider a big road network. You are travelling from your home city (say city CA
) to visit a
friend in another city (say city CB
) and you have figured out the shortest length path from
CA
to CB
. Before leaving your home, you learn there is a scenic spot at city Cx and if you take
a detour you can visit that before going to your friend’s place. Since you are driving and you
don’t want to increase the distance you have to travel too much, you decide to only visit Cx
if
the shortest distance from CA
to CB via Cx
increases by no more than 20% of the shortest
distance from CA
to CB
.
1. Code an efficient algorithm in C/C++ that determines if the distance from CA
to CB
via Cx
is at most 20% more than the shortest distance from CA
to CB
. Your code will
ask the user to input the values of CA
, CB
, and Cx
(the cities are numbered from 0 to
n-1, see format below). [6]
2. As output of your algorithm, print the following paths: (i) shortest path from CA
to CB
and its length, (ii) and the shortest path from CA
to CB via Cx and its length. Use
arrows(-) to separate your nodes. [4]
3. Give a clear description of your algorithm and the data structures used to implement
it in the comments at the beginning of your code. What is the running time of your
algorithm and how much space does it use? Your should include clear comments
that explain your algorithm’s time and space complexity. [2+1]
4. You should create at least three different input files to test your algorithm for different
scenarios (see format below). [3]
Your code will read input from a text file. The problem will be modeled as a directed graph,
where the vertices represent cities and the edges represent the roads that connect the cities.
The direction on the edges represent that they are one-way roads. Each of the roads has a
length represented by a positive edge weight. The graph input file format is similar to Q1’s
except for the addition of the edge weights. The graph nodes are numbered from C0
to Cn-1
.
The file will have the value of n on 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 Ci
) followed by a
colon and a comma separated list of nodes to which node i has an edge. The edge weights
will be appended to each neighbor of i using a semicolon. For example, if there is an edge
between node C0 and node C1 of weight 5 and edge between node C0 and node C5 of weight
2, then that will be represented as C0: C1;5, C5;2
An example is given below. Suppose user enters C0 as home city, C2 as friend’s city and C3
as the scenic spot.
n 6
C0: C1;5, C5;2, C3;3
C1: C4;1
C2:
C3: C2;5
C4: C2;1
C5: C2;10
Asymptotic Complexity
Q4. [10 marks]
Q4-i What is the asymptotic time complexity of the following program fragment. [2]
Show your working.
for (i=1; i<=n; i*=2) {
j = i;
}
Q4-iia What is the asymptotic time complexity of the following program fragment. [3]
Give both the upper bound and lower bound for this fragment. Show your working.
int x, y, n;
...
/* P is a 1-D array of size n integers and
W is a 2-D array of size n x n integers */
for (x=0; x<n; x++) {
for (y=x+1; y<n; y++) {
W[x][y] = func(P, x, y);
}
}
...
The function func() called from the main program (above) is defined as follows:
int func(int *array, int i, int j)
{
int ii, val=0;
for (ii=i; ii<=j; ii++) {
val += array[ii];
}
return (val);
}
Q4-iib What is being stored in the 2-D W array in Q4-iia? [2]
Q4-iic The program fragment in Q4-iia is not very efficient. Rewrite it to improve its time
complexity. [3]
Q5. [5 marks]
You are given the following two nxn-dimensional matrices. The first matrix called “Intern
Preference Matrix” stores information about n interns that want to apply for jobs at n
different companies. Each row corresponds to one intern and indicates his/her order of
preference for the employers. For example: Intern-1’s first preference is Employer-3, second
preference is for Employer-1, third preference is Employer-5 and so-on.
The second matrix called “Employer Preference Matrix” stores preference information of
each of the n employers for the intern applicants. For example: Employer-1’s first preference
is Intern-2, second preference is for Intern-4 and so-on.
Intern Preference Matrix
Intern 1 (I1
) E3 E1 E5 E8 ... E2
Intern 2 (I2
) E5 E2 E1 E7 ... E3
Intern 3 (I3
) ... ... ... ... ... ...
... ... ... ... ... ... ...
Intern n (In
) ... ... ... ... ... ...
Employer Preference Matrix
Employer 1 (E1
) I2
I4
I5
I1 ...
I3
Employer 2 (E2
) I6
I2
I3
I4 ...
I1
Employer 3 (E3
) ... ... ... ... ... ...
... ... ... ... ... ... ...
Employer n (En
) ... ... ... ... ... ...
We have a number of queries such as “Does Ex prefer Ia over Ib?” or “Does Ix prefer Ey over
Ez?” and we want to answer each query in O(1) time.
How would you restructure/re-store the above information so that we can answer such
queries in O(1) time? You are only allowed to use arrays. You cannot use other data
structures such as hash tables, etc. Clearly explain your answer and the space required by
your solution.
Instructions and policies
1. 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.
2. You should name your code files using the following convention: Qx-rollno.c
3. Type your answer to the theoretical questions (Q4 & 5) and submit a separate pdf file
for each using the naming convention above.
4. Upload all your files in Assignment-1 folder on LMS. There will be a 20% deduction
for assignments submitted up to one day late. Assignments submitted 24
hours after the deadline will not be marked.
5. 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.
6. For full credit, comment your code clearly and state any assumptions that you have
made. As mentioned in the beginning of the assignment, there are marks for writing
well-structured and efficient code.