CSS
443 - Machine Problem #1
Re-Familiarizing
with Linked-List
Fun with
Collecting Garbage
Assigning Date:
Program
Due Time:
Design
Document Due Time:
Objectives:
In this programming assignment we will pretend we are the java virtual machine and support the implementation of linked-list with no dynamic memory support, i.e. we cannot call the system new(). In particular, we will create our own memory manager that supports simple memory allocation and ”„”„mark and sweep”¦”¦ garbage collection.
Approach:
We will test our toy memory manager (TrecordMemoryPool) with a simple link list (TmyList) of integers (keys). We define a Record to be three consecutive memory locations:
”P keyField - for storing user”¦s key.
”P NextField - for storing address to the next Record in the list
”P MemoryManager (or MM) Field - this is reserved by memory manager to support garbage collection.
Each TmyList class has an instance of TrecordMemoryPool object. The TrecordMemoryPool is responsible for maintaining a pool of Records. Whenever TmyList needs to insert an integer, it will request for a Record from its TrecordMemoryPool. TmyList only cares about the first two fields in the Record for creating and maintaining the list of integers. Delete Records from TmyList are left dangling. TrecordMemoryPool will perform garbage collection to reclaim all the dangling Records when required.
Please refer to the mp1_assignment.zip off our course web-site. You are to complete the implementation of TrecordMemoryPool, and TmyList. As in all typical collaboration in software projects, the rest of the software development team has expectations on the public interface of these classes. As such, in this mp you:
1. cannot delete and/or change any existing public methods defined in the given TrecordMemoryPool and TmyList classes;
2. can add new public methods when necessary;
3. can add new private instance variables and/or methods
In addition, please keep in mind that someone else will implement the final testing driver program. This is saying, you cannot assume what Main.cpp would look like.
What to hand-in:
1.
Please refer to Programming Assignments section in our
class syllabus for details. You should create a zip file with your
FirstLastNameMp1.zip, containing your implementations of TmyList,
and TrecordMemoryPool in TmyList.cpp
and TmyList.h, TrecordMemoryPool.h,
and TrecordMemoryPool.cpp,n
and copy it to \\Hermes\Classes\CSS443\mp1 before the deadline time (of
2.
Hand-in a design document on the due date before
a. Pseudo code, worst and best case analysis of TrecordMemoryPool::GarbageCollection() and NextFreeRecord();
b. Worst and best case analysis of TmyList::InsertElement() and RemoveLinkFromList().
c. In general, can you improve the efficiency of RemoveLinkFromList() by optimizing the implementation of InsertElement()?
Credit Distribution:
1. Implementation of TmyList, and TrecordMemoryPool: |
65% |
|
a. Correct Memory Manager operations/Results Garbage Collection 20% |
30% |
|
b. Correct List Operations/Results: Merge sort 10% |
20% |
|
c. Efficient Implementation: |
15% |
|
1. Design Documentation: |
30% |
|
2. Proper programming style and proper submission |
5% |
BE WARNED! If your program does not compile, or if your implementations do not generate correct results, you WILL NOT GET ANY CREDIT. If your linked-List does not work, you WILL NOT get any credit for TrecordMemoryPool. If you implement algorithms based on pass students”¦ design documentations that are available on-line (or otherwise), please clearly indicate that. You will not receive any credit for those implementations. You have one and a half week to work on this assignment, please plan accordingly, and start early.
Extra Credit:
10%: Implement your link list based on doublely linked list. In this case, your Record will consist of four entries, in addition to the above nextField, keyField and MMField, you would have a previousField. If you choose to implement the doubly linked version, you do not need to implement the singly linked version.
You will get a maximum of 10 points for extra credit. Implementation with no corresponding design document submission will not get you any extra credit.
This programming assignment contributes 8% towards your final grade for this course.