Problem: A mayor of a city wants to revamp the industrial area, by demolishing some of the industrial buildings which contributes the most pollution, within a condition (see below). Justify the method of choosing which building to be demolished, by finding the maximum amount of pollution that can be reduced by destroying these buildings. Condition: If a building in a row is chosen to be demolished, the two buildings adjacent to it cannot be chosen. Example: B C D E G For example, if building D is chosen to be demolished, buildings C, B, E, and F cannot be chosen. Questions: Part A - Brute Force 1. What is your interpretation of this problem? What information do you think we need? Explain concisely. 2. Is it similar to any specific algorithmic problem we've learnt? What is it? 3. Explain concisely in plain English using your own words, the (recursive) brute-force approach to solve this problem. Draw any diagram/picture to help explaining your point. 4. What is the input for your brute-force algorithm? 5. What is the output for your brute-force algorithm? 6. Write a pseudocode for your recursive brute-force algorithm. 7. Visualize the recursive brute-force approach through the execution/recursion tree. 8. Is there any optimal substructure? Which part? 9. Is there any overlapping subproblem? Which part? You can show through your execution/recursion tree. Part B - Dynamic Programming 10. How can you make your algorithm more efficient by turning it into a recursive dynamic programming? Explain concisely in plain English using your own words. Draw any diagram/picture to help explaining your point. 11. What is(are) the base case(s)? 12. What is the formula/recurrence relation? 13. Write a pseudocode for your recursive dynamic programming algorithm for this problem. 14. Visualize your algorithm through the execution/recursion tree. 15. Compare it with the brute-force's execution/recursion tree. Have the overlapping subproblems been reduced? Yes/No 16. Based on your pseudocode, write a program code, in your preferred programming language (mention what language it is). a. It must have easy-to-understand comments and variable names etc., for the people who read your code. b. Prepare one test case (a set of input and output), to test your code. C. Submit your code and the snapshot(s) of the results. 17. How do you think we can turn your recursive dynamic programming into an iterative dynamic programming algorithm? Explain briefly. Part C-Extended problem Consider the same problem, but what if the mayor needs to consider the demolishing cost? Let's say the mayor can do this demolishing project, within the budget capacity W. You can demolish as many buildings within the condition and the budget capacity. Each building has its own demolishing cost. Find the maximum amount of pollution that can be reduced, within the condition and the budget capacity. 18. What are the input(s) and output? 19. How can you solve this with dynamic programming? Explain briefly in your own plain English words and diagram. 20. What are the recurrence relation and base cases? 21. Cite/provide all references you refer to when answering this Final Assessment 1 for all parts (link, the name(s) of people you refer to if any, book, etc.)