Homework 1 A k-ary heap...

EEL 3701: 
Advanced Data Structures and Algorithms Analysis
Programming Homework 1

1. (40 points) A k-ary heap is like a binary heap (where k = 2), but (with one possible
exception) non-leaf nodes have k children instead of 2 children. Implement k-ary heap
as a min-priority queue for an arbitrary k  2 to support following operations:
• insert (x): inserts the element x to the heap.
• extract-min(): removes and returns the element of heap with the smallest key.
k-ary heap is to be implemented using an array of predefined size. Also study the
relative eciencies of the data structure for varying values of k, by measuring the time
required for performing sequence of operations given the input file for k = 2, 3, 4, 6,
10. Plot a bar chart. Vary n (the maximum size of the data structure) from 50, 000
to 500, 000. For timing experiments, you can use n inserts followed by n exctract-min
operations.
Also, given is the sample input file (with much smaller data) where “IN” stands for
insert and “EX” stand for extract-min operation. Submit the sample output file for
this input file provided along with your code.
2. (60 points) An AVL tree is a binary tree that is height balanced: for each node x, the
heights of the left and right subtrees of x di↵er by at most 1. Implement an AVL tree
to support following operations.
• insert(x): inserts an element x to the tree.
• search(x): returns TRUE if a node containing element x is found in a binary
tree else returns FALSE.
• successor(x): returns successor of element x i.e. element with the smallest key
greater than that of element x.
• select(i): returns the element containing i
th smallest key in a binary tree.
• rank(x): returns the rank/position of element x in the liner order determined by
inorder traversal of tree.
Run your program on the given input files and generate the output file. Each line in
the input file is one the following commands:
• IN: insert
1
• SR: search
• SC: successor
• SE: select
• RA: rank
Note:
1. This programming homework is to be done in pairs (groups of 2 students). However,
both the partners should do both the problems. Spliting the load so that one person
does one problem each is disallowed.
2. Either C, C++ or java can be used as a programming language. (If you choose C++
as a programming language, you can download files “timer.h” and “timer.cpp”, which
are useful for timing experiments.)
3. Executing the program for a particular input file should generate output file containing
result of each operation (except insert) line by line. Please look at the sample output
file (contains comments after symbol “//” which are only for understanding purpose
and need not be part of actual output file).
4. Input files attached are sample input files only. For timing experiments (Problem 1),
these files need to be much bigger (having at least 10000 commands).
2
• SR: search
• SC: successor
• SE: select
• RA: rank
Note:
1. This programming homework is to be done in pairs (groups of 2 students). However,
both the partners should do both the problems. Spliting the load so that one person
does one problem each is disallowed.
2. Either C, C++ or java can be used as a programming language. (If you choose C++
as a programming language, you can download files “timer.h” and “timer.cpp”, which
are useful for timing experiments.)
3. Executing the program for a particular input file should generate output file containing
result of each operation (except insert) line by line. Please look at the sample output
file (contains comments after symbol “//” which are only for understanding purpose
and need not be part of actual output file).
4. Input files attached are sample input files only. For timing experiments (Problem 1),
these files need to be much bigger (having at least 10000 commands).
2