Reference no: EM13849779
All problem / exercise numbers are from the 3nd edition of Introduction to Algorithms (the 1st and 2nd editions are different!) Note the difference between problems and exercises!
1. Special Cases of Select:
(a) Give an algorithm to find the second smallest element in a list of n elements in at most n + |lg n| - 2 comparisons. Note: Your algorithm can use no more than n + |lg n| - 2 total comparisons in the worst case. Hint: Find the smallest element, too.
(b) Give an algorithm to find the 3rd smallest element in a list, using the smallest number of worst-case comparisons. Exactly how many comparisons does your algorithm take in the worst case? Hint: Use your solution to part a - you will need to find the smallest and second-smallest element as well!
2. Exercise 9.3-6 quantiles
The kth quantiles of an n-element set ar the k -1 order statistics that divide the sorted set into k equal-sized sets (to within 1). Give an O(n lg k)-time algorithm to list the k-th quantiles of a set. Elements within each quantitle can be listed in any order.
3. Exercise 9.3-8 Finding the median of two lists of numbers
Let X[1 . . . n] and Y [1 . . . n] be two arrays, each containing n elemetns already in sorted order. Give an O(lg n)-time algorithm to find the median of all 2n elements in arrays X and Y .
4. Does inserting and then immmediately deleting a unique element from a Binary Search Tree always leave the same tree? Does inserting and then immediatley deleting a unique element from a Red/Black tree always leave the same tree?
5. Exercise 14.3-6 (MIN-GAP) Show how to extend a red-black tree to support the operation MIN-GAP, which gives the magnitude of the difference of the two closest numbers in the tree. For example, if Q = {1, 5, 9, 15, 18, 22} then MIN-GAP(Q) returns 18-15 = 3 since 15 and 18 are the two closest numbers in Q.
|
Limitations prevent the forecasts from being foolproof
: Give examples of how ratios gleaned from the financial statements can be used as a tool in helping a firm plan for the future. What do these ratios tell an individual analyzing them? What limitations prevent the forecasts from being foolproof?
|
|
Presentation on reward is better than punish
: Explanation Presentation- Topic: Reward is better than punish when training animals. Students will explain a complicated subject related to the course theme in 4 minutes to a classmate. The listener will be randomly assigned on the day of the prese..
|
|
What is the size of the last payment
: Land is purchased for 75000. It is agreed for the land to be paid for over a 5 year period with compounding annual interest at 12%. Each payment is 3000 more than the previous. What is the size of the last payment?
|
|
What factors impact sourcing decisions
: What factors impact sourcing decisions? The custom duties can be paid after the product has been acquired by the customer. True or False
|
|
Introduction to algorithms
: All problem / exercise numbers are from the 3nd edition of Introduction to Algorithms (the 1st and 2nd editions are different!) Note the difference between problems and exercises!
|
|
Explain the various definitions of disability
: Explain the various definitions of disability that are found in disability-income insurance. Explain the following disability insurance income provisions
|
|
What would you recommend smith do to help the situation
: Evelyn Smith, the new president of Texas Wings Inc., had been recruited to the company in 2004 by a disgruntled investor who had lost faith in the business's management team and profitability prospects. What would you recommend Smith do to help the..
|
|
Complete a chart with recommended coverage
: What should the Parkers consider when deciding what insurance coverage they need. Do they have sufficient insurance coverage. If not, what type of insurance coverage do you recommend for them
|
|
Explain how much total tax does he pay on the stock sale
: How much principal must be invested today for 5 years. during a period when the inflation rate is 2%, if the investor is in the 25% Federal and 4% State tax bracket for ordinary income but taxed at a 15% Federal rate for dividend income, to accumu..
|