代做LCOMP3121、代写c/c++，Java语言编程

日期：2024-06-21 08:07

M LCOMP3121/9101

Algorithm Design and Analysis

J K

Tutorial 2

Divide and Conquer

Announcements

Attached at the end of the tutorial sheet is an appendix with further information

about recurrences. If you are struggling with understanding recurrences, you may

wish to refer to the appendix.

COMP3121/9101: Algorithm Design and Analysis 2024, Term 2

1 This Week, in summary...

The divide and conquer paradigm breaks a problem down into multiple subproblems and then com-

bines solutions to these subproblems to solve the original problem. We need to specify three steps.

– Divide. Splits the current problem instance into (two or more) problems of strictly smaller size.

– Conquer. Recursively splits the problem instances until the splitting stage can no longer be

performed. Once we reach the base cases, we can solve those individually.

– Combine. Uses solutions to smaller subproblems and merges them to obtain the solution to

the current problem instance.

See section 4 for a more detailed description of the process.

The Master Theorem is a general framework for computing the asymptotic solution of a recurrence.

Let T (n) = aT (n/b) + f(n), where a ≥ 1 and b > 1. The theorem says that:

– if there exist a constant ? > 0 such that f(n) = O (nlogb a??), then T (n) = Θ (nlogb a).

– if f(n) = Θ (nlogb a), then T (n) = Θ (nlogb a log n).

– if there exist a constant ? > 0 such that f(n) = ? (nlogb a+?) and if af(n/b) ≤ cf(n) for some

constant c < 1 for all sufficiently large n, then T (n) = Θ (f(n)).

– if the recurrence does not fit into any of the above cases, then the theorem cannot be applied

and other techniques must be used.

Lecture Problems, Key Takeaways

Maximum Median.

– If target t is achievable, then smaller targets are also achievable; if target t is not achievable, then

larger targets are also not achievable. Therefore, the problem of deciding is target t achievable?

is monotonic.

– Binary search for t between interval [A[n], A[n] + k].

– Time complexity. Deciding if target t is achievable takes O(n) time; binary search over a space

of length k; therefore, overall time complexity is O(n log k).

Merge Sort.

– Divide. Splits the array into two halves.

– Conquer. Sort each half recursively.

– Combine. Merge two halves together in O(n) time.

– Time complexity. Recurrence is given by T (n) = 2T (n/2)+O(n), which is T (n) = O(n log n).

Counting inversions.

– Divide. Splits the array into two halves.

– Conquer. Computes the number of inversions in each half recursively.

– Combine. Count the number of inversions that cross the dividing line in O(n) time.

– Time complexity. Recurrence is given by T (n) = 2T (n/2)+O(n), which is T (n) = O(n log n).

? Quick Sort.

– Divide. Choose pivot and partition array around it in O(n) time.

– Conquer. Sort both sides of the pivot recursively.

1

COMP3121/9101: Algorithm Design and Analysis 2024, Term 2

– Combine. Pass answer up the recursion tree.

– Time complexity. T (n) = O(n log n) in the average case; T (n) = O(n2) in the worst case,

depending on pivot choice.

Karatsuba. Split the two input integers into

A = A1 · 2n/2 +A0, B = B1 · 2n/2 +B0.

We now compute AB with the expression

AB = A1B1 · 2n + [(A1 +A0)(B1 +B0)?A1B1 ?A0B0] 2n/2 +A0B0.

– Time complexity. Recurrence is given by T (n) = 3T (n/2) + c · n, which is T (n) = Θ (nlog2 3).

2

COMP3121/9101: Algorithm Design and Analysis 2024, Term 2

2 Binary Search

When we wanted to decide if an element x exists in an array A, we required n queries in the worst-case!

If we know further information about the properties of our input, we can make further improvements to

reduce the running time or memory usage. Binary search is an optimisation technique that reduces the

number of queries from n down to ?log2 n?. However, for binary search to be effective, we require two

