Description
1 Algorithms Design book
Alice, Bob, and Charlie have decided to solve all exercises of the Algorithms Design book by Jon
Kleinberg, Eva Tardos. There are a total of ´ n chapters, [1, . . . , n], and for i ∈ [1, n], xi denotes the
number of exercises in chapter i. It is given that the maximum number of questions in each chapter
is bounded by the number of chapters in the book. Your task is to distribute the chapters among
Alice, Bob, and Charlie so that each of them gets to solve nearly an equal number of questions.
Device a polynomial time algorithm to partition [1, . . . , n] into three sets S1, S2, S3 so that
max{
P
i∈S1
xi
,
P
i∈S2
xi
,
P
i∈S3
xi} is minimized. [15 marks]
2 Course Planner
You are given a set C of courses that needs to be credited to complete graduation in CSE from IITD.
Further, for each c ∈ C, you are given a set P(c) of prerequisite courses that must be completed
before taking the course c.
1. Device the most efficient algorithm to find out an order for taking the courses so that a student
is able to take all the n courses with the prerequisite criteria being satisfied, if such an order
exists. What is the time complexity of your algorithm? [5 marks]
1
2. Device the most efficient algorithm to find minimum number of semesters needed to complete
all n courses. What is the time complexity of your algorithm? [5 marks]
3. Suppose for a course c ∈ C, L(c) denotes the list of all the courses that must be completed
before crediting c. Design an O(n
3
) time algorithm to compute a pair set P ⊆ C × C such
that for any (c, c0
) ∈ P, the intersection L(c) ∩ L(c
0
) is empty. [5 marks]
3 Forex Trading
Suppose you are a trader aiming to make money by taking advantage of price differences between
different currencies. You model the currency exchange rates as a weighted network, wherein, the
nodes correspond to n currencies – c1, . . . , cn, and the edge weights correspond to exchange rates
between these currencies. In particular, for a pair (i, j), the weight of edge (i, j), say R(i, j),
corresponds to total units of currency cj received on selling 1 unit of currency ci
.
1. Design an algorithm to verify whether or not there exists a cycle (ci1
, . . . , cik
, cik+1 = ci1
)such
that exchanging money over this cycle results in positive gain, or equivalently, the product
R[i1, i2] · R[i2, i3] · · · R[ik−1, ik] · R[ik, i1] is larger than 1. [9 marks]
(Hint: Use the fact that a number x is strictly larger than 1 if and only if log(1/x) < 0).
2. Present a cubic time algorithm to print out such a cyclic sequence if it exists. [6 marks]
4 Coin Change
You are given a set of k denominations, d[1], . . . , d[k]. Example for Rs. 1, 2, 5, 10, 20, 50, 100, you
have d(1) = 1, d(2) = 2, d(3)=5, d(4) = 10, d(5)=20, d(6)=50, and d(7)=100.
1. Device a polynomial time algorithm to count the number of ways to make change for Rs. n,
given an infinite amount of coins/notes of denominations, d[1], . . . , d[k]. [7 marks]
2. Device a polynomial time algorithm to find a change of Rs. n using the minimum number of
coins (again you can assume you have an infinite amount of each denomination). [8 marks]
2