CSS 443 - Machine Problem #1

 

Re-Familiarizing with Linked-List

Fun with Collecting Garbage                            

 

Assigning Date: March 31, 2003

Program Due Time: 2:30 pm, April 9, 2003

Design Document Due Time: 3:40 pm, April 9, 2003

 

 

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:30pm).  Please do not include NumRecord.h and Main.cpp, I will use my own version for testing your code. Please remember that if you change any existing public interface of any of the above classes then your code will not compile with my Main.cpp. Adding new public methods is fine, although I will not call them in my Main.cpp. If you change any existing public methods, my Main.cpp will not compile and you will not receive credit for your work!

2.        Hand-in a design document on the due date before 3:40pm.  In this document please include the followings:

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.