This document contains all the exercises, homework, and exams for CS5800 Spring 2019, taught by Emanuele Viola. The students have read-only access. January 22, 2019
Contents
1 Exercises
2 Homework1
3 7
1
Difficulty. Problems are marked with the level of difficulty, with the lowest being (Diffi- culty 1) and meaning as follows:
1. (Difficulty 1) means that the problem is just routine execution. The execution may be tricky, but is completely mechanical provided one has understood the lectures.
2. (Difficulty 2) means that the problem doesn’t require any new ideas, but it isn’t com- pletely mechanical either. It is appropriate for problems where the student has to map the problem to something from the lectures.
3. (Difficulty 3) is a problem that requires new ideas
4. (Difficulty 4) is a problem requires new ideas and is harder than (Difficulty 3)
On an exam, we also use these difficulty scores to assign points to question. If the exam has q questions with difficutlies di, i = 1, 2, . . . , q then question i is worth di/(i di). This allows to place the questions in different exams without having to recompute the scores each time.
2
1 Exercises
Problem 1. (Difficulty 2) For array A[1..n] define arg max A as the value i such that A[i] = max{A[1],A[2],…,A[n]}. For example, argmax of [4,6,18,2] is 3. Give code to compute arg max in linear time.
Problem 2. (Difficulty 2) For each of the following statement, say if it is true or false. If true, give a value for the constant c in the definition of Big-Oh such that the definition is satisfied. Recall that we write xyz for x(yz).
1. log(n2) = O(log n). 2. n2 = O(n).
2
√
3. n=O(2 logn).
4. log(n · log n) = O(log n).
5. 22100 log n = nO(1). 6. 2n2 = 2O(n).
7. (2n)2 = 2O(n).
Problem 3. (Difficulty 2) Return a list of the following functions separated by the symbol ≡or≪,wheref ≡gmeansf =Θ(g)andf ≪gmeansf =O(g). Youdonotneed to justify your answer. For example, if the functions are log n, n, 5n, 2n a correct answer is log n ≪ n ≡ 5n ≪ 2n. All logarithms are in base 2. One point for each correct symbol.
1. n
2. n4
3. 1/n
4. nlogn
11. (n+1000)2 12. 2n+logn
13. log2 n
14. log2(nlogn)
15. 13logn
16. loglogn 17. n2
18. (1.01)n 19. nlogn
20. 2n 3
5. 1
6.n1/ logn
7. logn! 8. 2n+10
9. n1/logn 10. log log2 n
√
Problem 4. (Difficulty 4) You are given as input an array A[1..n] whose entries all the numbers from 1 to n + 1 except exactly one of them.
(1) Give an algorithm to find the missing element in linear time.
(2) Give an algorithm to find the missing element in linear time and constant space.
(3) Now suppose you are missing two numbers from 1 to n + 2. Give a linear-time,
constant-space algorithm.
Problem 5. (Difficulty 2) Solve the following recurrence. Give both O(.) and Ω(.).
T (n) = 4T (n/2) + O(n).
Solution The recursion tree has depth log2 n. Level i contributes 4icn/2i = cn2i. The
sum of the costs is Θ(cn2log2 n) = Θ(n2).
Problem 6. (Difficulty 1) Simulate the Counting Sort on the following array of 10 numbers
A[] = {6,3,3,2,4,3,1,5,8,6}.
Write down the contents of the arrays after each loop of the algorithm.
Problem 7. (Difficulty 1) Simulate the Radix Sort in base 10 on the following array of 4 numbers
A[] = {123, 248, 143, 274}.
Write down the contents of the output array B[] during the execution of the algorithm.
Problem 8. Consider the algorithm Counting-Sort-II which is just like Counting Sort except that in the last loop we start from the first element instead of the last. That is, the line
for (j=n; 1 ; j – -)
is replaced with
for (j=1; n ; j ++).
Does Counting-Sort-II sort correctly? Justify your answer. Is Counting-Sort-II stable? Justify your answer.
Solution Counting-Sort-II sorts correctly. Specifically, its output is the same as that of Counting-Sort, except that each sequence of elements with equal keys is reversed.
Counting-Sort-II is not stable. For example, if (a, b) is the input and both a and b have key 1, the value of C[1] at the beginning of the last loop will be 2. Hence, a will be placed at location 2 and b at location 1.
Problem 9. Consider the algorithm Radix-Sort-II which is like Radix-Sort except that instead of sorting from the least significant digit to the most significant, we sort from the most significant to the least significant. Does Radix-Sort-II sort? Justify your answer.
4
Solution Radix-Sort-II does not sort. For example, consider the input (1,2), which is already sorted. This is written in binary as (01, 10). The array is already sorted with respect to the most significant binary digit. However, sorting with respect to the second results in (10, 01) = (2, 1), which is not sorted.
Problem 10. Give pseudocode for non-recursive Mergesort. Your code should only ac- cess the input through Merge(A,low,mid,high), a subroutine which merges A[low..mid] and A[(mid + 1)..high] into A[low..high]. You do not need to give the code for merge. Then analyze the running time of your algorithm.
Solution We can get some intuition opening up the recursion for recursive merge-sort on arrays of length 4.
Building on the intuition, we have the following pseudocode in the case in which n is a power of 2.
Bottom-Up-MergeSort(A[0..n − 1]) for(size=1; size < n; size = 2*size) {
for(i=0; i < n; i = i + 2*size) { Merge(i,i+size-1,i+2*size-1))
} }
The first for loop runs logn times. Then second for loop takes O(n) times, because it merges O(n/size) arrays of size size. Hence overall the time is O(n log n).
It remains to deal with the case in which n is not a power of 2. One way to deal with this is to modify the above code taking care of boundaries. Another way is to enlarge the array to length n′ which is a power of 2 by appending the corresponding number of copies of a special element INFINITY, which is bigger than anything else in the input array. Then we can call the above procedure, and simply truncate the output to the first n elements.
Problem 11. (Difficulty 3) Let A[1..n] be an array of n integers between 1 and n2. Give an O(n)-time O(n)-space algorithm to determine if the elements of A are distinct.
Let A[1..n] and B[1..n] be two arrays of n integers between 1 and n2. Give an O(n)-time O(n)-space algorithm to determine if A and B have a common element.
Solution (a) We use Radix Sort to sort the list. As the numbers are between 1 and n2, viewing each number in base-n, this takes O(2 · n) = O(n) time and O(n) space. Given a sorted list, we can check for duplicates by checking if any two adjacent numbers in the list are the same. This takes O(n) time and O(1) space. Therefore, the whole algorithm runs in O(n) time and O(n) space.
(b) We first sort A and B by Radix Sort and set the repeated numbers to 0. As seen in (a), this takes O(n) time and O(n) space. Now, we copy the non-zero numbers of A and B to an new array C. Note that A and B have a common element if and only if there is a duplicate in C. Use (a) to determine the latter. Overall the algorithm runs in O(n) time and O(n) space.
5
Problem 12. (Difficulty 2) Bubblesort and oblivious merge-sort each give a sequence of compare-exchange operations which sorts any array A[0..3]. Write down both sequences.
Problem 13. (Difficulty 4) For n distinct elements x1, x2, . . . , xn with positive weights w1, w2, . . . , wn such that ni=1 wi = 1, define the weighted median to be an index k sat- isfying i:xi
Problem 14. (Difficulty 3) Suppose we are given k sorted lists, each consisting of n elements. The multimerge problem is to merge the k lists into a single sorted list of length nk. Design an efficient algorithm for the multimerge problem. Analyze the running time of your algorithm. The more efficient your algorithm is in terms of its worst-case running time, the more credit you will get.
6
2 Homework 1
Problem 15. (Difficulty 3) Return a list of the following functions separated by the symbol ≡or≪,wheref ≡gmeansf =Θ(g)andf ≪gmeansf =O(g). Youdonotneed to justify your answer. For example, if the functions are log n, n, 5n, 2n a correct answer is log n ≪ n ≡ 5n ≪ 2n. All logarithms are in base 2. One point for each correct symbol.
1. 1/5
2. log(n)+5
3. (logn!)5
4. log(n5)
5. n1/5
6. (logn)5
7. n 8. 2n5
9. 1 10. n5
11. nlog 5 12. 25n
13. 5n 14. 2log n
15. 5n
16. 5 log(n)
17. 25 log log n 18. 5log n
19. 25 log n 20. n55
Problem 16. (Difficulty 3) Solve the following recurrences. Give both O(.) and Ω(.).
T(n) = 4T(n/3) + n, T(n) = 3T(n/4) + n, T(n) = 3T(n/4) + n2.
Problem 17. (Difficulty 2) Execute the Quick-Sort algorithm on the following array [5,2,6,1,3,4,7]
using the last element of the array as a pivot element. Show the contents of the array after each pass of partition.
Problem 18. (Difficulty 3) Give an algorithm running in time O(n) and space O(1) which sorts an array of n elements in the range {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Note that you cannot use another array of length n for the output because you are only allowed space O(1).
Problem 19. (Difficulty 3) You are given as input an array A[1..n] containing integer numbers from −n10 to n10. Give an O(n)-time algorithm to determine if there are two numbers which sum to 0.
7