cs Computer Science II Assignment 3 – Heaps and AVL Trees Solution

Important Note

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


    1) Question Part (50 points)

        a) (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.

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

            ▪ 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.”

            ▪ 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

        c) (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.

        d) (10 points)

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

            ▪ What is the minimum number of nodes in an AVL tree of height 15?

        e) (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


This homework will be graded by your TA, Süleyman Aslan (suleyman.aslan at bilkent edu tr)​.Thus, you may ask your homework related questions directly to him.

You have to follow the following instructions about the format, programming style and general layout of your program.

    • You can use the codes provided in your textbook or the lecture slides. However, you cannot use any external heap implementation such as STL’s in your code.

    • This assignment is due by 23:55, ​August 6​,2020. You should upload your solutions to Moodle. You should upload a ​single zip​file that contains:
        a. Your solution to the first part as ​pdf​(do NOT send photos of your solution), this ​pdf​must also include the report of the programming part.

        b. Code files (only the “​.cpp​” and “​.h​” files that you write for the homework) of the second part and a “​Makefile​” for the compilation of your code that produces the executable.

        c. In the end, your zip file should contain ONLY ​code files​,“​Makefile​” and a ​pdf​;any violation of these causes a significant loss from your grade. Name of the pdf should be “​Surname-Name.pdf​”.

    • Do not forget to put your name and student id in all of these files. Well comment your implementation. Add a header comment to the beginning of each file as follows:

/**

        ◦ Title: Heaps

        ◦ Author: Firstname LastName

        ◦ ID: 21000000

        ◦ Assignment: 3

        ◦ Description: description of your code

*/



    • If you do not know how to write a Makefile, you can find lots of tutorials on the Internet. Basically they are files that contain a list of rules for building an executable that is used by

“make” utility of Unix/Linux environments. “make” command should build an executable called
“heapsort​​”, so write your Makefile accordingly (i.e. at the end, when you type “make” in

terminal on your working directory, it should produce “heapsort​​” executable)








3
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