CS6033 Homework Assignment 2∗
Due September 24th at 11:00 p.m.
Enter your answers for this assignment†on Gradescope following the TA’s instructions. No late assignments accepted
1. For the following array
(a) create a max heap using the algorithm we discussed in class (BUILD-MAX-HEAP)
(b) removethelargestitemfromthemaxheapyoucreatedin??,usingtheHEAP-EXTRACT- MAX function from the book. Show the array after you have removed the largest item
(c) using the algorithm from the book, MAX-HEAP-INSERT, insert 56 into the heap that resulted from question 1b. Show the array after you have inserted the item.
2. Consider of 3-ary max-heap. A 3-ary max-heap is like a binary max-heap, but instead of 2 children, nodes have 3 children.
(a) How would you represent a 3-ary max-heap in a array?
(b) What is the height of a 3-ary max-heap of n elements in terms of n and 3?
(c) Give an efficient implementation of HEAP-EXTRACT-MAX. Analyze its running time in terms of 3 and n.
(d) Give an efficient implementation of MAX-HEAP-INSERT. Analyze its running time in terms of 3 and n.
(e) Give an efficient implementation of HEAP-INCREASE-KEY(A, i, k). Analyze its running time in terms of 3 and n.
3. Show that the number of leaves in a heap is ⌈n2⌉. (See if you can find a simple answer based on the lecture.)
4. Prove the correctness of HEAP-DECREASE-KEY using a loop invariant.
∗Many of these questions came from outside sources.
†You may call any algorithm as a subroutine that was presented in a lecture.
5. Draw the recursion tree for the following function. In your recursion tree, show the top 3 levels of the recursion tree and the bottom level of the recursion tree. Put “...” (dots) to represent the levels you didn’t show.
Show the running time for each level, and label each node with the running time corresponding to the function call for that node (don’t include the time it takes to complete the recursive calls in your running time).
maximum(A, l, r)
1) 2) 3) 4) 5) 6) 7) 8) 9) 10)
if(r−l==0) return A[r]
lmax=maximum(A,l,⌊(l+r)/2⌋) rmax=maximum(A,⌊(l+r)/2⌋+1,r) print(rmax,lmax)
if rmax < lmax
return lmax else
return rmax
6. In your last MMORPG you rocked.
The weekend is about to arrive, and it is time to find teammates again. The problem is, the word has leaked, and now everyone (perhaps on the entire planet) wants to join your team.
With so many people, you have no idea how you will determine how many people are on your team and who they are.
You need a faster algorithm than the last time.
Your algorithm must return a sorted list of players (where no player is listed twice) in time o(n2). You may call any algorithm as a subroutine that was presented in lecture 2. State what the running time is of your algorithm in big-Oh, Theta, and Omega notation using the tightest bounds possible1.
7. (10 points) Oh no! The bug that prevents the MMO from scaling the difficulty of the last boss has been fixed.
For the upcoming battle, you will choose k players who want to join your team. You have become known, so you have many more than k players vying to be chosen by you.
You decide to repeat the following steps k times to select your team:
• You will invite the best player who asked to join your team (that you haven’t already
invited to your team).
• After inviting that player, you will see if any new players have asked to join your team
(after seeing who you already have on your team - more people will want to join!).2
Design an algorithm. The fate of your gaming career depends on getting this right!
You may use:
1In this course, you must always provide the tightest bounds, even if a looser bound is valid. 2In this problem, you will assume the best players only ask to join your team one time.
• O(k) time to set up the problem
• O(log k) time to invite the next player to be part of your team • O(log k) time for each potential new candidate
Justify the run time of your algorithm.
8. The big space galactic grand tour tournament is about to begin, and ships are arriving from all over the galaxy. There are k portals for where ships can land on your ship. Each is near one of the k wormholes near your spaceship. Ships arrive from a wormhole line up outside the closest portal to that wormhole.3
It will prevent some future wars if the people who are allowed in the main tournament hall, located on the second deck, is determined not by how many weapons they are carrying but based on the time they exited the wormhole.
Your job is to keep the lines moving and assign a number to each person based on the time they entered through a wormhole as efficiently as possible. You must choose the next person in O(log k) time.4
9. The intergalactic vote for confidence (a number from 0 to 100) in the supreme chancellor is tomorrow! If over 50% of the galaxies are not confident in the commander (i.e. have a confidence score of 50 or higher), he will be cast out the airlock!
As the newspaper reporter for the galaxy times, you want to keep track and analyze of the scores as they come from the far flung galaxies.
How can you return the median in O(1) time and enter a new score in O(log n) time where n is the number of galaxies whose scores have already been entered.
Reminder: The median of 10, 19, 21 is 19. The median of 10, 30, 90, 99 is 30+90 . The median 2
of 10, 30, 50, 60, 90 is 50.
10. (3 bonus points) Think of a good5 exam or homework question for the material covered in
Lecture 2
3Surprisingly, no ship arrives without using a wormhole! Your galaxy is far, far away from all the other galaxies.
4You can decide what data structure to use and what information you store in the data structure. You might choose to use more than on data structure to solve this problem.
5Only well thought out questions will receive the bonus points. 3
