CSc 22000: Algorithms

Lab 2: B-Trees

[ Introduction | Setup | Specification | Guidelines | Collaboration Policy | Submission and Grade ]

Introduction

In this lab, you will implement the B-Tree data structure in C++. Please read Chapter 18 of the textbook to review B-Trees.

Setup

We have prepared skeleton files to help you get started with the lab. To set up the lab workflow on your computer, download lab2.tgz and type the following commands to extract the files:

% tar -xf lab2.tgz
% cd lab2

Specification

Inside the lab2 directory, you will find the following files:

% ls
btree.cpp    btree_test.cpp    makefile               test_data
btree.h      grader.py         output_required.txt

Once you've completed the lab by editing the btree.cpp file, you can test it as follows:

% python grader.py
Score: 10 out of 10 = 100%
--------------------------------------------- Summary ----------------------------------------------
All tests passed.
------------------------------------------ Builder Output ------------------------------------------
g++ -Wall -c btree.cpp
g++ -Wall -c btree_test.cpp
g++ -Wall btree.o btree_test.o -o solution

rm -f *.o solution

Guidelines

Now that you've seen how you can test your solution, let's go through some of the guidelines you should follow when implementing the lab.

First and foremost, this lab is designed to be completed on a machine in NAC7105 Linux Lab. Please make sure your solution executes as expected on those machines since your solution will be graded on one of those machines as well.

We have provided a skeleton file btree.cpp as a starting point. Your task is to only complete the following functions found inside btree.cpp file.

1. BTreeNode::BTreeNode();
2. BTreeNode::BTreeNode(bool isLeaf, int numKeys);
3. BTreeNode::~BTreeNode();
4. void bTreeSearch(BTreeNode *root, char key, BTreeNode *&returnNode, int &returnIndex);
5. void bTreeInsert(BTreeNode *&root, char key);
6. void bTreeInsertNonfull(BTreeNode *root, char key);
7. void bTreeSplitChild(BTreeNode *root, int index);
8. void bTreeDelete(BTreeNode *&root, char key);

Remarks:

Testing:

The grader.py script grades your solution by running the following tests:

  1. Insert A D Q and print the resulting B-Tree
  2. Insert A D Q R G S and print the resulting B-Tree
  3. Insert A D Q R G S E H V Y Z B C I J K L N X F P O T and print the resulting B-Tree
  4. Insert A D Q R G S E H V Y Z B C I J K L N X F P O T, print the resulting B-Tree, and search for R
  5. Insert A D Q R G S E H V Y Z B C I J K L N X F P O T, print the resulting B-Tree, and search for K
  6. Insert A D Q R G S E H V Y Z B C I J K L N X F P O T, delete T, and print the resulting B-Tree
  7. Insert A D Q R G S E H V Y Z B C I J K L N X F P O T, delete X, and print the resulting B-Tree
  8. Insert A D Q R G S E H V Y Z B C I J K L N X F P O T, delete T X, and print the resulting B-Tree
  9. Insert A D Q R G S E H V Y Z B C I J K L N X F P O T, delete H F G H, and print the resulting B-Tree
  10. Insert A D Q R G S E H V Y Z B C I J K L N X F P O T, delete F G H, insert G, print the resulting B-Tree, and search for M

After running all the test cases, the script

  1. Shows your grade,
  2. For each test that failed, shows the result computed from your implementation and the required result from the output_required.txt file.

Feel free to examine the output_required.txt file yourself, but make sure not to edit it. This file contains multiple sections separated by the @ symbol with each section describing the required output of a single test case. The sections are ordered in the same order as above.

Before you submit the lab, try to pass all the test cases shown above. You will be graded on those test cases as well as another set of 10 test cases.

Collaboration Policy

You must write all the code you hand in for the programming assignments, except for code that we give you as part of the assignment. You are not allowed to look at anyone else's solution. You may discuss the assignments with other students, but you may not look at or copy each others' code. You may not use code that might be available online.

Submission and Grade

The deadline for the lab is April 6, 2016 11:59 PM.

Please submit only the completed btree.cpp file to the Submission Server. The submission server will stop accepting solutions after the deadline.

You will be notified when the grades will be available during the class.


© 2016: Nelly Fazio and Milinda Perera.