Reference no: EM13936995
1. Let a[0..n-1] be an array of n distinct integers. A pair (a[i], a[j]) is said to be an inversion if these numbers are out of order, i.e., i j but a[i] > a[j].
For example: if array a contains the following numbers:
9, 8, 4, 5
then the number of inversions is 5.
(inversions are 9 > 8, 9 > 4, 9 > 5, 8 > 4, 8 > 5)
Write a program that uses the divide-and-conquer technique to count the number of inversion in the array. Describe briefly in a separate file how your divide-and-conquer algorithm works.
2. Given two lists of n integers A, B and a sum S, where all the elements in each list are unique, write a program that uses a transform-and-conquer algorithm with efficiency classT(nlogn) to decide whether there is an integer from A and an integer from B such that the sum of these two integers is equal to S.
For example, if A = {8, 3, 4, 7} and B = {5, 6, 12, 1} and S is 10, then your program should output "4 + 6 = 10" (where 4 is from A and 6 is from B)
Another example, if A = {1, 5, 4, 2} and B = {6, 3, 2, 1} and S is 9, then your program should output "No two integers from A and B add up to 9"
Describe briefly in a separate file how your transform-and-conquer algorithm works.Please note that a program using a brute-force algorithm with efficiency classT(n2) will NOT be marked.
3. Write a program that implements the distribution counting sort algorithm as discussed in class to sort a list of letters from a small set {a, b, c, d}. For example, the list contains b, a, c, c, d, d, a, your program should output a, a, b, c, c, d, d.
|
Classify individual cost items into one of four categories
: Classify the seven individual cost items into one of the four categories of prevention, appraisal, internal failure or external failure. Give two examples of non-financial performance measures Zaccaria could monitor as part of a total-quality-co..
|
|
Find ratio of a''s chance of winning a prize
: 'A' has three share in a lottery in which there are 3 prizes and 6 blanks' 'B' has one share in a lottery in which there is 1 prize and 2 blanks. Find ratio of A's chance of winning a prize to B's chance of winning a prizes.
|
|
What evolutionary line did mammals evolve from
: What evolutionary line did mammals evolve from? What is convergent evolution? Give an example, What was the first bird? It has characteristics of birds and dinosaurs; what are they?
|
|
What is the probability that 2 first spheres
: In a box there are 7 red spheres and 12 blue spheres. 2 spheres are taken without return. If the third sphere is red, what is the probability that 2 first spheres are blue ?
|
|
Write a program that implements the distribution counting
: Write a program that implements the distribution counting sort algorithm as discussed in class to sort a list of letters from a small set {a, b, c, d}. For example, the list contains b, a, c, c, d, d, a, your program should output a, a, b, c, c, d..
|
|
Describe one organism found in the paleozoic seas
: Describe how natural selection acted upon the peppered moth in England? What are two theories about why amphibians began to colonize land? What group did amphibians evolve from?
|
|
Explain the tree traversals in all orders
: If the node 30 is deleted, the erase algorithm selects which node as the replacement node?
|
|
A ticket is drawn at random.
: Tickets numbered 1 to 20 are mixed up and then a ticket is drawn at random. What is the probability that the ticket drawn has a number which is a multiple of 3 or 5?
|
|
Benefits of co-working and attract more membership
: What can Banyule DigiDECL do to educate more people about the benefits of co-working and attract more membership? What can they do to clearly convey their point of difference? (Amy)
|