Homework #3 Heaps and AVL Trees Solution

Important notes




Before 23:55, April 18th, upload your solutions in a single ZIP archive using the Moodle submission form. Name the file as studentId_hw3.zip .



Your ZIP archive should contain the following files:



hw3.pdf , the file containing the answers to Questions 1 and 2



A folder named q2 which includes AVLTree.h, AVLTree.cpp, analysis.h, analysis.cpp files and main.cpp files containing the C++ source codes and Makefile which compiles all your code and creates an executable file named q2 .



A folder named q3 which includes MaxHeap.h , MaxHeap.cpp and main.cpp files containing the C++ source codes and Makefile which compiles all your code and creates an executable file named q3 .



readme.txt , the file containing anything important on the compilation and the execution of your program in Question 2 and 3.



Do not forget to put your name, student ID, and section number in all of these files. Well comment your implementation. Add a header as the following to the beginning of each file:






/*




Title : Heaps and AVL Trees



Author : Name Surname



ID : 21000000



Section : 0



Assignment : 3



Description : description of your code



*/




Do not put any unnecessary files such as the auxiliary files generated from your favorite IDE. Be careful to avoid using any OS dependent utilities.



You should prepare the answers of Questions 1 and 3 using a word processor (in other words, do not submit images of handwritten answers).



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. Thus, you may lose significant amount of points if your C++ code does not compile or execute on the dijkstra server.



This homework will be graded by your TA, Leonard Dervishi. Thus, please contact him directly for any homework related questions.



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.










Question 1 - 25 points




(a) [5 points] Draw all valid min-heaps containing these 4 elements 5, 7, 6, 1.




(b) [5 points] How many valid max-heaps containing 5 distinct elements can be built?




(c) [10 points] This question has three subparts which follow one another.

i. Insert 46, 59, 51, 31, 68, 63, 25, 75, 40 to an empty AVL tree, in the given order. Show only the final tree after all insertions.




Add one more element such that it causes a single right rotation in the tree. Show the final tree after the insertion.



Insert 1; to the AVL tree. Now, delete one element such that it causes a single left rotation in the tree. State the deleted number and show the final tree after the deletion operation.



[5 points] True or false : “Insertion order of the same set of elements into an AVL tree affects the resulting tree structure”.



If yes, why; if not, provide a counter-example.




Question 2 - 25 points




Implement AVL tree data structure named as AVLTree for maintaining a list of integer keys with the following methods:

void insert(int value) ; //inserts an element into the tree

int getNumberOfRotations() ; //returns the number of rotations performed so far while constructing the AVL tree




After that you will analyze the average number of rotations and determine if different patterns of insertion affect it. Write a global function, void rotationAnalysis() which does the following:




Creates 1000 random numbers in the range [1,100000] and inserts them into an empty AVL tree. While inserting elements into the AVL tree, it counts the number of rotations and it outputs the total number of rotations in the end. Repeat the experiment for the following sizes: {2000, 3000, 4000,..., 10000}



Instead of creating arrays of random integers, create arrays with elements in the same range in ascending order and repeat the steps in part (a) .



Instead of creating arrays of random integers, create arrays with elements in the same range in descending order and repeat the steps in part (a) .



Put function’s code into analysis.h and analysis.cpp files. Create a main.cpp file which calls rotationAnalysis() function. When the rotationAnalysis() function is called, it needs to produce an output similar to the following one:




Array Size
Random
Ascending
Descending








1000
x
x
x








2000
x
x
x








3000
x
x
x








...
x
x
x











After running your program, you are expected to prepare a report about the experimental results that you obtained in Question 2. In your report, you need to discuss the following points:




Do your findings related to average number of rotations in the AVL tree agree with theoretical results?



Do different patterns of insertion affect the number of rotations in the AVL tree? If so, explain how. If not, explain why not.






Question 3 - 50 points




Caezar, the leader of the Planet of the Apes, gained his intelligence from the ALZ - 112 drug and since then he has been learning computer science and hacking. A few days ago he visited Bilkent and hacked into your computers while you were practicing heaps. He takes the leaves of the heap that you have built from a given file and permutes them by picking a permutation uniformly at random. If the heap properties are not satisfied after the permutation, you need to fix the heap with appropriate methods. He also offers you a deal where he will either pay 10TL for each swap operation that you perform in the course of fixing the heap, or a 20 TL ALL worth treat (independently of the count). You need to write a program for a given file containing integers advising you about the best deal for you.




You need to implement a MaxHeap class which includes its appropriate methods and permutation(…) method. In main.cpp class you should take the input from a file named “input.txt” and build the heap by using the implemented methods. After that you need to generate every permutation of the leaves and sum up the total number of swaps that is done for each case. Then you need to compute the average number of swaps and choose the betterdeal accordingly.