## 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