$(15$ marks$)$ In some computer systems, RAM is separated into sections. Usually

one section is used for variables, another for function call parameters, etc. In

this problem there will be two sections: variables and function call parameters.

Variables expand from one area of the RAM and function call parameters from the

other end $($see diagram$).$

The amount of RAM is fixed. Think of RAM as one large static array, with one

end used for some purpose $($in this case variables$),$ and other end being used for a

different purpose $($in this case function call parameters$).$ The memory allocations

for these $$grow$$ towards each other. If the two ends ever meet, then the memory

has been exhausted. As you may have noticed, memory allocation and removal

behave like a Stack.

$($a$)$ In this question you will partially simulate this behaviour for the Microvision

handheld game console. The requirements for this simulation:

$$ The RAM size is $64$ bytes.

$$ Allocations at the $$bottom$$ are for variables; $$top$$ are for parameters, just

like in the diagram.

$$ When testing, you can add $($random$)$ characters to represent variables$/-$

parameters. You may assume each allocation is $1$ byte $($fixed size$).$

You will implement this using one $1-$D array, which combines two stacks. You

will need to implement the following operations:

$$ isEmpty $($for each RAM area$)$

$$ size $($for each RAM area$)$

$$ allocate $($add an item to the proper RAM area, if space is available$)$

$$ free $($for each RAM area$)$

$$ top $($for each RAM area$)$

Do not use the built$-$in append or pop function, as these can change the size

of the array.

$($b$)$ Fully test all operations in a Python main program, including all corner cases

$($i$.$e$.$ test for memory exhaustion$).$

$($c$)$ Give the time complexity for each of the operations, with justifications.

$3.(35$ marks$)$ In more advanced computers with variable amounts of RAM, allocating

variables is not as simple as in the first question. A common approach for such

systems is keep a linked list of allocations in a memory pool, and upon de$-$allocation

to coalesce $($combine$)$ the freed space back into the free part of the pool.

See the following illustration:

In this example, we start with $1000$blocks$$ of RAM, and then perform a sequence

of allocations and free$$s; the resultant linked list is shown after each operation has

been performed.

$($a$)$ In this question, you will partially simulate the behaviour of such a memory

allocator. A partial Python class has already been provided, along with a

sample input text file for the illustration above. Your solution must implement

the following requirements:

$$ Allocations must happen in the smallest available block that can hold

that memory. So if you want to allocate $5$ blocks, and there are several

places to allocate that space, it must be from the smallest area. In the

event of a tie, it should be the first location in the linked list.

When an allocation happens and there is more space than needed, the

block splits into two $$ the memory being allocated and the remaining free

memory $($see Allocate $4$ e for smallest block and the split$).$

$$ De$-$allocations $($free$$s$)$ must coalesce adjacent blocks that are already free.

Note that there are two possibilities:

$$ An area is free to the left $($or the right$)$: In this case, the area to

remove as well as the adjacent area will coalesce into one area, with

the free space being a sum of the two.

$$ Areas are free both to the left and right: In this case, all three areas

should coalesce into one, with the free space being a sum of the three

$($see $$Free d$$ for an example of this$).$

Complete the Python class in the attached file MemoryAlloc.py$.$ Study the

given code, and read$/$understand the comments. Remember that the markers

will use different test files, so your code must be robust and consider all use

cases.

$($b$)$ Create a few test files. Note that the markers will be using several test files,

so your code must be general and work in all cases.

$($c$)$ Compare both the time and space complexity of this implementation with the

solution from Question $2.$