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

Deadline: 17th November 2015.
How to submit: As an attachment of email to

The rules

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:

For each set, measure the following values:

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/ in the unix lab Rotunda. Run it with the following parameters:

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

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:

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