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.

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.