Data Structures - Chapter 11 - Programming Assignment
Implement and Test the Set Class Using a B-tree

The Assignment:
Implement a class for a set of integers, using a b-tree to store the items. The basics of the b-tree are described in Section 11.2, though we will make one major change: Instead of storing the b-tree node information in ordinary arrays, you will use vectors. This is a difficult assignment. The first part (Homework 10) is due at 11:30pm on Thursday, December 3. HW 10 late work is accepted up to 96 hours late with a penalty of 10%. The second part (Homework 11) is due at 11:30pm on Friday, December 11. No late work will be accepted for HW 11.
Purpose:
Implement a challenging tree-based data structure.
Before Starting:
Read all of Sections 10.5 and 11.2.
Files that you must write:
  1. vset.h: Header file for this version of the set class. You don't have to write much of this file. Just copy our version from vset.h and add your name and other information at the top. You may also add more private member functions if you like. Notice that the set is NOT a template class. It is easier to debug with the Item type fixed as an int.
  2. vset.cxx: The implementation file for the new set class. You will write this yourself, including all the private member functions described in Section 11.2. Note: I changed the insert and erase functions a little. They return a bool value now. Read the meaning of these values in the header file.

    If you have any private helper functions, you must put a precondition/postcondition contract with each private function's implementation. NOTE: Some of you have been forgetting to put your name and a clearly written invariant at the top of this file. The TAs will start taking off points for such omissions.

  3. makefile: This is a makefile for the assignment. The file should contain targets for vset.o, vsetexam.o, and vsetexam (an executable file). The source code for vsetexam.cxx is available in the locations listed below. Your makefile should also include "all" and "clean" options.
Other files that you may find helpful:
  1. vsetexam.cxx: A non-interactive test program that will be used to grade the correctness of your vset class. This will provide 75 of the 100 points on Homework 11.

The Set Class Using a B-tree
Discussion of the Assignment

Your Set class for this assignment will use a B-tree as described in Section 11.2. You may use a typedef statement defining the Item type as an int number (rather than implementing a template class).

Do the Assignment in Two Parts

For easier debugging, carry out this assignment in two parts. Part A should include everything except the public remove member function and any private functions that are needed for removal. Once Part A (Homework 10) is working and tested, you may complete the assignment (Homework 11) by implementing the remove member function and its associated private functions.

Use your own interactive test program and the debugger to track down errors in your implementation. If you like, you may share an interactive test program with another student, but do not look at another student's b-tree. If you have an error, do not start making changes until you have identified the cause of the error. If you come to me or a TA for help, we will always ask you to do the following:

  1. Show us the invariant that describes how your private member variables implement the List class.
  2. Use the debugger to show us the problem!

Michael's Implementation Notes

Michael will implement this assignment between Nov 17 and Nov 24. He will write a blog of his progress and post that blog here each day! Follow along for a fun learning experience!

Michael Main (main@colorado.edu)