Suppose a sorting algorithm takes 4 seconds to sort 100 items. How much time in seconds will the same algorithm take to sort 300 items if the number of operations the algorithm performs is exactly n2.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

1. (20 points)

 

• Suppose a sorting algorithm takes 4 seconds to sort 100 items. How much time in seconds will the same algorithm take to sort 300 items if the number of operations the algorithm performs is exactly n2.
• Suppose algorithm A takes 300n log2 n time and algorithm B takes 4n2 What is the smallest value of n (assuming n > 2) for which A will be faster than B? It may be difficult to do an exact calculation here;  if so, try to give an approximate answer.
• For each of the following, indicate whether the statement is true or false (no explanations necessary): i. 100n3 + 3n is O(n4)..
  1. 2n5 is O(n2).

• 6n5 is O(2n).

1. 5n3 + 2n + 3 is O(n3).
2. n3 is O(log2 n).

 

• If p(n) and q(n) are two functions such that p(n) is O(q(n)), does this always mean that for every value  of n, p(n)    q(n)?  If you think the answer is yes, give a justification.  If you think the answer is no, give     a counterexample i.e. find two functions p(n) and q(n) and a number y  such that p(n) is O(q(n)) and  p(y) > q(y).

2. (10 points)
   • Trace insertion sort on the list 5, 8, 1, 4, 9, 3 e. show what the list looks like after each iteration of the outer loop. Also, calculate the exact number of total data comparisons made. Note that a data comparison is when two different pieces of data are compared, and not when loop variables etc are compared.
   • Trace the merge algorithm (not the complete merge sort) on the two lists 2, 3, 7, 14 and 1, 6, 8, 9 Show what the combined list (i.e. the merged list) looks like after every step and also calculate the exact number of total data comparisons
3. (10 points) Consider the following sorting algorithm (the UNH sort) to sort an array A[1..n].

 

for i = n-1 downto 1 do for j = 1 to i do

if A[j] > A[j+1] then swap(A[j],A[j+1])

 

• Trace this sorting algorithm on the list 5, 8, 1, 4, 9, 3 i.e. show what the list looks like after each iteration of the outer Also, calculate the exact number of total data comparisons made.
• As we did with insertion sort in class, do a worst case analysis (use big O notation) of the running time of this You don’t have to give any explanations here - just state your answer.

 

• As we did with insertion sort in class, do a best case analysis (use big O notation) of the running time of this You don’t have to give any explanations here - just state your answer.

 

4. (20 points)

Let A and B be two sorted arrays, each with n elements. You have  to write an efficient algorithm which finds  out if A and B have any elements in common.

For example if A = [4, 7, 12, 15], B = [2,4,6,23000] the answer should be yes (since 4 is an element in common), if A = [4, 7, 900], B = [2,3, 28] the answer should be no. In terms of efficiency, the faster your algorithm is, the better.

• You will get full credit if your algorithm is correct and works in time O(n).

You will get substantial partial credit if your algorithm is correct and works in time smaller than O(n2) but bigger than O(n).

• You will get some partial credit if your algorithm is correct and works in time O(n2).
  • Give a very short and clear description in English of the basic idea behind your
  • Give the pseudocode
  • Trace your algorithm on the above two
  • Do a worst case time analysis (use big O notation) of your No explanation necessary.

 

5. (20 points) Let A[1], A[2], . . ., A[n], be n integers (possibly with repetitions) in the range 1 . . . k e. all the entries of the array A are between 1 and k. You want to repeatedly answer range queries of the form [a, b] where

1 a b k; each range query asks how many A[i]’s are in the range a . . . b, i.e., how many numbers from A lie between a and b. For example, if k = 10, and the array A has seven elements 5, 9, 3, 5, 10, 6, 1, 7 the range query [2, 7] asks how many numbers are there in the array A between 2 and 7, so the answer should be 5 (because the numbers 3,5,5,6,7 from A lie in the range [2, 7]). You want to do this efficiently. In order to do this, you first do some preprocessing, which is a one-time operation i.e. you are willing to pay the one-time relatively expensive cost of doing preprocessing before starting to answer the range queries, in order to save time with the many range queries which will follow. Your algorithm should work within the following time bounds:

• The one time preprocessing step should take O(n + k)

Each range query should be answered in O(1) (i.e. constant) time i.e. the amount of time to answer the range query [a, b] will be a small number which will in no way depend on n,k,A,a,b or the number of elements which actually lie in the range [a, b].

 

