=========================preview======================
(COMP3711)[2011](f)midterm~rahuja^_83163.pdf
Back to COMP3711 Login to download
======================================================
COMP 3711 Design and Analysis of Algorithms Fall 2011 Midterm Exam
Student name: Student ID: Email: Lecture session:
Question Score Maximum Question Score Maximum
1 10 5 20
2 10 6 10
3 6 7 15
4 15 8 14
TOTAL:
Instructions
1.
Print your name, student ID, and section number (L1 or L2) at the top of every page (in case the staple falls out!).
2.
This is a closed-book, closed-notes, open-brain exam.
3.
Time limit: 120 minutes.
4.
You should answer all the questions on the exam. At least you should read all the questionsthey are not ordered by their di.culty!
5.
You can write on the back of the paper if you run out of space. Please let us know if you need more scratch paper.
6.
The cheat sheet is provided at the end of the exam paper.
7.
Any log has base 2 unless explicitly stated otherwise.
8.
Relax and breathe, its just a midterm.
1. (10 pts) For each pair of expressions (A, B) below, indicate whether A is O, , or of B. Note that zero, one, or more of these relations may hold for a given pair. List all correct ones.
(a)
A = n3,B = n2 + 100n;
(b)
A = log100 n, B = log n;
(c)
A =2n,B =2n+log n;
(d)
A = log n2,B = log2 n;
(e)
A = log n, B = 100100 .
2. (10 pts) Give asymptotic upper bounds for T (n) under the following recurrences. Make your bounds as tight as possible. A correct answer will gain full credits; otherwise, showing the steps may gain you partial credits.
(a)
T (1) = 1; T (n)=4T (n/4) + 100n for n> 1.
(b)
T (1) = 1; T (n)= T (n . 1) + log n for n> 1.
3.
(6 pts) Suppose we use Radix Sort to sort n integers, each with b bits. If we require the sorting to take O(n) time, how large can b be? State your answer using the O notation.
4.
(15 pts) We say that an array A[1...n] is k-sorted if the array can be divided into k blocks with n/k elements in each block, such that the elements in each block are larger than the elements in earlier blocks, and smaller than elements in later blocks. The elements in each block need not be sorted. For example, the array [5, 2, 3, 7, 6, 8, 10, 11, 12, 20, 14, 13] is 4-sorted. Please design an O(n log k) algorithm that k-sorts an arbitrary array. You may assume that both n are k are powers of 2.
5.
(20 pts) It is said that the following problem has been used by Google as one of their interview questions. Let S1 and S2 be two arrays, each of size n, that are already sorted. Lets assume that all elements in the two arrays are distinct and n is a power of 2.
(a)
(15 pts) Design an O(log n)-time algorithm to .nd the median in the union of the two arrays. Since there are 2n elements in total, we de.ne the median to be the n-th smallest element. [Hint: Compare the median of S1 and the median of S2. Then what can you say about the median of S1 S2?] You can still get partial credits for this problem if you give a slower algorithm.
(b)
(5 pts)