Answer Happy

Watchman-Allocation-For-Security Problem: (100 pts) Imagine that you are a security officer and a guest president's visit to your country is planned. Your responsibility is to decide about allocation of watchmans to junction points of a single storey building having several hallways. Each watchman situated at an hallway junction is responsible from watching all the hallways connected to the junction point and inform you about possible insecure event that may happen. In order to minimize your government's expenditure, you need to achieve your allocation task by assigning minimum number of watchmans to the junction locations. i. il. 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 (30 points) Implement the algorithm that you designed in part(1). 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 (60 points) Analyze your algorithm's time complexity (10 points) iii. SAMPLE INPUT: 11 245 1 56 158 134 // Number of hallway junctions of the single storey building (n) // The junction IDs to which Junction 1 is connected through an hallway // The junction IDs to which Junction #2 is connected through an hallway // The junction IDs to which Junction #3 is connected through an hallway // The junction IDs to which Junction 14 is connected through an hallway // The junction is to which Junction 15 is connected through an hallway // The junction 10s to which function 16 is connected through an hallway // The junction is to which Junction 7 is connected through an hallway // The junction is to which Junction u8 is connected through an hallway // The junction is to which Junction 19 is connected through an hallway // The junction IDs to which Junction 810 is connected through an hallway // The junction IDs to which Junction 811 is connected through an hallway 37 10 611 49 8 10 69 7 SAMPLE OUTPUT: As a possible solution, we need 6 watchman to be allocated to functions: 1, 3, 4, 6, 7,9