CMPT360- Assignment 2 Solved

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

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