• For the pre-processing step
  1. Give a clear description of how your pre-processing step will work
  2. Give the pseudo-code for how your pre-processing step will work

• Trace your algorithm on the above example i.e. for the array A as above, show what will happen in the preprocessing

1. Do a worst case time analysis (use big O notation) of your algorithm for the preprocessing

• For the range query step
  1. Give a clear description of how your range query will work
  2. Give the pseudo-code for how your range query will work

• Show how your range query algorithm will work on the range query [2, 7].

1. Show how your range query algorithm will work on the range query [1, 9].
2. Do a worst case time analysis (use big O notation) of your algorithm for the range query

 

Hint: Think about counting sort discussed in class and in the textbook. You will need to keep the auxillary array C[1..k] we used for counting sort where C[j] represents the number of elements from A which are less than or equal to j. In the above example, C[2] will be 1 since there is one element (i.e. 1) in A which is  2; C[7] will be 6 since there are 6 elements (i.e. 1,3,5,5,6,7) which are 7. In class we saw how to fill C  in time O(n + k) (this is the preprocessing step), and once the array C is available, you should show how to use it to answer range queries in O(1) time.

 

6. (20 points)

In this part you have to come up with an algorithm to answer a more complicated range query, namely, given an array A as above, a range query [a, b] now requires you to actually list all of the A[i]’s in the range a . . . b. Using the same array A as above, the range query [2, 7] asks which numbers from A are there in the array A are between 2 and 7, so the answer should be 3,5,5,6,7 (it doesn’t matter in what order the numbers are outputted).

Your algorithm should work within the following time bounds:

The one time preprocessing step should take O(n + k) time (the preprocessing here will be different from that in the first part).

Given a range query [a, b],  the time taken to answer this query should not depend on k  or on n or on  the quantity b a; instead, the query should be answered in time O(t) where t is the number of elements  in the output (the number of A[i]’s in the range [a, b]). For example, if we consider two range queries, [a1, b1] and [a2, b2], [a1, b1] leads to an output of 500 elements, and [a2, b2] leads to an output of 100 elements, then answering [a1, b1] should take approximately 5 times as much time as answering [a2, b2]. Or consider another example, where k = 106, n = 105, a = 2000, b = 3000, and there are only three elements in the range [2000, 3000]. If you look at every entry in C between 2000 and 3000 i.e. you look at C[2000], C[2001], C[2002], . . . , C[3000], you are looking at b − a = 1001 entries which is too expensive since t = 3 is much smaller than b − 1 i.e. there are only three elements in the range [2000, 3000].

• For the pre-processing step

1. Give a clear description of how your pre-processing step will work
2. Give the pseudo-code for how your pre-processing step will work

• Trace your algorithm on the above example i.e. for the array A as above, show what will happen in the preprocessing

1. Do a worst case time analysis (use big O notation) of your algorithm for the preprocessing
   • For the range query step
2. Give a clear description of how your range query will work
3. Give the pseudo-code for how your range query will work

• Show how your range query algorithm will work on the range query [2, 7].

1. Show how your range query algorithm will work on the range query [1, 9].
2. Do a worst case time analysis (use big O notation) of your algorithm for the range query

 

Hint: You will need to keep one or more auxillary arrays; what these are going to be, you need to figure out. You should show how to fill these auxillary array(s) in time O(n + k) (this is the preprocessing step), and once these auxillary array(s) are available, you have to figure out how they can be used to quickly answer the range queries.

 

Extra Credit Problem 1: Implement (i.e. program) insertion sort, merge sort and UNH sort, run your programs on different random inputs (i.e. the inputs are generated using a random number generator) with 10,000 numbers, and compare the three algorithms on how much time they take. Hand in a hard copy of your code, a hardcopy of some sample runs and the timing analysis; the timing analysis (how much time each of the sorting programs actually takes) should be presented in an easy to understand way. A soft copy of your program should also be submitted on blackboard.

Extra Credit Problem 2: Implement (program) your algorithm to find out if there is an index k such that T [k] = k (problem 4), and show how it works on some examples. Hand in a hard copy of your code and a hardcopy of some sample runs. A soft copy of your program should also be submitted on blackboard.

Extra Credit Problem 3: Implement (program) your algorithm for the first range query problem (problem 5), and show how it works on some examples. Hand in a hard copy of your code and a hardcopy of some sample runs. A soft copy of your program should also be submitted on blackboard.

with this assignment on algorithms design and analysis.

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of