Data Structures I - NTIN066 - Winter Semester 2015/2016 - 2nd homework

The rules

• All the code which you submit must be original created by you without any external "inspiration".
• Do not share your solution with anyone else so that your code does not become someone else's "inspiration". The only exception to this rule is submitting the assignment.
• Feel free to discuss the homework and possible approaches with others. However, you should observe the above rules about not sharing any code. That is, discussion is fine as long as you write your own code by yourself!
• Your solution should be written in either C/C++ (recommended), Java or C#.
• Use only standard constructs of your programming language. Do not use any special library functions. The code dealing with the data structure has to be written solely by you.
• Solutions deviating from the above rules will not be accepted.

The description of the problem

Implement representations of a set by (2,3)-trees and (2,4)-trees. The set will consist of positive 31-bit numbers, stored in all nodes of the tree (not only in the leaves).

Examine behavior of both data structures on test data generated by the program described below. The test data contain sets of varying sizes with two kinds of operations:

• uniform test: a sequence of Insert and Delete operations, which access all keys of the set uniformly;
• biased test: first, the set is created using Insert from 1 to N, followed by Inserts and Deletes on a certain small subset, and finally all elements are Deleted from 1 to N.

For each set, measure the following values:

• the average number of tree nodes accessed per operation (for each operation, we count nodes “touched” by the operation; repeated access to the same node counts as one);
• the average number of nodes modified per operation (for each operation, we count nodes, but only those which were created, deleted, or changed during the operation).

For each kind of test (uniform/biased), draw a plot showing the number of accesses and modifications vs. the size of the set (two lines for (2,3)-trees, two more for (2,4)-trees). Try to explain the differences in behavior of the two structures.

Generating the data

Download the generator or use a compiled version /afs/ms.mff.cuni.cz/u/b/babkm5am/ds1/hw2/abgen in the unix lab Rotunda. Run it with the following parameters:

• -s XX, where XX are the last two digits of your student ID;
• -b, if you want to generate the biased test; otherwise, the uniform test is generated.

The output of the generator is a text file. Each line specifies a single operation on the tree:

• # N: start a test for a set of size N – discard the previous tree and create a new one (the set size can be useful for plotting);
• I X: insert a key X to the tree (if the key is already present, ignore this operation);
• D X: remove a key X from tree (if the key is not present, ignore this operation).

A single invocation of the generator creates a sequence of tests ranging roughly from 1000 to 1000000 elements. If you want to use a different size for debugging, use the -n N parameter.

Example input

# 5
I 67
I 45
D 67
I 81

Submitting your solution

Send an e-mail with subject of the form 'HW2-55973318' (i.e., HW2-student ID) with the following attachments:

• source code used to get your results (in case it consists of multiple files, please use ZIP or TAR to pack them),
• a PDF with plots and comments.

The body of your e-mail shall have the following form:

Name: Martin Mareš
Pseudonym for web results: Guybrush Threepwood
Tutorial section: Monday-12:20-odd