Mathematics > QUESTIONS & ANSWERS > Questions and Answers > Worcester Polytechnic Institute - CS 584Homework 2 Solutions. CS 584 Algorit (All)

Questions and Answers > Worcester Polytechnic Institute - CS 584Homework 2 Solutions. CS 584 Algorithms: Design and Analysis. Solutions for Homework 2

Document Content and Description Below

CS 584 Algorithms: Design and Analysis Fall term 2013 Solutions for Homework 2 1. In our MERGE-SORT algorithm we merged two sorted lists into one sorted list in O(n) time. Describe an O(n log k)-t... ime algorithm to merge k sorted lists into one sorted list, where n is the total number of elements in all the input lists. (Hint: Use a min-heap.) Solution: 2. In class we showed using an adversary argument that any algorithm to compute the MAX and the MIN of a set of n distinct numbers simultaneously using pairwise comparisons must, in the worst-case, use at least d3n=2e ¡ 2 comparisons. (a) Use the decision tree argument (flnding a lower bound on the number of possible responses, which is a lower bound on the number of leaves, and using this as a bound on the height of the tree) to develop a worst-case lower bound on the number of pairwise comparisons. (b) If this bound is difierent than d3n=2e ¡ 2, explain how seemingly contradictory bounds can both be correct. Solution: 3. Show that the second largest element can be found with n+dlog ne¡2 comparisons in the worst case. Solution: 4. In our linear-time selection algorithm, the inputs are divided into groups of 5. What if you used groups of 3 instead? What if used groups of 7 or larger (odd integers)? Solution: 5. Show that 2n¡1 comparisons are necessary in the worst case to merge two sorted lists containing n elements each. Solution: 6. Describe a O(n) worst-case time algorithm that, given a set S of n distinct numbers and a positive integer k • n, determines the k numbers in S that are closest to the median of S in the sorted order of S 3 (for simplicity we assume that both n and k are odd, so there is one median). 4 [Show More]

Last updated: 2 years ago

Preview 1 out of 4 pages

Buy Now

Instant download

We Accept:

We Accept
document-preview

Buy this document to get the full access instantly

Instant Download Access after purchase

Buy Now

Instant download

We Accept:

We Accept

Reviews( 0 )

$12.00

Buy Now

We Accept:

We Accept

Instant download

Can't find what you want? Try our AI powered Search

94
0

Document information


Connected school, study & course


About the document


Uploaded On

Feb 11, 2021

Number of pages

4

Written in

Seller


seller-icon
QuizMaster

Member since 6 years

1187 Documents Sold

Reviews Received
185
56
29
11
17
Additional information

This document has been written for:

Uploaded

Feb 11, 2021

Downloads

 0

Views

 94

Document Keyword Tags


$12.00
What is Scholarfriends

In Scholarfriends, a student can earn by offering help to other student. Students can help other students with materials by upploading their notes and earn money.

We are here to help

We're available through e-mail, Twitter, Facebook, and live chat.
 FAQ
 Questions? Leave a message!

Follow us on
 Twitter

Copyright © Scholarfriends · High quality services·