Problem Set 5
Problem Set 5
Problem 1 Show how to implement a stack ADT using only a priority queue and one additional
integer variable.
Problem 2 Write an algorithm for updating the key of an item in a priority queue, and analyse
its time complexity.
Problem 3 Given a heap T and a key k, give an algorithm to compute all the items in T with keys
less than or equal to k. Your algorithm should run in time proportional to the number of items
returned.
Problem 4 Qantas Airlines wants to give a first-class upgrade coupon to their top log n frequent
flyers, based on the number of miles accumulated, where n is the total number of the airlines’
frequent flyers. The algorithm they currently use, which runs in O(n log n) time, sorts the flyers
by the number of miles flown and then scans the sorted list to pick the top log n flyers. Describe
an algorithm that identifies the top log n flyers in O(n) time.
Problem 5 Suppose two binary trees, T1 and T2, hold entries satisfying the heap-order
property, where no entry in each tree exists in the other tree. Describe a method for combining
T1 and T2 into a tree T such that T’s internal nodes hold the union of the entries in T1 and T2
and T also satisfies the heap-order property. Your algorithm should run in time O(h1+h2) where
h1 and h2 are the respective heights of T1 and T2.
Problem 6 Give an alternative analysis of the bottom-up heap construction algorithm.
Problem 7 Prove that a binomial tree with 2n nodes has (
𝑛
𝑖
) nodes at depth i ( 0 ≤ i ≤n).
Problem 8 Consider the following binomial heap. Draw the resulting binomial heaps after
inserting the keys 7, 12, 20, 24, 25 and 25, respectively.
Problem 9 In a computer game, all the players are divided into a number of groups. Each player
can join one group only and is not allowed to join a different group later. Describe an algorithm
for checking if two players are in the same group. What is the running time of your algorithm?