AE2 Algorithms and Data Structures
Assessed Exercise 2
Submission Instructions
Your solution must be submitted in Moodle. It should contain only three files:
1. A pdf file named “Name_MatrNum.pdf”, where Name is your last name and MatrNum your matriculation number. You should write all your answers in this file, except your java source code for questions 1B and 2D, which should be provided in the following files:
2. “ValidParentheses.java”: your Java implementation for Question 1B
3. “BSTHeightHistogram.java”: your Java implementation for Question 2D
Your source code should be able to be compiled (without errors) and executed in a standard Unix shell, by running the commands: javac file_name.java java file_name
No other operating-system dependent setup should be assumed, and your execution should not rely on any special PATH variable configuration, IDEs, or dependencies. In a nutshell, we should be able to easily compile and run your code!
Finally, you should not make use of any special Java libraries, and you should only import the classes that we explicitly allow you to in the statement of Questions 1B and 2D.
Question 2 (Binary Search Trees)
A binary tree is called perfectly balanced, if the left and right sub-trees of all its nodes have exactly the same height.
A. Prove that any (non-empty) perfectly balanced binary tree of height ℎ has exactly 2!"# − 1 many nodes. [4]
B. Give two different orderings in which we can enter the values {1,2, … ,7} in a (initially empty) binary search tree (BST) so that in the end it is perfectly balanced. For one of these input sequences (whichever you like), draw all intermediate BSTs that arise after each insertion (that is, you have to draw seven BSTs). [4]
C. Draw two different BSTs whose in-order traversal outputs the sequence 1,2,3,4,5. [3]
D. Implement the following algorithm in Java: you ask the user to input a positive integer ?. Then, for each of the ?! Many different permutations of the values {1,2, … , ?}, you compute the heigh of the BST that arises if we insert,at an initially empty BST, the specific sequence of elements. Then, you print a histogram with the frequencies of the different heights than can arise, as well as the average height.
Your output should be in the following form (here given for ? = 7):
my wechat：_0206girl
Don't hesitate to contact me
