CENG ALGORITHMS Take Home Solution

    • 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 w1; w2 2 V and d1; :::; dk 2 V where k is always even, nd the shortest total length of paths that connect k=2 d vertices to w1 and remaining k=2 d vertices to w2. The solution is the total length of the paths and the assignments between wj ’s and di’s. If there is more than one solution, one of the assignments is enough as a result.

Informally, you have two warehouses w1 and w2. Each warehouse have k=2 trucks that can only carry the load for one city and you have k destination cities d1; :::dk . 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:

10








4








5
7







1
4
6 8






0
43
0
46150
0 0

0 0

43
0
0
50 0
36
43
0
0
0
0
0
0 0
0 0
0
49 13
0



1

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

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