COL 106 Assignment 5


  • When two nodes (or more) free blocks have the same size, pick the one with the smallest address.
  • When a node is deleted, it is always replaced by its in-order successor.
  • When freeing a block, first merge with any contiguous block before it. If none exist, attempt to merge with any contiguous block after it. (Deleting old node and add a new one.)
  • You should not VISIT any node more than once in any ALLOC. Note that the print is only for the traversal for searching for the closest match. Traversal for re-insertion is not to be printed.
  • In case multiple nodes of the best-fit size are found, pick the node encountered first.
  • You should print the free-list at the end in the increasing order of the addresses.


    Replace the BST in assignment 3 with a BST_RB: a red black tree. BST_RB implements interface BST (below) and is constructed on pair of keys and a genric type.
    class Key implements Comparable<Key> {
       // fill body
    interface BST <T> {
       Position add(T data, Key key);
       Position remove(T data, Key key);
       T[] remove(Key key);


    See assignment 3, except, for every visited node, VISIT must now include the color, i.e., VISIT RED or VISIT BLACK. Also, change the name of the main class public class Assignment5.


    ALLOC 100
    ALLOC 1000
    ALLOC 10000
    FREE  1101 100 
    FREE  1201 1000
    FREE 1 100
    ALLOC 50
    ALLOC 1
    VISIT BLACK 101 ∞
    ALLOC 101
    VISIT BLACK 1101 ∞
    ALLOC 1101
    VISIT BLACK 1101 1100
    VISIT RED 1 100
    ALLOC 1
    FINAL 51 50 1101 1100 11101 ∞

    Submission instructions

    Submission will be at moodle.

    Please ensure that you follow the following set of instructions meticulously while submitting the assignment on Moodle. Also, please note that in case of deviation from this procedure will render your submission faulty, and your assignment might not be evaluated at all by the script. Please follow these steps:

    1. On eclipse, by default, all your source files (.java files) are saved into a directory called "src" inside your project. You have to compress this directory (to zip format) and rename the zip file in this format:
      Example: If your entry number is 2012CSZ8019, the zip file should be named It should expand to a directory called src, which contains all your .java files. Please make sure that you follow exactly this naming format.
    2. Next, convert the zip file to base64 format. On any linux system, you can do this easily by issuing the following command on the terminal :
         base64 >
      This will create a file with the same name with a b64 extension appended at the end.
    3. Upload this b64 file on moodle and submit it (in the "Submission" section). After Submission, there is an option of "Evaluate" in the "Edit" section. Click on "Evaluate". On the right side of the window, you will get information about the submission status. On clicking the "Evaluate" link, you should see a script running and producing an output of your codes' performance against the standard set of test cases that we supply internally for the assessment. A dialog box will show you the messages on how your codes performed against the benchmarks that we provided.
            Important notes