ALGORITHMS Take Home Solution

Description

• Problem De nition

In this assignment, you will implement a solution to the following problem where input is a graph. Given a connected positive weighted undirected graph G(V; E) with vertices w₁; w₂ 2 V and d₁; :::; d_k 2 V where k is always even, nd the shortest total length of paths that connect k=2 d vertices to w₁ and remaining k=2 d vertices to w₂. The solution is the total length of the paths and the assignments between w_j ’s and d_i’s. If there is more than one solution, one of the assignments is enough as a result.

Informally, you have two warehouses w₁ and w₂. Each warehouse have k=2 trucks that can only carry the load for one city and you have k destination cities d₁; :::d_k . The goal is to nd the shortest possible total distance the trucks will travel and the assignment of destination cities to warehouses in this optimal solution.

Note that the total travel cost is computed by simply summing the lengths of the paths taken in-dividually by each truck. Therefore, you shall ignore path overlaps across the pairs of warehouse and destination found by your algorithm

• Speci cations

2.1 Libraries and Complexity

You can use the C++ standard library in your program and nothing else. The expected complexity of your solution is O((E + V ) log(V )).

2.2 Input Speci cations

Your program will get a le name as parameter. The le for the graph shown in gure 1 is as follows:

465000000000

1500000004645

036000020000

043000200000

00490000000

001304600000

00004500000

Figure 1: Sample input visualization

The rst line of the le gives the total number of cities n, including warehouses and the destinations. The second line is the number of destinations. The third line is the indexes for two warehouses. The fourth line gives the indexes for the destination cities. Both indexes are zero based. Rest of the le represents an n by n matrix that represents the distances between cities, where 0 means no connection. You can assume there will be at most 10.000 cities.

2.3 Output Speci cations

Your program should write the result to the standard output. First line must be the total length of the paths for a given input. The following lines must show the assignments of warehouses to each city in ascending order.

226

• 5

4 7

6 5

8 7

2.4 Execution

Your make le must generate the executable runTH . Your program will be run with the following com-mand.

./runTH fileName

2.5 Submission

Your submission should be a tar le, only containing your code and the Makefile to compile your code in its root. You can do this with a command such as this: tar -cvf TH.tar *.cpp *.hpp makefile

• Regulations

• 1. Programming Language: You must code your program in C++. Your submission will be compiled with g++ on department lab machines.

• 2. Late Submission: There is no late submission.

• 3. Evaluation: Black box evaluation method is going to be used, therefore you need to be careful about input/output speci cations. You should not print any unnecessary characters and/or white spaces. Missing make les will be evaluated as compile errors. Wrong executable names or wrong parameterization will be evaluated as if no output is produced.

• 4. Cheating: In case of cheating, the university regulations will be applied.

3