685.621 Algorithms for Data Science
Homework 6
Total Points 100/100
Total Points 100/100
Collaboration groups have been set up in Blackboard. Make sure your group starts one thread for
the collaborative problem. You are required to participate in the collaborative problem. Do not directly
post a complete solution, the goal is for the group to develop a solution after everyone has participated.
1. [50 points] Consider the following algorithm for doing a postorder traversal of a binary tree with
root vertex root. Prove that this algorithm run in time Θ(n) when the input is an n-vertex
Algorithm 1 Postorder Traversal
function Postorder(root)
if root 6= null then
Postorder(root.lef t)
Postorder(root.right)
visit root
end if
end function
binary tree.
2. [50 points] Note this is a Collaborative Problem We define an AVL binary search tree to
be a tree with the binary search tree property where, for each node in the tree, the height of its
children differs by no more than 1. For this problem, assume we have a team of biologists that
keep information about DNA sequences in an AVL binary search tree using the specific weight
(an integer) of the structure as the key. The biologists routinely ask questions of the type, “Are
there any structures in the tree with specific weight between a and b, inclusive?” and they hope
to get an answer as soon as possible. Design an efficient algorithm that, given integers a and b,
returns true if there exists a key x in the tree such that a ≤ x ≤ b, and false if no such key exists
in the tree. Describe your algorithm in pseudocode and English. What is the time complexity
of your algorithm? Explain.
1
