COL 106 Assignment 5

Clarifications

  • 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.

    Assignment

    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);
}

    Implementation

    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.

    Examples

    Input: 
    ALLOC 100
ALLOC 1000
ALLOC 10000
FREE  1101 100 
FREE  1201 1000
FREE 1 100
ALLOC 50
    Output: 
    VISIT BLACK 1 ∞
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: 
      your-entry-number_assignment5.zip
      Example: If your entry number is 2012CSZ8019, the zip file should be named 2012CSZ8019_assignment5.zip. 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 entrynumber_assignment5.zip > entrynumber_assignment5.zip.b64
      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