Tutorial 2 – Problems
COMP3121/9101
1. Determine the asymptotic growth rate of the solutions to the following recur-
rences. You may use the Master Theorem if it is applicable.
Copyright By PowCoder代写 加微信 powcoder
(a) T(n)=2T(n/2)+n(2+sinn) (b) T(n)=2T(n/2)+√n+logn
(c) T(n) = 8T(n/2) + nlog2 n (d) T(n)=T(n−1)+n
2. You are given a 2n × 2n board with one of its cells missing (i.e., the board has a hole). The position of the missing cell can be arbitrary. You are also given a supply of “trominoes”, each of which can cover three cells as below.
Your task is to design an algorithm which covers the entire board (except for the hole) with these “trominoes”. Note that the trominoes can be rotated.
3. You and a friend find yourselves on a TV game show! The game works as follows. There is a hidden N ×N table A. Each cell A[i, j] of the table contains a single integer and no two cells contain the same value. At any point in time, you may ask the value of a single cell to be revealed. To win the big prize, you need to find the N cells each containing the maximum value in its row. Formally, you need to produce an array M [1..N ] so that A[r, M [r]] contains the maximum value in row r of A, i.e., such that A[r,M[r]] is the largest integer
among A[r, 1], A[r, 2], . . . , A[r, N ]. In addition, to win, you should ask at most 2N⌈logN⌉ many questions. For example, if the hidden grid looks like this:
Column 1 Column 2 Column 3 Column 4 Row1 10 5 8 3 Row2 1 9 7 6 Row3 -3 4 -1 0 Row4 -10 -9 -8 2
then the correct output would be M = [1, 2, 2, 4].
Your friend has just had a go, and sadly failed to win the prize because they asked N2 many questions which is too many. However, they whisper to you a hint: they found out that M is non-decreasing. Formally, they tell you that M[1] ≤ M[2] ≤ ··· ≤ M[N] (this is the case in the example above).
Design an algorithm which asks at most O(N log N) many questions that pro- duces the array M correctly, even in the very worst case.
Hint: Note that you do not have enough time to find out the value of every cell in the grid! Try determining M[N/2] first, and see if divide-and-conquer is of any assistance.
4. Given positive integers M and n, compute M n using only O(log n) many mul- tiplications.
5. Define the Fibonacci numbers as
F0 =0,F1 =1, andFn =Fn−1+Fn−2 foralln≥2.
Thus, the Fibonacci sequence is as follows: 0,1,1,2,3,5,8,13,21,….
(a) Show, by induction or otherwise, that
Fn+1 Fn 1 1n
for all integers n ≥ 1.
(b) Hence or otherwise, give an algorithm that finds Fn in O(log n) time.
Hint: You may wish to refer to Example 1.5 on page 28 of the “Review Mate- rial” booklet.
FF=10 n n−1
6. Suppose you are given an array A containing 2n numbers. The only operation that you can perform is make a query if element A[i] is equal to element A[j], 1 ≤ i, j ≤ 2n. Your task is to determine if there is a number which appears in A at least n times using an algorithm which runs in linear time.
Warning and a Hint: a really tricky one. The reasoning resembles a little bit the reasoning used in the celebrity problem: try comparing them in pairs and first find one or at most two possible candidates and then count how many times they appear.
7. Let P(x) = a0 +a1x and Q(x) = b0 +b1x, and define R(x) = P(x)·Q(x). Find the coefficients of R(x) using only three products of pairs of expressions each involving the coefficients ai and/or bj.
Addition and subtraction of the coefficients do not count towards this total of three products, nor do scalar multiples (i.e. products involving a coefficient and a constant).
8. Let P(x) = a0 +a1x+a2x2 +a3x3 and Q(x) = b0 +b1x+b2x2 +b3x3, and define R(x) = P (x) · Q(x). Find the coefficients of R(x) using only twelve products of pairs of expressions each involving the coefficients ai and/or bj.
Challenge: can you do better?
9. Recall that the product of two complex numbers is given by (a + ib)(c + id) = ac + iad + ibc + i2bd
= (ac−bd)+i(ad+bc)
(a) Multiply two complex numbers (a + ib) and (c + id) (where a, b, c, d are all
real numbers) using only 3 real number multiplications.
(b) Find (a + ib)2 using only two multiplications of real numbers.
(c) Find the product (a + ib)2(c + id)2 using only five real number multiplica- tions.
10. Suppose we modify the median of medians quickselect algorithm to use blocks of seven rather than five. Determine the appropriate worst-case recurrence, and solve for the asymptotic growth rate.
11. Given an array A of n distinct integers and an integer k < n2 , design an O(n) algorithm which finds the median as well as the k values closest to the median from above and below. You may assume that n is odd.
12. Given two sorted arrays A and B, each of length n, design a O(log n) algorithm to find the (lower) median of all 2n elements of both arrays. You may assume that n is a power of two and that all 2n values are distinct.
13. Let A be an array of n distinct integers, each with an associated weight wi. All wi are non-negative, and w1 + . . . + wn = 1. The weighted (lower) median is the element A[k] satisfying
wi<12and wi≤12. A[i]
Design a O(n) algorithm to find the weighted (lower) median.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com