Imagine that you are a security officer and a guest president’s visit to your country is planned. Your responsibility is to decide about the allocation of watchmen to junction points of a single-story building having several hallways. Each watchman situated at a hallway junction is responsible for watching all the hallways connected to the junction point and informing you about a possible insecure event that may happen. In order to minimize your government’s expenditure, you need to achieve your allocation task by assigning a minimum number of watchmen to the junction locations. 

i. Design an algorithm that aims to solve the watchman-allocation-for-security problem efficiently. Write down a report that explains each step of your design solution, clearly. 

ii. Implement the algorithm that you designed in part(i). The format of your sample input and output is given below. Do NOT hard-code the sample problem input instance below but read the sample input either from the screen or from a text file. 

iii. Analyze your algorithm’s time complexity.

SAMPLE INPUT: 11 // Number of hallway junctions of the single-story building (????)

2 4 5 // The junction IDs to which Junction #1 is connected through a hallway

1 // The junction IDs to which Junction #2 is connected through a hallway

5 6 // The junction IDs to which Junction #3 is connected through a hallway

1 5 8 // The junction IDs to which Junction #4 is connected through a hallway

1 3 4 // The junction IDs to which Junction #5 is connected through a hallway

3 7 10 // The junction IDs to which Junction #6 is connected through a hallway

6 11 // The junction IDs to which Junction #7 is connected through a hallway

4 9 // The junction IDs to which Junction #8 is connected through a hallway

8 10 // The junction IDs to which Junction #9 is connected through a hallway 6

9 // The junction IDs to which Junction #10 is connected through a hallway

7 // The junction IDs to which Junction #11 is connected through a hallway

SAMPLE OUTPUT:

 As a possible solution, we need 6 watchmen to be allocated to junctions: 1, 3, 4, 6, 7, 9

Answer rating: 100% (QA)

i Algorithm Design The watchmanallocationforsecurity problem can be solved efficiently by using a greedy algorithm that assigns watchmen to junction p... View the full answer