CS计算机代考程序代写 algorithm Problem Set 5

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?