-
Notifications
You must be signed in to change notification settings - Fork 3
/
Copy pathindex.html
148 lines (148 loc) · 9.69 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" lang="" xml:lang="">
<head>
<meta charset="utf-8" />
<meta name="generator" content="pandoc" />
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes" />
<title>DSA2: PA1: FedUps</title>
<style>
code{white-space: pre-wrap;}
span.smallcaps{font-variant: small-caps;}
div.columns{display: flex; gap: min(4vw, 1.5em);}
div.column{flex: auto; overflow-x: auto;}
div.hanging-indent{margin-left: 1.5em; text-indent: -1.5em;}
/* The extra [class] is a hack that increases specificity enough to
override a similar rule in reveal.js */
ul.task-list[class]{list-style: none;}
ul.task-list li input[type="checkbox"] {
font-size: inherit;
width: 0.8em;
margin: 0 0.8em 0.2em -1.6em;
vertical-align: middle;
}
.display.math{display: block; text-align: center; margin: 0.5rem auto;}
</style>
<link rel="stylesheet" href="../../markdown.css" />
</head>
<body>
<header id="title-block-header">
<h1 class="title">DSA2: PA1: FedUps</h1>
</header>
<h3 id="description">Description</h3>
<p>Package delivery isn’t what it used to be. With a rise in premium package delivery services, FedEx and UPS have now created a new tier in their delivery service options: FedUps sub-premium delivery subscription service. Subscribers to FedUps will receive a small discount on their shipping costs, but they must agree to receive only the worst customer treatment and delivery times for all packages. One example of this intentionally poor treatment is that FedUps will now send your packages to you via routes that are not guaranteed to be the most efficient. Instead, FedEx and UPS will try to use FedUps orders to do their best to minimize the excess capacity of all of their vehicles.</p>
<p>Your algorithm will receive two weighted graphs (lists of edges) as input. The first graph will represent the total transportation capacities of their vehicles. The nodes represent cities, edges represent trucks traveling between cities, and the weight of the edge represents the maximum weight that can be carried by each truck. The second graph will represent the remaining available capacities on all vehicles. The same nodes and edges will be present as for the first graph, but now the edges represent how much more cargo each truck can carry.</p>
<p>Your goal will be to write an algorithm which finds the path from a given start city to a destination city which <em>minimizes the sum of load percentages</em> across the nodes in the graph. Note that the number of trucks is irrelevant, we only care to <em>minimizes the sum of load percentages</em>. At-capacity trucks may not be used, since FedUps could not add a package to that truck.</p>
<h3 id="changelog">Changelog</h3>
<ul>
<li>Tue, 9/24: To make this assignment more feasible, we are changing the goal: instead of “maximizes the percentage of available capacity” we are “minimizes the sum of load percentages”. Note that what you have to minimize is the load percentage (how much space is taken), but what is given to you in the problem is the available space (how much space is left). Also, another example test cases was added.</li>
<li>Sun, 9/15: The original graph had an error: the edge from 0->3 should be “0/60” (as now shown below); the example.txt and the I/O output below was fixed the next day</li>
</ul>
<h3 id="input">Input</h3>
<p>Your input will be 5 parameters containing the following information:</p>
<ul>
<li><code>numCitites</code> - the number of total cities; the cities are integers from 0 to <span class="math inline"><em>n</em><em>u</em><em>m</em><em>C</em><em>i</em><em>t</em><em>i</em><em>e</em><em>s</em> − 1</span>.</li>
<li><code>start</code> - the start city.</li>
<li><code>end</code> - the destination city.</li>
<li><code>capacities</code> - a list of the total capacities of each of the trucks, given as a list of strings. Each string in the list contains a comma-separated list of integer values: the truck’s starting city, the truck’s destination city, and the truck’s total carrying capacity.</li>
<li><code>available</code> - a list of available capacity of each of the trucks, given as a list of strings. Each string in the list contains a comma-separated list of integer values: the truck’s starting city, the truck’s destination city, and the truck’s available capacity.</li>
</ul>
<p>The provided skeleton code, below, already reads in the input from an <code>example.txt</code> file.</p>
<h3 id="output">Output</h3>
<p>Your output will be a list of integers indicating the sequence of cities which starts in the start city and ends in the destination city, that also <em>minimizes the sum of load percentages</em>. The main method provided will print this list one city per line. An example output is given below.</p>
<h3 id="running-time-requirements">Running Time Requirements</h3>
<p>The worst-case asymptotic running time of your program should belong to <span class="math inline"><em>O</em>(<em>c</em>⋅<em>t</em>)</span>, where <span class="math inline"><em>c</em></span> is the number of cities and <span class="math inline"><em>t</em></span> is the number of trucks.</p>
<h3 id="example">Example</h3>
<p><img src="pa1-graph.jpg" style="float:right" /></p>
<p>Consider the graph to the right. The start is at node 0, and the end is at node 3.</p>
<p>In this example, there are three paths from the start node to the end node. The correct path your algorithm should return would be [0,2,3].</p>
<ul>
<li>The edge [0,3] is at capacity (has 0 available space), so it cannot be used.</li>
<li>The path [0,1,4,3] has available capacity 16/40 (40%) on each of the three segments, or 40%. The sum of these is 120%/</li>
<li>The path [0,2,3] has available capacity 60/100 (60%) for the path from 0-2, and 40/100 (40%) for the path from 2-3. This sums to 100%.</li>
</ul>
<p>As the third path <em>minimizes the sum of load percentages</em>, it would be the output path.</p>
<p>The actual output would be:</p>
<pre><code>0
2
3</code></pre>
<p>If we made one graph change – changing the available capacity of the (0,3) edge to 60 (so there is a lot of available space on that truck), then the output would be:</p>
<pre><code>0
3</code></pre>
<p><br clear='all'></p>
<h3 id="example-input">Example Input</h3>
<ul>
<li><code>numCities = 5</code>
<ul>
<li>The nodes are all integers, indexed from 0</li>
</ul></li>
<li><code>start = 0</code></li>
<li><code>end = 3</code></li>
<li><code>capacities</code> the list:</li>
</ul>
<pre><code>0,1,40
0,2,100
0,3,60
1,4,40
2,3,100
4,3,40</code></pre>
<ul>
<li><code>available</code> the list:</li>
</ul>
<pre><code>0,1,16
0,2,60
0,3,0
1,4,16
2,3,40</code></pre>
<p>The exact input would be the following; this is available in the <a href="example.txt">example.txt</a> file.</p>
<pre><code>5
0
3
0,1,40
0,2,100
0,3,60
1,4,40
2,3,100
4,3,40
---
0,1,16
0,2,60
0,3,0
1,4,16
2,3,40
4,3,16</code></pre>
<h3 id="example-output">Example Output</h3>
<p>The exact output would be:</p>
<pre><code>0
2
3</code></pre>
<h3 id="submission-requirements">Submission Requirements</h3>
<ul>
<li>Your algorithm must be written in Python 3.10.12 or Java 21.0.4 (OpenJDK)</li>
<li>You must download the appropriate wrapper code based on the language you choose: <code>Main.py</code>, <code>FedUps.py</code>, and <code>Graph.py</code> for Python; <code>Main.java</code>, <code>FedUps.java</code>, and <code>Graph.java</code> for Java.
<ul>
<li>Java files: <a href="FedUps.java.html">FedUps.java</a> (<a href="FedUps.java">src</a>), <a href="Graph.java.html">Graph.java</a> (<a href="Graph.java">src</a>), and <a href="Main.java.html">Main.java</a> (<a href="Main.java">src</a>)</li>
<li>Python files: <a href="FedUps.py.html">FedUps.py</a> (<a href="FedUps.py">src</a>), <a href="Graph.py.html">Graph.py</a> (<a href="Graph.py">src</a>), and <a href="Main.py.html">Main.py</a> (<a href="Main.py">src</a>)</li>
<li>For both: <a href="example.txt">example.txt</a></li>
</ul></li>
<li>Implement the <code>compute()</code> method in the <code>FedUps</code> class. The <code>compute()</code> method should execute the entirety of your algorithm and return the list of cities in the path.</li>
<li>Implement the <code>Graph</code> class using an Adjacency List graph implementation. You should then use this in your <code>FedUps</code> class.</li>
<li>You <em>may</em> modify the <code>Main.java</code> or <code>main.py</code> files to test your algorithm, but they <strong>will not</strong> be used during grading.</li>
<li>You must submit your {<code>FedUps.java</code> and <code>Graph.java</code>} or {<code>FedUps.py</code> and <code>Graph.py</code>} files on Gradescope. Do <strong>not</strong> submit <code>Main.java</code>, <code>main.py</code>, or any test files.</li>
<li>A few other notes:
<ul>
<li>Your code will be run as:
<ul>
<li><code>python Main.py</code> or <code>python3 Main.py</code> for Python</li>
<li><code>javac *.java && java Main</code> for Java</li>
</ul></li>
<li>Any and all source code must be in the two files that you submit (FedUps.py/java and Graph.py/java)</li>
<li>You may <strong>not</strong> use any graph packages for this assignment.</li>
<li>Please note that you are responsible for analyzing the running time of any algorithm you use and ensuring that they satisfy the runtime requirements for this assignment.</li>
</ul></li>
</ul>
<h3 id="rules-on-collaboration-and-outside-sources">Rules on Collaboration and Outside Sources</h3>
<p>You must follow the rules about Collaboration and Outside Sources <a href="https://uva-cs.github.io/dsa2/syllabus.html#honesty-and-collaboration">in the syllabus</a>.</p>
<h3 id="use-of-generative-ai">Use of Generative AI</h3>
<p>For PA1, you are not allowed to use generative AI tools to help you solve this problem.</p>
</body>
</html>