properties to hold.

Well-defined interval. If we want to query the middle element, we need a well-defined interval to begin

with so that the middle element is defined.

Monotonicity. If we remove a set of elements, we should ensure that we never have to query any of the

elements that we previously tossed out.

A monotonic array looks like a sorted or reverse sorted array. For example, consider the array A =

. If we want to check if A consists of the element 2, then we can first query 0. Since A

is sorted (monotonic), we know that any element to the left of 0 will never be larger than 0 and so, we can

safely remove all such elements to the left. This drastically improves the running time of our first algorithm

where we check all of the elements of the array, especially when the number of elements becomes large!

In the following problems, be sure to check that the two above properties hold before simply applying

binary search!

2.1 Identity Element

Let A[1..n] be a sorted array of n distinct integers. Some of these integers may be positive, negative,

or zero. Design an O(log n) algorithm to decide if there exist some index i such that A[i] = i.

Hint. Consider constructing a new array B such that B[i] = A[i]? i.

Exercise. Further, suppose we now know that A[1] > 0. Answer the same problem in O(1) time.

2.2 Search in Rotated Sorted Array (#33)

Let A[1..n] be an array of n integers. We are given an additional integer x, and our goal is to decide

whether x appears somewhere in A.

(a) Without any additional information aboutA, design a linear-time algorithm that decides whether

x appears somewhere in A.

(b) Now, suppose you know that A is a sorted array. Design an O(log n) algorithm that decides

whether x appears somewhere in A.

(c) Now, suppose you know that A is a sorted array but it has been shifted by k units to the right.

For example, if k = 4 and the sorted array was [1, 2, 3, 5, 6, 7], then A = [5, 6, 7, 1, 2, 3]. In this

scenario, suppose we are given k in advance. Design anO(log n) algorithm that decides whether

x appears somewhere in A.

Note. You are given, as input, an array that is promised to be shifted by k units to the right, where

k is known.

(d) Finally, suppose that we do not know what k is. Design an O(log n) algorithm that decides

whether x appears somewhere in A.

Hint. If we can find k in O(log n) time, then we can just use the previous algorithm.

3

COMP3121/9101: Algorithm Design and Analysis 2024, Term 2

2.3 Order Statistic of Two Sorted Arrays

Let A[1..n] and B[1..n] be two sorted arrays. For simplicity, assume that A and B share no common

elements and all elements in each array are distinct. We construct a new array C[1..2n] by merging

A and B together.

Given an integer k, where 1 ≤ k ≤ 2n, we want to design an algorithm to find the kth smallest

element in C.

(a) Design an O(n log n) algorithm that finds the kth smallest element in C.

Hint. This is really easy...

(b) Design an O(k) algorithm that finds the kth smallest element in C.

(c) Design an O(log n) algorithm that finds the kth smallest element in C.

Hint. How does this problem relate to median finding? Do we obtain further information by

comparing an element of A with an element of B?

4

COMP3121/9101: Algorithm Design and Analysis 2024, Term 2

3 Applications of Binary Search

3.1 Unbounded Binary Search

To directly apply binary search, we needed a well-defined interval. However, what happens when we are

not given the interval directly? We will need to artificially construct the interval.

Let A be a sorted array of distinct elements. However, you are not given the size of A. Your task is to

find the smallest index i so that A[i] > 0, or report that no such index exists. Of course, we can just

check each element one by one. Aim to design a more efficient algorithm.

Hint. Try to artificially construct an interval to binary search over.

3.2 Discrete Binary Search

Binary search works well when the array we want to binary search over is monotonic. Discrete binary

search directly toys with this idea. Instead of an array of integers where the monotonicity is clear, we can

additionally construct a boolean array.

What does monotonicity mean here?

Definitions.

Subsequence. A subsequence of a string S is a string T that can be formed by deleting some

or no characters from S without changing the relative order of the remaining elements. For

example, if S = Comp3121AndComp9101, then we can form the subsequence T = 3121n9101.

Substring. A substring of a string S is a contiguous string T that forms a subsequence of S.

Supersequence. A supersequence of a string T is a string S that contains T as a subsequence

of S.

Superstring. A superstring of a string T is a string S that contains T as a substring of S.

You are given a string S of n characters and another string T of m characters such that m ≤ n. You

want to find the length of the longest subsequence of S that appears as a prefix of T . For example, if

S = abcdefgh and T = bcdghf, then your algorithm should return 5.

(a) Let T ′ be a prefix of T . Show that:

If T ′ is a subsequence of S, then any substring of T ′ is also a subsequence of S.

If T ′ is not a subsequence of S, then any superstring of T ′ is not a subsequence of S.

(b) For a given string A of n characters and another string B ofm characters (withm ≤ n), assume

that there is an O(f(n)) algorithm that decides if B is a subsequence of A. Using this algorithm,

describe an O(f(n) logm)-time algorithm to compute the length of the longest subsequence of

S that appears as a prefix of T .

5

COMP3121/9101: Algorithm Design and Analysis 2024, Term 2

4 Solving problems with Divide and Conquer

4.1 Designing the algorithm

To solve a problem with divide and conquer, we need to describe two steps in our algorithm: how we

divide our problem instance into multiple (usually two or more) subproblems, and how we combine the

solutions to the subproblems to solve the original problem. However, the process by which we do this

comes in three steps.

4.1.1 Dividing the instance

The first step is to find a suitable method of dividing the problem instance. We need to ensure that the

subproblems constructed are of the same type; after all, we will be calling the magical recursion wizard to

do the work for us. But for the wizard to do its work, we need to ensure that the problem instance mirrors

the original problem we wanted to solve (see the tiling problem).

There are usually many ways of appropriate dividing the problem instance; however, the intended division

lends itself nicely to a clean combine step (see merge sort).

4.1.2 Conquering each subproblem

We can loosely describe the conquer step as follows:

If the current problem instance is easy, we solve it directly ourselves.

Otherwise, we simplify the problem instance by transforming it into (usually two or more) smaller

instances of the same problem.

If the self-referential description is confusing, we can imagine asking a recursion wizard to solve our

smaller problem instances. However, there is one catch here:

If you ask the wizard to solve the current problem, it will be able to solve all subproblem instances

that are strictly smaller.

The wizard can only solve the problem when the input is in the appropriate format.

The wizard will send you the solution to all subproblems and will ask you to use those solutions to

solve the original problem.

4.1.3 Combining solutions

Once we have solutions to the smaller subproblems from the recursion wizard, we need a way to merge

them together to answer the original problem. The combine step may be as simple as taking the maxi-

mum/minimum of either two sides, or as complicated as requiring extra work to consider elements from

either side of the partition.

Example. Merge sort requires us to merge the two sorted arrays together to form a new sorted array;

this is done with two pointers initially at the head of the arrays and then sweeping left to right.

Example. Counting inversions requires us to count inversions between pairs of elements that are on

both halves of the split (i.e. one element from the pair is on one half and the other element is on the

other half).

Example. Computing the pair of points that are closest in distance requires us to consider pairs of

points that are on both halves of the split.

6

COMP3121/9101: Algorithm Design and Analysis 2024, Term 2

4.2 Analysing the algorithm

4.2.1 Proving correctness

When proving the correctness of divide-and-conquer algorithms, we typically prove it by induction. There-

fore, we follow the induction structure:

The base cases are typically easy to argue because, by the nature of how you have handled the base

cases, the problem is solved.

Assume, now, that the problem has been solved for each of the recursive steps. We now need to

argue that if our algorithm retrieves the correct solution in our recursive stages, then it also retrieves

the correct solution in the current step.

4.2.2 Analysing the time complexity

To analyse the running time of your algorithm, we need to analyse the work taken at each recursive step,

including the time taken to combine all previous solutions. This typically requires setting up a recurrence

and solve the recurrence for the asymptotic behaviour. To this end, we can use the Master Theorem stated

below. See the appendix for the extension of theMaster Theorem that may be applicable in some situations.

Let T (n) = aT (n/b) + f(n), where a ≥ 1 and b > 1. The Master Theorem says that:

if there exist a constant ? > 0 such that f(n) = O (nlogb a??), then T (n) = Θ (nlogb a).

if f(n) = Θ (nlogb a), then T (n) = Θ (nlogb a log n).

if there exist a constant ? > 0 such that f(n) = ? (nlogb a+?) and if af(n/b) ≤ cf(n) for some

constant c < 1 for all sufficiently large n, then T (n) = Θ (f(n)).

If the recurrence does not fit any of these cases, then we need to unroll the recurrence.

7

COMP3121/9101: Algorithm Design and Analysis 2024, Term 2

5 Applications of Divide and Conquer

5.1 Tiling Problems

Let n be a power of two. An equilateral triangle is partitioned into smaller equilateral triangles by

parallel lines dividing each of its sides into n > 1 equal segments. The topmost equilateral triangle

is chopped off. We want to tile the remaining equilateral triangles with trapezoids, each of which is

composed of three equilateral triangles.

Design a divide and conquer algorithm to tile the equilateral triangles with trapzedoids. Justify the

correctness of the algorithm and analyse its time complexity.

Every equilateral triangle must be covered by at least one trapezoid.

No equilateral triangle may be tiled by more than one trapezoid.

Note. A tiling always exists.

5.2 Line Segment Intersections

You are given two lists of n points, one list P = [p1, . . . , pn] lies on the line y = 0 and the other list

Q = [q1, . . . , qn] lies on the line y = 1. We construct n line segments by connecting pi to qi for each

i = 1, . . . , n. You may assume that the numbers in P are distinct and the numbers in Q are also

distinct. Design an O(n log n) algorithm to return the number of intersections between every pair of

distinct line segments.

For example, the following instance

p1 p2 p3p4

q1q2q3 q4

should return 5 since there are five intersections.

8

COMP3121/9101: Algorithm Design and Analysis 2024, Term 2

5.3 Geometric Applications of Divide and Conquer

Alice is planting n1 flowers f1, . . . , fn1 among n2 rectangular gardens g1, . . . , gn2 . Bob’s task is to

determine which flowers belong to which gardens (possibly none). Alice informs Bob that no two

gardens overlap; therefore, if a flower belongs to a garden, then it belongs to exactly one garden.

Moreover, a garden can contain multiple flowers. If a flower does not belong to any garden, then Bob

returns undefined for that flower. Finally, let n = n1 + n2.

Figure 1: A collection of n1 = 5 flowers and n2 = 4 gardens.

We can define the location of a rectangular garden by identifying its bottom-left and top-right corners.

Additionally, flower fi is represented by a point F [i]. Formally, we are given three arrays:

B = [(x1, y1), . . . , (xn2 , yn2)], where B[i] represents the bottom-left point of garden gi.

T = [(x1, y1), . . . , (xn2 , yn2)], where T [i] represents the top-right point of garden gi.

F = [(x1, y1), . . . , (xn1 , yn1)], where F [i] represents the location of flower fi.

For each flower fi, your task is to identify which garden (if any) contains fi. If a flower is not contained

inside any garden, then we return undefined.

(a) We first solve the special case where all of the gardens intersect with a horizontal line. Design

an O(n log n) algorithm to determine which flowers belong to which gardens (if such a garden

exists).

Figure 2: A collection of n1 = 6 flowers and n2 = 4 gardens that intersect with a horizontal line.

Hint. What do you know about two adjacent gardens if they have to intersect with a horizontal

line?

(b) We now remove the assumption that every garden intersects with a horizontal line. Design an

O(n log2 n) algorithm to determine which flowers belong to which gardens (if such a garden

exists).

Hint. If T (n) = 2T (n/2) +O(n log n), then T (n) = O(n log2 n).

Exercise. Reduce the time complexity to O(n log n).

9

COMP3121/9101: Algorithm Design and Analysis 2024, Term 2

Further practice exercises

In addition to your lab exercises, here is a curated list of further practice problems in preparation for your

exam. The problems are (approximately) ordered by difficulty. No solutions will be released for these

exercises; therefore, you may want to post on the forum if you have any queries.

1. Let A be an array of n integers. Further, suppose that A[1] ≥ A[2] and A[n? 1] ≤ A[n]. An element

A[i] is a local minimum if it satisfies the inequalities

A[i] ≤ A[i? 1], A[i] ≥ A[i+ 1].

Design an O(log n) algorithm that returns the index of a local minimum. For example, if A =

[1,3, 4, 3, 6, 8], then one possible answer is A[2] = ?3. Another possible answer is A[4] = 3.

2. You are handed n bottles from a genie, and the genie exclaims that exactly one of these bottles

contain the secret to eternal happiness. In order to play the game, the genie has a few rules:

You pick up a set of bottles and can only ask the genie if any of these bottles contain the secret.

You are not allowed to peek inside any of the bottles; otherwise, you will banished forever!

? You can query any bottle an infinite number of times.

Since the genie knows you are an algorithm enthusiast, they will grant you only O(log n) queries. If

you need to use more thanO(log n) queries, then you will not receive the secret to eternal happiness.

Design an algorithm to win the game and unlock the secret to eternal happiness!

3. Let G = (V,E) be a connected and acyclic graph on n vertices. On this graph, you are guaranteed

that exactly one of these vertices contains a prize; however, you do not know which vertex it is. You

are allowed to query vertices and each query will tell you which edge you must travel on in order to

reach the prize, or “yes” if the current vertex you are querying on contains the prize.

Your task is to determine which vertex contains the prize using at most O(log n) queries.

Note. The time complexity of your algorithm might be slower than log n, but your algorithm can only

use at most O(log n) many queries.

(a) If G is a path (or line graph), design an O(n)-time algorithm that finds the prized vertex using

at most O(log n) many queries.

(b) For the remaining two parts, assume thatG is an arbitrary connected and acyclic graph. Design

an O(n2 log n)-time algorithm that finds the prized vertex using at most O(log n)many queries.

(c) Reduce the time complexity to O(n log n).

Note. Since G is connected and acyclic, |E| ≤ |V |.

4. Let A be an array of n objects. These objects may not necessarily be comparable and so, we cannot

test for inequality. Instead, we can only ask queries of the form: is A[i] = A[j]?. An element x is the

majority element whether x appears more than n/2 times. Design an O(n log n) algorithm to find

the majority element, or report that no such element exists.

Hint. Firstly, if a majority exists, then convince yourself that there is only one majority element. Yes...

there is an O(n) algorithm for this problem.

5. You have just landed at a sporting arena with n students, either from UNSW or USYD. Each student

is either from UNSW or USYD, and not both or neither. From their outward appearance, you cannot

tell which person is from which school and you cannot ask any student what school they are from;

otherwise, you will receive many stares. Instead, you devise a plan.

You pick two arbitrary students and introduce them to one another. Two students from the same

school knows each other and will greet each other with a smile. Two students from opposing

schools will stare blankly at each other.

10

COMP3121/9101: Algorithm Design and Analysis 2024, Term 2

Suppose you know that more than half of the students belong to a particular school. Design an

O(n log n) algorithm to identify all students in the majority school.

Hint. Try to first find a student in the majority school. Maybe something similar to the previous problem

might help. Yes... this means that there is an O(n) algorithm for this problem too.

6. Let I = {I1, . . . , In} be a set of n intervals. Each interval Ii is specified by its two end points: ai and

bi with ai ≤ bi. Two intervals Ii and Ij overlap if there exist a point x such that x = Ii and x = Ij .

In other words, x = [ai, bi] and x = [aj , bj ]. Finally, the length of the overlap is given by the longest

interval that is shared between Ii and Ij . Formally, we can express this length as

L(i, j) = max{0,min{bi, bj} ?max{ai, aj}}.

Given n intervals, design an O(n log n) algorithm that returns the pair of intervals Ii and Ij that

maximises L(i, j). Your input is two arrays A[1..n] and B[1..n] such that A[i] specifies the beginning

of interval Ii and B[i] specifies the end of interval Ii.

7. Let L = {?1, . . . , ?n} be a set of n non-vertical lines, where line ?i is specified by the equation

y = aix + bi. Further, we will assume that no three lines intersect at a point. A line ?i is uppermost

at a point x0 if aix0 + bi > ajx0 + bj for all i ?= j. A line ?i is visible if there exist some x-coordinate

for which ?i is uppermost. In other words, if we look down from the line y =∞, then we can see a

portion of the line.

Design an O(n log n) algorithm that returns all of the visible lines.

Hint. Sort in increasing order of slope. Which two lines are always visible? When we combine two

subproblems, consider each intersection point. It might help to draw out a picture.

11

COMP3121/9101: Algorithm Design and Analysis 2024, Term 2

Appendix: Understanding Recurrences

A recurrence is a succinct description of a system that depends on itself, usually by calling itself multiple

times. For divide and conquer algorithms, we often split the problem instance into multiple smaller in-

stances of the same problem. To quickly analyse the running time of the algorithm, we usually write it as

a recurrence.

Let T (n) denote the running time of the algorithm on a problem of size n. Then, if we divide the problem

instance into a copies of itself, each of size n/b, then we can succinctly write T (n) in terms of T (n/b);

specifically,

T (n) = aT (n/b) + f(n),

where f(n) is the amount of overhead work used to combine all a subproblems. Pictorially, this recurrence

can be viewed exactly as a recursion tree.

Figure 3: Courtesy: Jeff Erickson’s Algorithms.

The total amount of work required of an algorithm with recurrence T (n) = aT (n/b) + f(n) is the sum of

the amount of work at each level; in other words, the amount of work is given by

T (n) = f(n) + af(n/b) + a2f(n/b2) + · · ·+ aLf(n/bL),

where L = logb n. The Master Theorem gives conditions on f(n), and the asymptotic complexity can be

resolved depending on which term dominates.

? If af(n/b) > cf(n) for some constant c > 1, then the series form an ascending geometric series. The

largest term in the series, therefore, is the last term and so, T (n) = Θ(nlogb a). To see why this is the

12

COMP3121/9101: Algorithm Design and Analysis 2024, Term 2

case, note that.

If af(n/b) < cf(n) for some constant c > 1, then the series form a descending geometric series. The

largest term in the series, therefore, is the first term and so, T (n) = Θ(f(n)).

If af(n/b) = f(n), then each term in the series contributes to the overall work required. Thus, in

this case, we have that

T (n) = Θ (f(n)L) = Θ (f(n) log n)

Otherwise, this analysis is not applicable and we need to resort to other methods such as unrolling

the recurrence.

A.1 The Akra-Bazzi Method

The Akra-Bazzi method generalises the above discussion and provides a much more powerful result. In

doing this, we actually recover the Master Theorem in its stated form. To do this, we will firstly consider

a general divide and conquer recurrence:

T (n) =

L∑

i=1

aiT (n/bi) + f(n),

where L is a constant. Further, assume that ai > 0 and bi > 1 are constants for each i. These do not have

to be the same constants throughout; see exercise for an example. Finally, we will assume that f grows

polynomially; that is, we make the assumption that

f(n) = ?(nc), f(n) = O(nd),

with 0 < c ≤ d. Akra and Bazzi proved that the closed form solution to the recurrence is

T (n) = Θ