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 p₁,p₂,p₃,p₄,p₅ may be collected at D in the order S = (p₃,p₁,p₅,p₄,p₂).

A network performance metric t for this data transfer is computed by taking for every pair of packets p_i,p_j S, where p_i arrives before p_j, the maximum of (i j). In the above example, t = 3, which is determined by p₅ and p₂

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

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(nlogn) 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

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

Lets 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 _{36 = 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 recurrence relation for solving the problem using dynamic programming.
• A pseudocode for solving the problem using your recurrence relation.
• A brief argument of why you think your algorithm will produce a correct answer.
• The description of the dynamic programming table (or data structure, if any) thatyou will be using.
• Time complexity analysis of your dynamic programming.

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⁹), then you will get a bonus.

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