COMP3121/9101 (Tutorial 2) School of Computer Science and Engineering, UNSW Sydney
To help you with what problems to try, problems marked with [K] are key questions that tests you on the core concepts, please do them first. Problems marked with [H] are harder problems that we recommend you to try after you complete all other questions (or perhaps you prefer a challenge). Good luck!!!
1 Recurrences
2 Divide and Conquer
Copyright By PowCoder代写 加微信 powcoder
3 Karatsuba’s trick
4 Selection
COMP3121/9101 (Tutorial 2) School of Computer Science and Engineering, UNSW Sydney §1 Recurrences
Exercise 1.1. [K] Determine the asymptotic growth rate of the solutions to the following recurrences. You may use the Master Theorem if it is applicable.
(a) T(n)=2T(n/2)+n(2+sinn).
(b) T(n) = 2T(n/2)+
(c) T(n) = 8T(n/2) + nlog2 n.
(d) T(n)=T(n−1)+n.
Exercise 1.2. [K] Explain why we cannot apply the Master Theorem to the following recurrences.
(a) T(n)=2nT(n/2)+nn. (b) T(n)=T(n/2)−n2logn.
(c) T(n)= 31T(n/3)+n. (d) T(n) = 3T(3n) + n.
Exercise 1.3. [H] Consider the following naive Fibonacci algorithm.
Algorithm 1.1 F(n): The naive Fibonacci algorithm Require: n ≥ 1
if n=1orn=2then return 1
return F(n−1)+F(n−2)
When analysing its time complexity, this yields us with the recurrence T (n) = T (n − 1) + T (n − 2). Show √
that this yields us with a running time of Θ(φn), where φ = 1+ 5 which is the golden ratio. How do you 2
propose that we improve upon this running time?
Hint — This is a standard recurrence relation. Guess T (n) = an and solve for a.
§2 Divide and Conquer
Exercise 2.1. [K] 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.
Design an algorithm that covers the entire board (except for the hole) with these “trominoes”. Note that the trominoes can be rotated and your solution should not try to brute force all possible placement of those “trominoes”.
COMP3121/9101 (Tutorial 2) School of Computer Science and Engineering, UNSW Sydney Exercise 2.2. [K] Given positive integers M and n, compute M n using only O(log n) many multiplications.
Exercise 2.3. [H] 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.
Exercise 2.4. [H] 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 produces the array M correctly, even in the very worst case.
Exercise 2.5. [H] 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 FF=10
Hint — A rather a tricky one !! The reasoning resembles a little bit the reasoning used in the celebrity problem (Tutorial Question 1.5): try comparing them in pairs and first find one or at most two possible candidates and then count how many times they appear.
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.
for all integers n ≥ 1.
(b) Hence or otherwise, give an algorithm that finds Fn in O(log n) time.
COMP3121/9101 (Tutorial 2) School of Computer Science and Engineering, UNSW Sydney Hint — You may wish to refer to Example 1.5 on page 28 of the “Review Material” booklet.
Exercise 2.6. [H] Let A be an array of n integers, not necessarily distinct or positive. Design a Θ(n log n) algorithm that returns the maximum sum found in any contiguous subarray of A.
§3 Karatsuba’s trick
Exercise 3.1. [K] 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).
Exercise 3.2. [K] Recall that the product of two complex numbers is given by (a + ib)(c + id) = ac + iad + ibc + ß2bd
= (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 multiplications.
Exercise 3.3. [H] Let P(x) = a0 +a1x+a2x2 +a3x3 and Q(x) = b0 +b1x+b2x2 +b3x3, and define R(x) = P (x) · Q(x). You are tasked to 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?
§4 Selection
Exercise 4.1. [K] Suppose we modify the median of medians quickselect algorithm to use blocks of 7
rather than 5. Determine the appropriate worst-case recurrence, and solve for the asymptotic growth rate.
Exercise 4.2. [K] 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.
Exercise 4.3. [K] 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.
Note — Note that there is an O(n) algorithm that solves this problem; however, the technique used in that solution is much more involved and will be taught in due time.
COMP3121/9101 (Tutorial 2) School of Computer Science and Engineering, UNSW Sydney Exercise 4.4. [H] 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]
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com