-
Notifications
You must be signed in to change notification settings - Fork 3
/
index.html
107 lines (107 loc) · 10.3 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
<!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: PA5: Final Exam Scheduling</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: PA5: Final Exam Scheduling</h1>
</header>
<figure style="float:right;width:40%;margin-left:20px">
<a href="graph-before.svg"><img src="graph-before.svg"></a>
<figcaption style="text-align:center">
The constructed graph to run max flow on. The classes and rooms are sorted by size, with the smaller classes and rooms on the bottom.
</figcaption>
</figure>
<p>It’s always difficult to schedule final exams for all the classes at UVA. Instead of the current method of scheduling final exams – based on the time the class meets – UVA wants to see if they can create a schedule that, for a given number of rooms, exam times, and classes, one can find a schedule that makes this all work.</p>
<p>But there is a complication. There needs to be faculty members present at each exam to proctor it. Under this new method, it doesn’t have to be the faculty member who teaches the class, just any faculty member. But, in an effort to balance the workload, no faculty member can have too many exams to proctor.</p>
<p><strong>Part 1: Reduce to Max Flow:</strong> You will be given the number of classes (<span class="math inline"><em>c</em></span>), a number of rooms (<span class="math inline"><em>r</em></span>), a number of times (<span class="math inline"><em>t</em></span>), and a number of proctors (<span class="math inline"><em>p</em></span>). For the sake of this assignment, these entities are all 0-index integers (so if <span class="math inline"><em>c</em> = 7</span>, then the classes are just 0 through 6). To solve this problem, you will have to construct a graph such as the upper image on the right. In that image, there are five sets of bipartite “ranges”. With the exception of one of those sets, all edges have capacity set to 1.</p>
<ol type="1">
<li>From the start (<span class="math inline"><em>s</em>′</span>) to each of the classes: this represents that there is only one exam per class (if a class had multiple exams, then the capacity would be set higher, but that is not part of this assignment).</li>
<li>From the classes to the rooms: any class can fit into any room that has a sufficient capacity. Thus, the lines in this section only connect to rooms that can hold the number of students in the course. In the diagram, both the courses and the rooms are sorted by size with the smaller courses / rooms on the bottom. The course sizes will be provided in the input.</li>
<li>From the rooms to the times: any exam could potentially be at any time, so this is a complete sub-graph (every room connects to every time).</li>
<li>From the times to the proctors: this is based on the proctor’s availability, which is provided.<br />
</li>
<li>From the proctors to the terminus: to allow the max flow to complete. Each proctor has some limit of exams they can cover, so the capacity on these edges is set to that limit (5, in this example, but the actual limit varies by the input case).</li>
</ol>
<p>Once max flow is run on this updated graph, you might get something like the lower of the images to the right. In that image, the red edges have flow 1, and the green edges more more flow (proctor 3 to the terminus has capacity 3, the other two green edges have capacity 2). This graph was the result of an actual solution for this assignment.</p>
<figure style="float:right;width:40%;margin-left:20px">
<a href="graph-after.svg"><img src="graph-after.svg"></a>
<figcaption style="text-align:center">
The result of running max flow on the graph. The classes and rooms are sorted by size, with the smaller classes and rooms on the bottom.
</figcaption>
</figure>
<p>You will need to print the max flow value (as an integer) from this part in your final output. The max flow of the graph shown is 9.</p>
<p><strong>Part 2: Extract the schedule:</strong> Once we have run max flow, we need to extract the schedule from the graph. This can be done by tracing the paths through the graph, following edges with flow – you can pick any outbound path from a given node.</p>
<p>You will need to print those paths in your final output. This part is worth fewer points than the previous part, and if you do not get to it, there is a modification of the output, and you will still get the majority of the credit for the assignment (assuming your answers are otherwise correct).</p>
<h3 id="input">Input</h3>
<p>The first line of a file will contain <span class="math inline"><em>n</em></span>, the number of test cases in that file. Each test case uses a different graph.</p>
<p>The first line of each test case will contain five positive integers: <span class="math inline"><em>c</em></span>, <span class="math inline"><em>r</em></span>, <span class="math inline"><em>t</em></span>, <span class="math inline"><em>p</em></span>, and <span class="math inline"><em>p</em><sub><em>c</em></sub></span>, space separated. The first four are the number of classes, rooms, times, and proctors, respectively. The last is the proctor capacity – how many exams they can handle. For the examples images shown here, <span class="math inline">(<em>c</em>, <em>r</em>, <em>t</em>, <em>p</em>, <em>p</em><sub><em>c</em></sub>) = (9, 5, 4, 7, 5)</span>. However, these values – including <span class="math inline"><em>p</em><sub><em>c</em></sub></span> – will vary on the input used to test your program.</p>
<p>The next line will contain <span class="math inline"><em>c</em></span> positive integers, which is the class sizes of the <span class="math inline"><em>c</em></span> courses. These will be sorted in non-descending order.</p>
<p>The next line will contain <span class="math inline"><em>r</em></span> positive integers, which is the room capacity of the <span class="math inline"><em>r</em></span> rooms. These will be sorted in non-descending order.</p>
<p>The next <span class="math inline"><em>p</em></span> lines will contain the scheduling information for the <span class="math inline"><em>p</em></span> proctors. Each of these lines will start with a positive integer <span class="math inline"><em>x</em></span> which is how many times that proctor is available for, followed by the <span class="math inline"><em>x</em></span> times the proctor is available for (space separated).</p>
<p>All values, both input and output, will fit in a 32-bit singed integer. All of the “things” referenced (classes, rooms, times, and proctors) are represented as consecutive integers indexing from 0.</p>
<p>You may assume that the provided graph is valid. You may not assume that the max flow will be equal to the number of classes. In some test cases, there will be classes that cannot have a final exam scheduled.</p>
<h3 id="output">Output</h3>
<p>The first line of the output per test case will be the (integer) max flow of the graph.</p>
<p>If you did not complete part 2, then you should print out a -1 on a second line for each test case.</p>
<p>If you did complete part 2, then the next <span class="math inline"><em>c</em></span> lines will contain their path (aka their schedule.) It will be of the form <code>1 - 2 - 3 - 0</code>, which indicates that class 1 will use room 2 at time 3 with proctor 0. These lines can print out in any order. Note that the separator between each is three characters: space, dash, space. You may also print out a single letter prefix before each, such as <code>c1 - r2 - t3 - p0</code> to indicate course, room, time, and proctor; either format is acceptable, but the ONLY letters you can use on those lines are ‘c’, ‘r’, ‘t’, and ‘p’ (upper case or lower case).</p>
<p>If a class is not assigned a room / time / proctor, then print the class number and -1: <code>4 -1</code> (or <code>c4 -1</code>).</p>
<p>There are likely going to be many max flow paths through the graph, and any correct one (meaning a valid flow of maximum value) is acceptable.</p>
<h3 id="sample-input">Sample input</h3>
<p>This input corresponds to the first graph shown above. In that image, the classes and rooms are sorted by size, with the smaller classes and rooms on the bottom of their respective column. This means that class <span class="math inline"><em>c</em><sub>0</sub></span>, the smallest class, is at the bottom of the classes column, and likewise with the room column. The number in each node corresponds to its number in the input.</p>
<p>This file is available as <a href="sample.in">sample.in</a>:</p>
<pre><code>1
9 5 4 7 5
12 20 34 57 63 63 87 153 725
18 48 72 100 850
2 0 1
1 0
2 0 2
3 0 1 2
3 1 2 3
2 2 3
2 1 3</code></pre>
<h3 id="sample-output">Sample output</h3>
<p>This output corresponds to the second graph shown above.</p>
<pre><code>9
c8 - r4 - t1 - p4
c7 - r4 - t0 - p3
c6 - r3 - t0 - p2
c5 - r2 - t2 - p3
c4 - r2 - t1 - p3
c3 - r2 - t0 - p1
c2 - r1 - t1 - p0
c1 - r1 - t0 - p0
c0 - r0 - t2 - p2</code></pre>
<p>Note that you could have eliminated the letters (‘c’, ‘r’, ‘t’, and ‘p’) in the above output.</p>
<h3 id="requirements">Requirements</h3>
<p>You are <em>required</em> to reduce this problem to a max-flow problem. You should use the networkx package for Python or the JGraphT package for Java.</p>
<ul>
<li>Networkx: <a href="https://networkx.org/">https://networkx.org/</a></li>
<li>JGraphT: <a href="https://jgrapht.org/">https://jgrapht.org/</a></li>
</ul>
<p>Your final submission should be in a file named <code>pa5.py</code> or <code>PA5.java</code>.</p>
</body>
</html>