COMP3121/9101 (Tutorial 1) School of Computer Science and Engineering, UNSW Sydney List of Abbreviations and Symbols
A[1..n] An array indexed from 1 to n of n elements.
N Set of all nature numbers, i.e., {1, 2, 3, . . . }.
R Set of all real numbers.
Copyright By PowCoder代写 加微信 powcoder
Z Set of all integers, i.e., {…,−2,−1,0,1,2,…}.
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 Introductory problems
2 Searching algorithms
3 Sorting algorithms
4 Complexity analysis
COMP3121/9101 (Tutorial 1) School of Computer Science and Engineering, UNSW Sydney
§1 Introductory problems
Exercise 1.1. [K] 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 time O(n). Thus, you have to find the values of all of the sums
S[1] = A[1] + A[2] + . . . + A[n − 1] + A[n]; S[2] = A[2] + A[3] + . . . + A[n] + A[n + 1];
S[n] = A[n] + A[n + 1] + . . . + A[2n − 2] + A[2n − 1], and your algorithm should run in time O(n).
Exercise 1.2. [K] Given an array A[1..n] which contains all natural numbers between 1 and 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.
Exercise 1.3. [K] You are given an array A of n distinct integers.
(a) You have to determine if there exists a number (not necessarily in A) which can be written as a sum of
squares of two distinct numbers from A in two different ways (note: A[m]2 + A[k]2 and A[k]2 + A[m]2
counts 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 n = O(n4) 4
such quadruples.
(b) Solve the same problem but with an algorithm which runs in the expected time of O(n2).
Exercise 1.4. [H] 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 students 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.
Exercise 1.5. [H] 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
Hint — first, use part (c) to consider how you would solve it in the case where every student received at least one vote. Then, apply part (b).
COMP3121/9101 (Tutorial 1) School of Computer Science and Engineering, UNSW Sydney
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).
(a) Show that your task can always be accomplished by asking no more than 3n − 3 such questions, even in the worst case.
(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.
Exercise 1.6. [H] 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.
Exercise 1.7. [H] 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 (Tutorial 1) School of Computer Science and Engineering, UNSW Sydney §2 Searching algorithms
Exercise2.1. [K]LetM beann×nmatrixofdistinctintegersM(i,j),1≤i≤n,1≤j≤n. Eachrow 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.
Exercise 2.2. [K] 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.
Exercise 2.3. [K] Assume you have an array of 2n distinct integers. Find the largest and the smallest number using 3n − 2 comparisons only.
Exercise 2.4. [K] Let f : N → Z be a monotonically increasing function. That is, for all i ∈ N, we have thatf(i)