## Description

A. Network Delay

Assume that a large database is being transferred from a source S to a destination D.

The transfer is being done through many routes in the form of small data packets. The

destination puts the data packets on a stack in the order they arrive. Since different paths

have different time requirement, a set of packets p1, p2, p3, p4, p5 may be collected at D in the

order S = (p3, p1, p5, p4, p2).

A network performance metric t for this data transfer is computed by taking for every

pair of packets pi

, pj ∈ S, where pi arrives before pj

, the maximum of (i − j).

In the above example, t = 3, which is determined by p5 and p2

Input:

The input is in ‘network.txt’. Each line contains a list of n numbers (1 ≤ n ≤ 1, 000)

representing the packet ordering at D.

Sample input:

3,1,5,4,2

10,3,200

Output:

Each line of the output contains one number, which is the performance metric for the corresponding input.

Sample output:

3

7

1

Assignment 2 — Posted October 5, 2019— Submission Deadline: See Moodle

Instructions:

Edit the given code Network.java to complete the assignment. Do not edit the part which is

READ ONLY. Only submit Network.java in Moodle. To obtain a full mark for this question,

you must try to achieve an O(n log n) time algorithm.

B. Mass Production of Quantum Computer

This is expensive, so before the production – we want to find the best possible design.

The specification says that the computer has X ‘data bus’ — you can think this as X

parallel and disjoint horizontal lines lying on the lines y = k, where 1 ≤ k ≤ X.

The computer needs to connect each pair of buses. The connections can only be vertical.

The cost of connecting a pair of buses is the number of other buses that it crosses. The task

is to find the minimum total cost for arranging the buses.

Figure A is showing a configuration with cost 1, and this is the minimum possible when

X = 5. Note that there can be exactly 10 possible connections for 5 buses and we can make

9 of these connections without crossing. The one shown in red is the one where there is no

way we can avoid a crossing.

Figure B is showing a configuration with cost 3, where X = 6. I am not going to tell you

whether this is the minimum possible – ask others in piazza.

Although in the above examples each connection crosses at most one bus, for larger values

of X, a minimum cost solution may contain a connection with two or more buses.

Input:

The input is in ‘quantum.txt’. Each line contains a number X, representing the number of

data buses.

Sample input:

1

4

5

2

Assignment 2 — Posted October 5, 2019— Submission Deadline: See Moodle

Output:

Each line of the output contains one number, which is the cost for the corresponding input.

Sample output:

0

0

1

Instructions:

Edit the given code Quantum.java to complete the assignment. Do not edit the part which is

READ ONLY. Only submit Quantum.java in Moodle. To obtain a full mark for this question,

you must try to achieve answers for larger values of X.

Reward:

If you can find a correct answer for X = 8, then you get a reward. You can submit for a

reward anytime before November 30.

C. Just to Sharpen the Brain

Let’s define a class of graphs called ‘Recursive Network’ consisting of n ≥ 4 nodes. The

base graph looks like the top left graph in the following figure. The subsequent graphs are

produced by inserting new nodes in clockwise order.

Given a recursive network, we want to find a crossing free layout for the graph minimizing

rectangular area of the layout. The term ‘crossing free’ means no two links cross in the layout.

The bottom figure shows an example crossing free layout that minimizes the area when

n = 7. The rectangular area is (width × height) of the layout. In this example, the area is

3 × 6 = 18 unit square, which is the best possible.

Instructions:

Write your answer and upload a single pdf in moodle. Your answer must consist the followings.

(a) A recurrence relation for solving the problem using dynamic programming.

(b) A pseudocode for solving the problem using your recurrence relation.

(c) A brief argument of why you think your algorithm will produce a correct answer.

(d) The description of the dynamic programming table (or data structure, if any) that

you will be using.

(e) Time complexity analysis of your dynamic programming.

3

Assignment 2 — Posted October 5, 2019— Submission Deadline: See Moodle

To get a full mark, your algorithm must have a time complexity, which is a polynomial

in n.

Reward:

If you can find a correct answer with a running time around O(n

9

), then you will get a bonus.

Here n is the number of nodes. You can submit for a reward anytime before November 30.

4