ICS325 Analysis of Algorithms Group Assignment 3

Winter 2022

Homework Policy:

1. Students should work on group assignments in groups of preferably three people. Each group submits to CANVAS a zip file that includes their source code and their typeset report. The report must include the name of all group members. Specifically, for this assignment your zipped folder should contain two  les named assignment3.pdf, and assignment3.py. One submission from each group is sufficient.
2. The goal of the homework assignments is for you to learn solving algorithmic problems. So, I recommend spending sufficient time thinking about problems individually before discussing them with your friends.
3. You are allowed to discuss the problems with other groups, and you are allowed to use other resources, but you must cite them. Also, you must write everything in your own words, copying verbatim is plagiarism.
4. I don't know policy: you may write "I don't know" and nothing else to answer a question and receive 25 percent of the total points for that problem whereas a completely wrong answer will receive zero.
5. Algorithms should be explained in plain english. You can use pseudocodes if it helps your explanation, but the grader will not try to understand a complicated pseudocode.
6. More items might be added to this list. ©

The art exhibition organizers again!! Yes, after the successful exhibitions in Corvallis, they are trying to organize a tour of shows now. They plan to visit n towns t1; t2; : : : ; tn in this tour. They want to start the tour from t1 and end it at t1. They have a small problem though. With the very expensive art pieces in their truck they do not want to stop in between the towns to fill their gas tank. In other words, they want to recall their tanks only when they are in a town. But, they are fine taking paths that are not necessarily the shortest. For example, when going from t1 to t2, they allow themselves to pass through other towns if needed. In order to make this trip possible they are ready to change the tank of their trunk to have a larger capacity. But, they want to know the smallest possible capacity with which this trip is possible. They took the time to calculate the required gas to drive between any pair of towns. Now, they are asking us to design an algorithm that calculates the minimum required tank capacity to finish the tour from these numbers.

Formally, they give us the number of towns, n, and the gas they need to drive between any pair of them, $g_{ij}$ for all 1 $\leq$ i < j $\leq$ n whenever there is a direct road between ti and $t_j$ . In the output, they just ask for one number, the minimum capacity of the tank that allows completing the tour. Consider the examples in the following figure. The left side one is an example with three towns, in which the answer is 4; the optimal tour is t1 ! t3 ! t1 ! t2 ! t1. The right side one is an example with four towns, in which the answer is 4; the optimal tour is t1 ! t2 ! t3 ! t2 ! t4 ! t2 ! t1.

• Design an algorithm to compute the minimum required capacity of the tank, for a problem with n towns and m roads. Any algorithm with polynomial time in n and m receives the full credit for the report part. For the implementation, we try to build test cases so that any algorithm with O(mlogn) time (with a reasonable hidden constant factor) can pass them.
• Prove that your algorithm is correct, and analyze its running time.

Report (60%). In your report, include the description of your algorithms, running time analysis, and proof of correctness. Algorithms should be explained in plain english. You can use pseudocode if it helps your explanation, but the grader will not try to understand complicated pseudocode. Code (40%). Submit a python program that computes the minimum required capacity of the tank. Your program will be tested against several test cases, for correctness and efficiency. For each test case, the program will be automatically stopped after 30 seconds if it is not done in that time. In this case, the group will miss the points of that test case. Note: it is important that your output is formatted as described below, since your codes will be tested automatically. Specifically, you must implement the function "minimum tank capacity" in the following code. The code you submit will be an implementation of this procedure in a file named "assignment3.py".

Input/Output The input file composed of two lines. The first line is one integer n, with 1 $\leq$ n < 106. The second line is a list of triples (i; j; gi;j) for all the roads between towns i and j and the gas needed to drive from one to the other directly, gi;j . For the pair of towns that are not in this list you can assume that there is not direct road between them, or equivalently the gas needed to go from one to the other directly is 1. Finally, you can assume all gi;j 's are non-negative integers with value at most 106. The output file must composed of one line that contains a single integer that is the minimum required tank capacity for the organizers to finish the tour.

Sample Input (1):
3
(1,2,3),(1,3,4),(3,2,6)
Sample Output (1):
4

Sample Input (2):
4
(1,2,3),(1,3,6),(4,3,7),(4,2,4),(2,3,2)
Sample Output (2):
4

Sample Input (3):
5
(1,2,1),(2,3,1),(3,4,1),(4,5,1)
Sample
1```