Determining the three-way comparisons

Assignment Help Basic Computer Science

Reference no: EM13968271

1. Propose an algorithm to sort a large ?le using only two tapes.

2. a. Show that a lower bound of N!/22N on the number of heaps is implied by the fact that buildHeap uses at most 2N comparisons.

b. Use Stirling's formula to expand this bound.

3. M is an N-by-N matrix in which the entries in each rows are in increasing order and the entries in each column are in increasing order (reading top to bottom). Consider the problem of determining if x is inM using three-way comparisons (i.e., one comparison of x with M[i][j] tells you either that x is less than, equal to, or greater than M[i][j]).

a. Give an algorithm that uses at most 2N - 1 comparisons.

b. Prove that any algorithm must use at least 2N - 1 comparisons.

Reference no: EM13968271

Questions Cloud

What are the arguments for abortion and against abortion : Moral Decision Making: Thinking Ethically Perhaps one of the most heated debates in healthcare ethics centers around the topic of abortion. Both the ethics and the legality of partial-birth abortions have been scrutinized in recent years. What are th..

What internal effectiveness factor largest catalyst particle : When considering mass transfer in this porous sphere scenario, there are several regions to consider. Draw and label these for a spherical particle. Assume that Da

Legally required to pay the additional amount : Jim Bowie owns a lot in Starr County and wants to build a house according to a certain set of plans and specifications. He solicits bids from three building contractors as follows: George Kimbell bids $ 175,000; Green Jameson bids $170,000; and, Davy..

In the context of single period inventory management : Direct Air operates a 300 seat jet from Toledo to Myrtle Beach, SC once a week. Cancellation distribution is normal with mean 30 and s.d. 8. A vacant seat in the jet is considered to cost $600 for the airline. What is the cost of shortage (in the con..

Determining the three-way comparisons : M is an N-by-N matrix in which the entries in each rows are in increasing order and the entries in each column are in increasing order (reading top to bottom). Consider the problem of determining if x is inM using three-way comparisons (i.e., one ..

Linear programming model-production and transportation costs : Linear Programming Model- Forbelt Corporation has a one-year contract to supply motors for all refrigerators produced by the Ice Age Corporation. Ice Age manufacturers the refrigerators at four locations around the country: Boston, Dallas, Los Angele..

Differentiate cosmological models on the nature : Objective: Differentiate cosmological models on the nature of the universe. Assignment Instructions: The Big Bang theory has today largely superseded the Steady State theory

Comparison-based sorting algorithm : 1. Prove that any comparison-based sorting algorithm requires 0.(N log N) compar- isons on average.

Focusing on improving health care delivery : It is increasingly clear that focusing on improving health care delivery is not suf?cient to reduce health disparities. How can we as a society begin to affect the broader factors that underlie racial and ethnic disparities in health?

User Account

All Pages