This assignment assesses your ability to design an algorithm and analyze it. It also reinforces the expectation for formal mathematical notation. This assignment will help you develop the skills needed throughout the remainder of this course.

Carefully read the description below; it is directly linked to the topic and the assigned readings. You are expected to prepare professionally written answers; use rigorous mathematical notation; and include a cover page, detailed explanations, justifications for all your claims, and references in APA style.

Problem: Consider a hallway in a building, with N equally sized rooms, numbered 1,..., N. Several meetings are planned, which require different numbers of adjacent rooms. You are given a list of meeting requests with the number of rooms need for each. The requests are represented by the array r[1, ..., k]. For example, meeting j requires r[j] adjacent rooms. You are offered a programmatic tool, which requires n steps to partition a set of n rooms, to accommodate two meeting requests of sizes s₁ and s₂, where s₁+s₂ = N.

Design an algorithm that receives a set of meeting requests s₁, s₂, ..., etc., and calculates the rooms allocations in the least number of steps. Formally prove that the algorithm is correct and that the solution it provides requires the lowest cost (in computational steps). Illustrate your solution with a concrete example.