COMP3121/9101
Algorithm Design
Copyright By PowCoder代写 加微信 powcoder
PROBLEM SET 1 – INTRODUCTION
[K] – key questions [H] – harder questions [E] – extended questions [X] – beyond the scope of this course
1 SECTION ONE: INTRODUCTORY PROBLEMS 2
2 SECTION TWO: SEARCHING ALGORITHMS 4
3 SECTION THREE: SORTING ALGORITHMS 6
4 SECTION FOUR: TIME COMPLEXITY ANALYSIS 7
PROBLEM SET 1 SECTION ONE: INTRODUCTORY PROBLEMS
§ SECTION ONE: INTRODUCTORY PROBLEMS
[K] Exercise 1. You are given an array A[1 . . . 2n − 1] of integers. Design an algorithm which finds all of the n
possible sums of n consecutive elements of A which runs in O(n); that is, you have to find the values of the sums
S[1] = A[1] +A[2] + · · ·+A[n];
S[2] = A[2] +A[3] + · · ·+A[n+ 1];
S[n] = A[n] +A[n+ 1] + · · ·+A[2n− 1].
[K] Exercise 2. Given an array A[1, . . . , n] which contains all natural numbers from 1 to n− 1, design an algorithm
that runs in O(n) time and returns the duplicate value, using
(a) O(n) additional space;
(b) O(1) additional space.
[K] Exercise 3. You are given an array A of n distinct integers.
(a) You have to determine if there exist a number (not necessarily in A) which can be written as a sum of two distinct
numbers from A in two different ways (note that A[m]2 + A[k]2 and A[k]2 + A[m]2 count as a single way), and
which runs in time n2 log n in the worst case performance.
Note that the brute force algorithm would examine all quadruples of elements in A and there are
such quadruples.
(b) Solve the same problem but with an algorithm which runs in the expected time of O(n2).
[H] Exercise 4. You are conducting an election among a class of n students. Each student casts precisely one vote
by writing their name, and that of their chosen classmate on a single piece of paper. We assume that students are not
allowed to vote for themselves. However, the students have forgotten to specify the order of names on each piece of
paper – for instance, “ ” could mean that Alice voted for Bob, or that Bob voted for Alice!
(a) Show how you can still uniquely determine how many votes each student received.
(b) Hence, explain how you can determine which students did not receive any votes. Can you determine who these
people voted for?
(c) Suppose every student received at least one vote. What is the maximum possible number of votes received by
any student? Justify your answer.
(d) Using parts (a) and (c), or otherwise, design an algorithm that constructs a list of votes of the form “X voted
for Y ” consistent with the pieces of paper. Specifically, each piece of paper should match up with precisely one
of these votes. If multiple such lists exist, produce any. An O(n2) algorithm earns partial credit, but you should
aim for an O(n) algorithm.
[H] Exercise 5. You are at a party attended by n people (not including yourself), and you suspect that there might
be a celebrity present. A celebrity is someone known by everyone, but who does not know anyone else present. Your
task is to work out if there is a celebrity present, and if so, which of the n people present is a celebrity. To do so, you
can ask a person X if they know another person Y (where you choose X and Y when asking the question).
COMP3121/9101 – Term 3, 2022 2
PROBLEM SET 1 SECTION ONE: INTRODUCTORY PROBLEMS
(a) Show that your task can always be accomplished by asking no more than 3n− 3 such questions, even in the worst
(b) Show that your task can always be accomplished by asking no more than 3n− ⌊log2 n⌋ − 3 such questions, even
in the worst case.
[H] Exercise 6. There are N teams in the local cricket competition and you happen to have N friends that keenly
follow it. Each friend supports some subset (possibly all, or none) of the N teams. Not being the sporty type – but
wanting to fit in nonetheless – you must decide for yourself some subset of teams (possibly all, or none) to support.
You don’t want to be branded a copycat, so your subset must not be identical to anyone else’s. The trouble is, you
don’t know which friends support which teams, so you can ask your friends some questions of the form “Does friend A
support team B?” (you choose A and B before asking each question). Design an algorithm that determines a suitable
subset of teams for you to support and asks as few questions as possible in doing so.
[H] Exercise 7. You are in a square orchard of 4n by 4n equally spaced trees. You want to purchase apples from
precisely n2 many of those trees, which also form a square. Fortunately, the owner is allowing you to choose such a
square anywhere in the orchard and you have a map with the number of apples on each tree. Your task is to choose a
square that contains the largest amount of apples and which runs in time O(n2). Note that the brute force algorithm
would run in time Θ(n4).
COMP3121/9101 – Term 3, 2022 3
PROBLEM SET 1 SECTION TWO: SEARCHING ALGORITHMS
§ SECTION TWO: SEARCHING ALGORITHMS
[K] Exercise 8. Let M be an n × n matrix of distinct integers M(i, j), 1 ≤ i ≤ n, 1 ≤ j ≤ n. Each row and each
column of the matrix is sorted in the increasing order, so that for each row i, 1 ≤ i ≤ n,
M(i, 1) < M(i, 2) < . . . < M(i, n) and for each column j, 1 ≤ j ≤ n, M(1, j) < M(2, j) < . . . < M(n, j). You need to determine whether M contains an integer x in O(n) time. [K] Exercise 9. You are given an array of A[1..2n] distinct integers. You are tasked to find the largest and the second largest number using only 2n + n− 2 comparisons. [K] Exercise 10. Assume you have an array of 2n distinct integers. Find the largest and the smallest number using 3n− 2 comparisons only. [K] Exercise 11. Let f : N → Z be a monotonically increasing function. That is, for all i ∈ N, we have that f(i) < f(i+ 1). Our goal is to find the smallest value of i ∈ N so that f(i) ≥ 0. Design an O(log n) algorithm to find the value of i so that f(i) ≥ 0 for the first time. [K] Exercise 12. You’re given an array A[1..n] of integers, and you are required to answer a series of n queries, each of the form: “how many elements of the array have a value between L and R (inclusively)?”, where L and R are integers. Design an O(n log n) algorithm that answers all n of these queries. [H] Exercise 13. Assume you are given two arrays A and B, each containing n distinct positive numbers and the equation x8 − x4y4 = y6 + x2y2 + 10. Design an algorithm which runs in time O(n log n) which finds if A contains a value for x and B contains a value for y that satisfy the equation. [H] Exercise 14. You are a fisherman, trying to catch fish with a net that is W meters wide. Using your advanced technology, you know that the positions of all N fish in the sea can be represented as integers on a number line. There may be more than one fish at the same location. To catch the fish, you will cast your net at position x, and will catch all fish with positions between x and x + W , inclusive. Given N , W and an array X[1..N ] denoting the positions of fish in the sea, give an O(N logN) algorithm to find the maximum number of fish you can catch by casting your net once. For example, if N = 7,W = 3 and X = [1, 11, 4, 10, 6, 7, 7], then the most fish you can catch is 4: by placing your net at x = 4, you will catch one fish at position 4, one fish at position 6 and two fish at position 7. [H] Exercise 15. Your army consists of a line of N giants, each with a certain height. You must designate precisely L ≤ N of them to be leaders. Leaders must be spaced out across the line; specifically, every pair of leaders must have at least K ≥ 0 giants standing in between them. Given N,L,K and the heights H[1..N ] of the giants in the order that they stand in the line as input, find the maximum height of the shortest leader among all valid choices of L leaders. We call this the optimisation version of the problem. COMP3121/9101 – Term 3, 2022 4 PROBLEM SET 1 SECTION TWO: SEARCHING ALGORITHMS For instance, suppose N = 10, L = 3,K = 2 and H = [1, 10, 4, 2, 3, 7, 12, 8, 7, 2]. Then among the 10 giants, you must choose 3 leaders so that each pair of leaders has at least 2 giants standing in between them. The best choice of leaders has heights 10, 7 and 7, with the shortest leader having height 7. This is the best possible for this case. (a) In the decision version of this problem, we are given an additional integer T as input. Our task is to decide if there exists some valid choice of leaders satisfying the constraints whose shortest leader has height no less than Give an algorithm that solves the decision version of this problem in O(N) time. (b) Hence, show that you can solve the optimisation version of this problem in O(N logN) time. COMP3121/9101 – Term 3, 2022 5 PROBLEM SET 1 SECTION THREE: SORTING ALGORITHMS § SECTION THREE: SORTING ALGORITHMS [K] Exercise 16. You are given an array A[1..n] of integers and another integer x. (a) Design an O(n log n) algorithm (in the sense of the worst case performance) that determines whether or not there exist two elements in A whose sum is exactly x. (b) Design an algorithm that accomplishes the same task, but runs in O(n) expected (i.e., average) time. [K] Exercise 17. Given two arrays of n integers, design an algorithm that finds out in O(n log n) steps if the two arrays have an element in common. [K] Exercise 18. Suppose that you are taking care of n kids, who took their shoes off. You have to take the kids out and it is your task to make sure that each kid is wearing a pair of shoes of the right size (not necessarily their own, but one of the same size). All you can do is to try to put a pair of shoes on a kid, and see if they fit, or are too large or too small; you are NOT allowed to compare a shoe with another shoe or a foot with another foot. Describe an algorithm whose expected number of shoe trials is O(n log n) which properly fits shoes on every kid. [H] Exercise 19. Given n real numbers x1, . . . , xn in the interval [0, 1), devise an algorithm that runs in linear time which outputs a permutation of the n numbers, say y1, . . . , yn, such that |yi − yi−1| < 2. [H] Exercise 20. Given n real numbers x1, . . . , xn where each xi is a real number in the interval [0, 1), devise an algorithm that runs in linear time and that will output a permutation of the n numbers, say y1, . . . , yn, such that |yi − yi−1| < 1.01. COMP3121/9101 – Term 3, 2022 6 PROBLEM SET 1 SECTION FOUR: TIME COMPLEXITY ANALYSIS § SECTION FOUR: TIME COMPLEXITY ANALYSIS [K] Exercise 21. Determine if f(n) = Ω(g(n)), f(n) = O(g(n)), both (i.e. f(n) = Θ(g(n))) or neither for the following pairs. Justify your answers. log2 n) + 2 log2 n n100 2n/100 n1.001 n log2 n n(1+sin(πn/2))/2 Exercise 22. Classify the following pairs of functions by their asymptotic relation; that is, determine if f(n) = O(g(n)), f(n) = Ω(g(n)), both (i.e. f(n) = Θ(g(n))) or neither. (a) [K] f(n) = 1/n, g(n) = sin(1/n). (b) [K] f(n) = log (n!), g(n) = log (nn). What does this say about the growth rate between f1(n) = n! and (c) [H] f(n) = nlogn, g(n) = (logn)n. (d) [H] f(n) = (−1)n, g(n) = tan(n). (e) [H] f(n) = n5/2, g(n) = [X] Exercise 23. Define f : N → R by 1 if n ≤ 2, + n if n ≥ 3. Show that f(n) = Θ(n). COMP3121/9101 – Term 3, 2022 7 SECTION ONE: INTRODUCTORY PROBLEMS SECTION TWO: SEARCHING ALGORITHMS SECTION THREE: SORTING ALGORITHMS SECTION FOUR: TIME COMPLEXITY ANALYSIS 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com