Design an algorithm that switches two arbitrary trucks

Assignment Help Data Structure & Algorithms

Reference no: EM132088482

You have a parking lot with parking spots numbered 1, 2, ..., n, to which n venture capitalists drive money-filled trucks of sizes a1, a2, ..., an (leaving no extra parking spaces).

You'd like to sort the trucks by size (so you can work your way down the list of trucks later talking with the venture capitalists about their terms), but you can only see along a limited distance of the parking lot at any one time, so (1) you can only compare the sizes of two trucks at most k parking spots away from each other1, and (2) you can only tell trucks at distance at most k from each other( That is, only trucks in spots i and j where |i - j| = k) to swap places.

a. Design an algorithm that compares two arbitrary trucks (not necessarily at distance at most k) in O(n/k) truck swaps (each of distance at most k), and returns any trucks that were moved in the process to their original positions.

b. Design an algorithm that switches two arbitrary trucks (not necessarily at distance at most k) in O(n/k) truck swaps (each of distance at most k), and returns any other trucks that were moved in the process to their original positions.

c. Describe an algorithm that sorts the trucks. You may possibly use the previous two parts

Reference no: EM132088482

Questions Cloud

What are some examples of group functions : What are some examples of group functions, and how do they differ from single-row functions

Heterozygous tongue-rolling mother and father : What are the genotype(s) and phenotypes(s) of the offspring from the cross of heterozygous tongue-rolling mother and father? (include ratios or percentages)

What are the possible genotypes for this cross : What are the possible genotypes for this cross?

Prepare journal entries to record the purchase of materials : The standard materials price is $2.10 per pound. The actual materials price was $2.00 per pound. Prepare the journal entries to record the purchase of materials

Design an algorithm that switches two arbitrary trucks : Design an algorithm that switches two arbitrary trucks (not necessarily at distance at most k) in O(n/k) truck swaps.

Indicate the phenotype : Dimples (D) is dominant to (d) no dimples. The Widow's peak (W) is dominant to no widow's peak (w). For each genotype, indicate the phenotype.

Create a main method to demonstrate the jvm throwing : Create a main method to demonstrate the jvm throwing each of these exceptions. You might have to dig around a bit to find out what they are.

Compute cost of goods sold expense : Martin Corp. began the year with 2,000 units of inventory that had been purchased for $6 per unit. Compute cost of goods sold expense

Draw a legal binary min heap that stores these keys : Draw a legal binary min heap that stores these keys such that after deleting 8 from the heap, the resulting repair of the binary heap involves.

User Account

All Pages