Trying to teach a high school student Dynamic Memory Allocation - what are the best ways to do so?

Question

Copied from stack overflow due to feedback

So I want to teach someone how to do dynamic memory allocation using the block padding model. What that means is every memory block is prefixed and postfixed with 4 bytes holding the length of the block in bytes along with a bit (held in the leftmost bit as that one should never get used) to denote whether the block is free or allocated.

Everything in the dynamic memory allocation involves the manipulation of the padding of the blocks which I tend to think of as nodes in a doubly linked list. It's technically not quite the same but it is enough to make a fairly decent comparison in mentality and the operations used.

I'm going to be working on a project with a much younger high school kid with basic programming knowledge in C++ and Java (based on what he claims, anyway). Basically his teacher knows his next year teacher and they are letting him do some kind of programming over the summer with anyone the student chooses (I got the honor of being chosen).

Anyways, the solution i determined to accomplish something in a pretty clunky programming language (Game Maker and that's because it's something we can do gamedev in) with a broken object/pointer interface is to simply implement structs by using an array and acting as if it were the heap space. So hence, we're implementing the DMA algorithms to act on array indices. This isn't really hard for me to do and I probably have half-decent code somewhere in my files that would suit our interests.

However, I want to try to give the other guy a chance to do it, since it is one of the pivotal subsystems for the program. So that leads to the final question:

How does one explain the concept of dynamic memory allocation and how to code the functions to do it without relying upon pointers and linked lists as concepts to make comparisons to?

I was thinking of maybe making some problem sets with answers and steps to demonstrate the allocator's actions on an array but I think that might be overkill considering we should get working right away and not waste too much time. Are they any good ways to describe block padding and stuff that even a laymen might understand?

If it helps with context, I'm a third year undergrad computer science major. Hence, I have no real experience teaching.

Answer 1

Based on the feedback I have received and thinking about it for a while I've realized quite a few key points in my question that I think lead to a solution to this issue.

1. The person I am working with has very little knowledge of low-level code and while probably can understand the concepts of dynamic memory allocation, probably would need quite some time to figure out how to actually code it from scratch.

2. The only reason why we need that code written is because the language we selected is supposed to have that feature and it doesn't work properly. In particular, pointers can end up pointing to different things after freeing any memory.

3. The code itself is only needed for the purpose of allocating memory and building linked structures. There is nothing special we need to do with our implementation.

4. I already know how to write this code and I probably have some version of it that I've already written in the past and just need to clean up a little bit.

5. The purpose of the project is for the student to use physics and programming to create a video game. Wasting most of the time trying to make an allocation module probably isn't wise in the long run.

So, I think perhaps in my particular situation the best course of action is for me to just fix the issue myself and take care of it instead of insisting that the person who is essentially my fellow teammate know every inch of the program. After all, if the language didn't have a bug in its design, we wouldn't waste our time doing this. So then, why waste even more time trying to teach someone to code it themselves and then expect them to make a working version on their own.

Assuming that I was going to teach them it though, I think the best course of action (since we only communicate digitally) would be to create example problems of some form showing the raw memory and how it changes when different functions and inputs are used.

Answer 2

To explain this topic, you need to find a real life thing which is similar, and would be understood by the student.

For example, you could use the concept of a bookshelf and books. You can place books in a bookshelf one by one and fill it up, but as you take books out, it leaves holes that can be filled with other books. Sometimes you have books that are bigger than others, and they won't fit in those holes. So you have to put the book at the end (or get another bookshelf) rather than using the hole that already exists. You could also "compact" the books, but this would invalidate any direct pointers to those books (ie, 15th book from the left on the 3rd shelf). (Yes, I know that managed languages deal with this issue, but trying not to get too technical)

The bit about the size of the allocation is really just a placeholder for eyeballing the size of the book.