Computer Science II Assignment 3 – Heaps and AVL Trees Solution

Description

Important Note

Please do not start the assignment before reading the notes in HAND IN section (last two pages):

1. Question Part (50 points)

1. 1. (10 points) Show the result of inserting 13, 6, 3, 7, 2, 4, 11, 0, -1 and 1 in that order into an initially empty AVL tree. Show the tree after each insertion, clearly labeling which tree is which.

1. 2. (10 points) This problem gives you some practice with the basic operations on binary min heaps. Make sure to check your work.

1. 1. • Starting with an empty binary min heap, show the result of inserting, in the following order, 12, 8, 3, 7, 4, 5, 13, 2, 6, 10 and 1, one at a time, into the heap. By show, we mean, “draw the tree resulting from each insert.”

1. 1. • Now perform two deleteMin operations on the binary min heap you constructed in part

(a). Show the binary min heaps that result from these successive deletions, again by drawing the binary tree resulting from each delete

1. 3. (10 points) Consider a binary heap. Print the keys as encountered in preorder traversal. Is the output sorted? Justify your answer. Attempt the same question for inorder and postorder traversals.

1. 4. (10 points)

1. 1. • Give a precise expression for the minimum number of nodes in an AVL tree of height h.

1. 1. • What is the minimum number of nodes in an AVL tree of height 15?

1. 5. (10 Points) Write a function in pseudocode that determines whether a given binary tree is a min heap.

1

2) Programming Part (50 points)

In this assignment, you will write a Heap class and use it to implement HeapSort. The Heap class must be defined in two files: heap.cpp and heap.h. The Heap class must support, at least, the following functions.

void insert(const int a)

int maximum()

int popMaximum()

Your program will read input from an input file which contains one integer per line, and write sorted output to an output file which contains the same integers in sorted order. Moreover, your program should write the number of comparisons made during the sorting function to standard output.

Deliverables:

• A heap.cpp and heap.h file which implement the Heap data structure.

• A heapsort.cpp file which uses the Heap data structure to implement the heapsort algorithm

• A report describing the heap data structure and heapsort functions including the theoretical and actual number of comparisons required for each algorithm.

• Run your program on five sample input files. In your report, report the number of data points, n, in each file, as well as the number of comparisons heapsort uses to sort them. Please remember that your program will be tested with additional input files.

The program must compile using the following command on dijkstra.cs.bilkent.edu.tr

g++ heapsort.cpp heap.cpp -o heapsort

The program must run using the following command on dijkstra.

./heapsort input_filename output_filename

2

Code Format, Notifications and Turn In

IMPORTANT:

• Although you may use any platform or any operating system to implement your algorithms and obtain your experimental results, your code should work on the ​dijkstra server (dijkstra.ug.bcc.bilkent.edu.tr). We will compile and test your programs on that server. If your C++ code does not compile or execute in that server, you will lose points.

• Attention: For this assignment, you are allowed to use the codes given in our textbook and/or our lecture slides. However, you ARE NOT ALLOWED to use any codes from other sources (including the codes given in other textbooks, found on the Internet, belonging to your classmates, etc.). Furthermore, you ARE NOT ALLOWED to use any data structure or algorithm related function from the C++ standard template library (STL).

Do not forget that plagiarism and cheating will be heavily punished. Please do the homework yourself.

4