Assignment 4
● Topic: Data Structures
1. Show how to implement a stack using two queues. Analyze the running time of the
stack operations.
2. Demonstrate what happens when we insert the keys 5, 28, 19, 15, 20, 33, 12, 17, 10 into
a hash table with collisions resolved by chaining. Let the table have 9 slots, and let the
hash function be h(k) = k mod 9.
3. Consider a binary search tree T whose keys are distinct. Show that if the right subtree
of a node x in T is empty and x has a successor y, then y is the lowest ancestor of x
whose left child is also an ancestor of x.
4. Describe a non-recursive algorithm for enumerating all permutations of the numbers
{1, 2, …,n} using an explicit stack.
5. Show that any n-node binary tree can be converted to any other n-node binary tree
using O(n)rotations.
