CSC373 – Problem Set 3
To avoid suspicions of plagiarism: at the beginning of your submission, clearly state any resources (people, print,
electronic) outside of your group, the course notes, and the course staff, that you consulted.
Problem Set: due November 15, 2021 22:00
Answer each question completely, always justifying your claims and reasoning. Your solution will be graded not only on
correctness, but also on clarity.
Answers that are technically correct that are hard to understand will not receive full marks. Mark values for each question
are contained in the [square brackets].
You may work in groups of up to TWO to complete these questions.
Please be concise and accurate in your responses. Short, accurate algorithmic descriptions are worth more than long, vague
or unnecessarily complicated explanations.
1 Finishing a Proof
[2] See Lecture 7, slide 8. Prove that augmenting along a path maintains the conservation constraint. (Hint: for vertex v on
the augmenting path, there are four cases, because the edge that enters v can be a forward or backward edge, and the edge
that leaves v can be a forward or backward edge.)
2 Island Network
On the new island of Dan Cayman live two types of people: students and professors. Each person lives in their own house,
with their own computer, but right now there are no network cables on the island, so no one can communicate with anyone
else. (Why don’t people just go outside and walk to other people’s houses to communicate? Well, that’s because everyone
on the island is a lazy computer scientist.)
We are provided in the input a list of pairs of the form (professor, student), indicating which professors can be paired up
with which students for learning computer science. For example, we might get input like this:
(Bogdan, X)
(Dan, X)
(Arnold, X)
(Arnold, Y)
where I use X and Y for students’ names instead of picking on two real students. You can assume that each student and each
professor shows up in such a list at least once.
If we run a network cable from person a’s house to person b’s house, then a and b can communicate. If there is no pair (a, b)
in the provided input, then no network cable can be run between their houses.
Given m students, n professors, and p (professor, student) pairs, the goal is that each student be able to communicate with
at least one professor and each professor be able to communicate with at least one student, and to run the fewest network
cables to make this possible. The minimum number of network cables for the above instance is 3.
[5] Describe and prove correctness of an algorithm, based on maximum-flow, to solve this problem. Hint: study the edge-cover
and vertex-cover problems; what you learn there will be useful for your solution.
3 Campus Construction
The University of Toronloo is planning on constructing a new campus. The planning committee has already found a suitable
land for the campus. This land is in the shape of a rectangular grid with n rows and m columns.
At this moment, each cell of this land is either suitable for constructing buildings (these are the “buildable cells”) or is a grass
cell. It’s possible to convert a buildable cell to a grass cell for a cost of A dollars and to convert a grass cell to a buildable
cell for B dollars.
The committee have already come up with a strategy. They’re planning to spend some time converting cells. After that,
they’ll put up buildings on all the buildable cells. To do so, they’ll also need to pay C dollars for every pair of adjacent cells
of different types (this is to put up a wall separating buildings from the grass area). Additionally, they’ve decided that the
outermost layer of the grid (the cells on the border of the grid) must all be grass cells in the end.
The committee don’t care much about the final layout of the campus. In fact, they’re happy with any layout so long as the
total cost of constructing the buildings is minimized (as weird as it may be, they’re even fine with not having any buildable
cells at all if that minimizes the total cost). Note that the only construction costs are the ones described above. In particular,
if two buildable cells share an edge, there’s no additional cost for separating them.
[5] Help the committee by describing and proving the correctness of an algorithm for finding the minimum cost of constructing
the campus.
Example: Let’s say A = 1, B = 2, C = 4 and the initial layout of the grid is
100010
000
(where 0 represents a grass cell and 1
represents a buildable cell).
First of all, the initial layout is invalid since one of the edge cells is a buildable cell. So we need to pay A dollars to convert
that cell to a grass cell.
After the conversion, the layout will be
000010
000
. This is a valid layout and we could use it for a total cost of A + 4C = 17
dollars. However, if we convert the middle cell to a grass cell by paying another A dollars, we obtain the grid
000000
000
for a
total cost of 2A = 2 dollars.
Programming Question
The best way to learn a data structure or an algorithm is to code it up. In some problem sets, we will have a programming
exercise for which you will be asked to write some code and submit it. You may also be asked to include a write-up about
your code in the PDF/TEXfile that you submit. Make sure to maintain your academic integrity carefully, and protect
your own work. The code you submit will be checked for plagiarism. It is much better to take the hit on a lower mark than
risking much worse consequences by committing an academic offence.
4 Laptop Peripherals
A laptop has lots of different kinds of ports: USB, 3.5mm audio, HDMI, SD slot, Ethernet, and so on. But sometimes you
have a device that you want to use whose required port is not on the laptop. For example, maybe you have an old printer
that connects using a parallel port, but there’s no parallel port on your laptop. In that case, you’d buy an adapter that
converts from parallel port to, for example, USB. You’d then connect the printer to the adapter and the adapter to the USB
port on the laptop.
Or maybe it takes multiple adapters to get your device to work. Imagine that a parallel port → USB port adapter is not
available. Then, for that same printer, you might need a parallel port → serial port adapter, and then a serial port → USB
adapter.
Your laptop has n ports, each of some specified kind. (Real laptops are boring and have only a small number of ports, but
here n can be big.) Multiple ports of the same kind are allowed.
You have m devices; you’d like to use as many of them as possible at the same time. For each device, we are given the kind
of port that it requires. We also have p types of adapters available; we can use as many of each type of adapter as we wish.
The goal is to report the maximum number of devices that can be used with the laptop at the same time.
Here’s an example where the maximum number of devices that we can connect is 4:
Laptop ports are
USB
3.5mm audio
SD slot
Ethernet
Devices are
scanner, USB
mouse, USB
keyboard, USB
headphones, 3.5mm audio
printer, parallel
Available adapter types are
USB->parallel
parallel->Ethernet
parallel->SD slot
Here’s a different example where we can connect a maximum of only 3 devices:
Laptop ports are
USB
3.5mm audio
SD slot
Ethernet
Devices are
scanner, USB
mouse, USB
keyboard, USB
headphones, 3.5mm audio
printer, parallel
Available adapter types are
parallel->Ethernet
parallel->SD slot
[5] Implement the function max_devices in the starter code to compute the maximum number of devices. Refer to the starter
code for input parameters and return value.
Requirements:
� Your code must be written in Python 3, and the filename must be peripherals.py.
� We will grade only the max_devices function; please do not change its signature in the starter code. You may include
as many helper functions as you wish.
� For each test case that your code is tested on, your code must run within 5x the time taken by our solution. Otherwise,
your code will be considered to have timed out.
Notes:
� Device and port names will be non-empty strings.
� There may be multiple ports on the laptop with the same name (e.g. you can have multiple USB ports).
� There may be multiple adapters of the same type that convert one port to another (though One is all you need as you
have an infinite supply of each).
� An adapter may convert a port to that same port (people will make anything these days!).
� Don’t make unnecessary assumptions about valid inputs.