CSC373 – Problem Set 4
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 18, 2016 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 THREE 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 Proof Cleanup
[4 marks] Complete the proof on slide 11 of lecture 7 by showing that the four requirements are met.
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 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:
(Larry, 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 provided pair (a, b), then a and b cannot communicate, and no network cable can even 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 answer for the above instance is 3.
[5 marks] 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 Computer 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 via parallel port (look it up, kids!), 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 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. (n can be big, like 50. Who wouldn’t want that laptop?) You have m devices that you’d like to use at the same time with the laptop. 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 we can connect is 4 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
The available adapters 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
The available adapters are
parallel->Ethernet
parallel->SD slot
[5 marks] Describe and prove correctness of an algorithm, based on maximum-flow, to solve this problem. Hint: in addition to maximum-flow, one solution to this problem also uses another graph algorithm that we have studied.