缵䵻 . Name:
‘
CS 577: Introduction to Algorithms Out: 04/28/21
Final Exam Due: 05/05/21 2:25pm
Problem 1 [70 points]
There’s an outbreak of the zombie plague in the city of Algotopia, and the head theorist must determine how to best contain the plague. The city is built in an n by n grid. Luckily, the zombies aren’t able to climb walls and the city has the technology to instantly construct walls separating any two adjacent grid squares. (Squares are adjacent if they share an edge, so squares that are diagonal from each other are not adjacent. An interior square is adjacent to 4 other squares.) Once the walls are constructed, the plague will spread between any two adjacent squares as long as there isn’t a wall between them. It will only stop spreading once every infected square has either a wall or another infected square at each of its sides. At this point, the plague will be contained.
A. [40 points] The head theorist calculates that it will cost 1 dollar to erect any single wall and that the city will mmm
incur a cost of c > 0 dollars for each originally healthy square that is infected. Luckily, Algotopia already has walls surrounding its borders, remnants of past wars against the Networks Alliance. Therefore, there is no chance of the plague infecting anything outside the city grid, and you don’t have to worry about such issues.
YouaregivenannbynbinarymatrixA,whereAi,j =1ifthecorrespondinggridsquareisinitiallyinfectedwith the plague and Ai,j = 0 if the square is not infected.
Give an efficient algorithm to determine which walls to erect so as to minimize the total cost (the number of walls build plus c times the number of originally healthy squares infected). Prove your algorithm is correct and state and analyze its runtime in terms of n. You may assume that c is a small constant.
Figure 1: The grid on the left represents a possible instance of problem 1A (incomplete because it doesn’t contain cost information), and the two grids on the right represent two possible solutions. The red represents intially infected squares, the orange initially healthy squares that will get infected, and the white squares that begin and stay healthy. The dark bolded lines represent walls that are constructed. Note that the walls on the boundary of the grid already exist and do not need to be constructed.
Wisc ID:
Provide an efficient algorithm for 1A.
Page 2
Prove your algorithm for 1A is correct.
State and justify the runtime of your algorithm.
Page 3
B. [30 points] The federal government of CS-landia has gotten word that Algotopia’s border walls are actually xmnmg
virtual firewalls and will do nothing to contain the plague. Luckily, the city does have the ability to construct actual walls on the border, just as they do in the interior of the city. The federal council is worried about a pandemic and wants to be absolutely certain that the plague does not escape the city limits. The plague escaptes city limits if it can spread beyond the city grid, that is if a square on the border of the grid gets infected and the wall separating the border square from outside the city has not been built.
In addition, the federal council realizes that the head theorist’s cost function was simplistic. Infecting an originally healthy square (i, j) now incurs an arbitrary cost Ii,j corresponding to the population of square. Additionally, each wall costs a different amount to build. Let Wi,j,⇤ be the cost to build a wall on the side of square i, j indicated by ⇤, which should be a direction in {“, !, , #}. The costs will be consistent, so both ways of indicating a particular wall have the same cost. For example, Wi,j,” = Wi,j1,#.
Give an efficient algorithm to determine which walls to erect so as to minimize the total cost (the cost of building walls plus the cost for infecting originally healthy squares), while ensuring that plague doesn’t escape the city. Prove your algorithm is correct and state and analyze its runtime in terms of n. You may assume that the costs W and I are bounded by a constant.
Figure 2: The grid on the left represents a possible instance of problem 1B (incomplete because it doesn’t contain cost information), and the two grids on the right represent two possible solutions. The red represents intially infected squares, the orange initially healthy squares that will get infected, and the white squares that begin and stay healthy. The dark bolded lines represent walls that are constructed. Note that walls on the boundary of the grid do not initially exist and must be constucted.
Page 4
Provide an algorithm for 1B. This will likely be a modification of your algorithm for 1A.
Page 5
Prove your algorithm for 1B is correct.
State and justify the runtime of your algorithm.
Page 6
Problem 2燃[50 points]
You decided to enter the event planning business to avoid having to solve hard computational problems, but it turns out that you are faced with such a problem anyway. You own a venue and rent it out by the day for customers who want to host events. It is common for a an event to span multiple (possibly not consecutive) days, and it is only possible to host such an event if we rent the venue for all of those days. It is not possible to host multiple events on a single day, and, to make planning easier, you are only worried about bookings that stretch out to at most D days in the future. Because you are new in the business, your objective is to be able to host as many events as possible during the D days of operation. Unfortunately, it turns out that (the decision version of) this problem is NP-complete, and this is what you are asked to prove.
Formally, the problem is defined as follows: you are given as input the total number of days D, n events E1, . . . , En and an integer k. Each Ei is a subset of {1, 2, . . . , D} indicating the days on which that event takes place. Your objective is to decide whether it is possible to schedule at least k events such that if events Ei and Ej are scheduled, then Ei \ Ej = ;. Call this problem EVENTPLANNING.
A. [10 points] Prove that EVENTPLANNING 2 NP. mm
Page 7
B.此[20 points] Describe an NP-complete problem A to reduce from and a polynomial-time mapping reduction from mmm
A to EVENTPLANNING.
Page 8
C. [20 points] Argue that the reduction from part (B) is correct. mmn
Page 9
Mmhs
Problem 3 [30 points]
Tired of not being able to efficiently compute a solution for the event planning problem from Problem 2, you decided to strike a deal with your competitors. Now, whenever a customer wants to host an event with your organization you are able to offer your venue for a day and the competitors’ venues for the others. Also, because the partnership was your idea, you get first pick of the day you are going to rent out your venue for each event. Ultimately, the effect is that now you are able to host an event by renting your venue for just a single day, even if it spans two or more days. Thankfully, it turns out that this change is enough to make the problem tractable again.
Formally, the problem is defined as follows: you are given as input the total number of days D and n events E1, . . . , En. Each Ei is a subset of {1, 2, . . . , D} indicating the days on which that event takes place. Your objective is to maximize the number of events out of E1 , . . . , En that are scheduled, such that you only schedule an event Ei on day d if d 2 Ei, and you schedule at most one event per day. In this setting, scheduling an event Ei means renting out the venue for at least one day out of the ones in Ei. Describe an algorithm for this problem, prove that it is correct and analyze its runtime. Your algorithm should run in time polynomial in n and D.
Page 10