程序代写 ECE 374 A (Spring 2022) Homework 5 Solutions

Problem 5.1:
CS/ECE 374 A (Spring 2022) Homework 5 Solutions
(a) (20 pts) Suppose that we are given a set H of horizontal line segments and a set V of vertical lines with |H| + |V | = n. (A horizontal line segment has two endpoints and can be specified by two x-coordinates and one y-coordinate; a vertical line is unbounded from above and from below, and can be specified by one x-coordinate.) Describe an O(n log n)-time algorithm to count the total number of intersections between H and V . You may use sorting as a subroutine.
(b) (70 pts) Next, suppose that we are given a set H of horizontal line segments and a set V of vertical downward rays with |H| + |V | = n. (A vertical downward ray is unbounded from below, and can be specified by the x- and y-coordinates of its top endpoint.) Describe an algorithm to count the total number of intersections between H and V . Your algorithm should use divide-and-conquer and have running time O(n log2 n) or better. You may (and should) use part (a) as a subroutine. [Hint: divide using a median horizontal line. . . ]

Copyright By PowCoder代写 加微信 powcoder

(c) (10 pts) Finally, suppose that we are given a set H of horizontal line segments and a set V of vertical line segments with |H| + |V | = n. Describe an algorithm to count the total number of intersections between H and V . Your algorithm should have running time O(n log3 n) or better. You should use part (b) as a subroutine. [Hint: one way is to use divide-and-conquer again, but there is also a slicker way, using (b). . . ]

[Note: You may assume that all x-coordinates and all y-coordinates are distinct.] Solution:
(a) Idea. We sort all the x-coordinates of the endpoints of the horizontal segments and the vertical rays. We consider a vertical “sweep line” moving from left to right, and maintain a depth holding the number of horizontal segments intersecting the current sweep line. We increment/decrement depth whenever the sweep line passes through a left/right endpoint.
Pseudocode. The input is a set H of horizontal segments and V of vertical lines with n = |H| + |V |. We let count be the number of intersections found.
part-a(H, V ):
2. 3. 4. 5. 6. 7. 8. 9.
sort the list X of the x-coordinates of all left and right endpoints of H and the x-coordinates of all lines in V
count = depth = 0
for each x ∈ X in increasing order do
if x is the x-coordinate of a left endpoint in H then depth = depth + 1
else if x is the x-coordinate of a right endpoint in H then depth = depth − 1
else if x is the x-coordinate of a vertical line in V then count = count + depth
return count
x-coordinate and its type (whether it is from a left or right endpoint of a horizontal segment, or from a vertical line); in case of a vertical line, the record would also contain a pointer to the line. This way, the conditions in lines 4, 6, and 8 can indeed be tested in constant time.]
Analysis. |X| ≤ 2n (each horizontal segment has two x-coordinates and each vertical line has one). Line 1 takes O(n log n) time by heapsort, for example. The linear scan in lines 2–10 takes O(n) time. The total time is O(n log n).
[Remark. Alternatively, one could use binary search to compute the number of inter- sections for each horizontal line segment, after sorting all the vertical lines. This would also give O(n log n) total time.]
(b) Idea. We use a divide-and-conquer based on the median y-coordinate.
Pseudocode. The input is a set H of horizontal segments and V of vertical rays with
n = |H| + |V |. We let count be the number of intersections found. intersect-count(H, V ):
1. ifn≤1thensetcountto0andreturn
2. let ym be the median among all y-coordinates from both
the horizontal segments in H and the endpoints of the vertical rays in V
3. let HU be the set of all horizontal segments above y = ym
and HL be the set of all horizontal segments below y = ym 2
in actual implementation, each element of X would be a record containing an

4. let VU be the set of all vertical rays with endpoints above y = ym and VL be the set of all vertical rays with endpoints below y = ym
5. let VU′ be the set of lines obtained by extending the rays in VU
6. returnintersect-count(HU,VU)+intersect-count(HL,VL)+part-a(HL,VU′)
Explanation. The two recursive calls in line 6 handle intersections between HU and VU and intersections between HL and VL. There are no intersections betwen HU and VL, but we still have to consider intersections between HL and VU . The key observation is that below y = ym, the rays in VU are equivalent to lines; thus, the intersections between HL and VU can be found by calling the subroutine in part (a) for HL and VU′ , as done in line 6.
Analysis. Let T (n) be the running time for an input set of size n. Line 2 takes O(n log n) time by sorting the y-coordinates (or O(n) time by a selection algorithm). Lines 3–5 clearly take O(n) time. Line 6 takes 2T(n/2) time (ignoring floors and ceilings). We get the following recurrence:
􏰪 2T(n/2)+O(nlogn) ifn>1 T(n) = O(1) if n ≤ 1.
The recurrence is identical to one from Problem Old.5.2(b). For completeness, we re- describe one way to solve the recurrence, by iteration: for some constant c,
≤ 2[2T(n/4)+c(n/2)log(n/2)]+cnlogn ≤ 4T(n/4)+2cnlogn
≤ 4[2T(n/8)+c(n/4)log(n/4)]+2cnlogn ≤ 8T(n/8)+3cnlogn
≤ 2kT(n/2k)+kcnlogn
≤ nT (1) + cn log2 n by setting k = log n = O(nlog2n).
[Remark. The running time can be improved to O(n log n), for example, by pre-sorting the x- and y-coordinates once before the recursion starts. When the input is pre-sorted, the call to part-a in line 6 actually takes linear time, and given the sorted lists for (H, V ), we can generate the sorted lists for (HU , VU ) and (HL, VL) in lines 9–10 in linear time by a linear scan. So the recurrence becomes T (n) = 2T (n/2)+O(n), which yields O(n log n) total time, even including the initial pre-sorting step.]
(c) The input is a set H of horizontal segments and V of vertical segments with n = |H|+|V |. For each vertical segment v in V , create a downward vertical ray v′ that starts at the upper endpoint of v, and create another downward vertical ray v′′ that starts at the lower endpoint of v. Observe that the number of intersections along v is exactly the number of intersections along v′ minus the number of intersections along v′′.
We call the subroutine from part (b) twice and subtract: the answer is precisely intersect-count(H, {v′ : v ∈ V } − intersect-count(H, {v′′ : v ∈ V }).
2T(n/2)+cnlogn

We thus immediately obtain an O(n log2 n)-time algorithm for part (c) (or O(n log n)- time according to the previous Remark).
Problem 5.2: Consider the following directed graph Gn:
012345 …n
We would like to count the number of the paths that go from vertex 0 to vertex n in Gn. Let
Xn denote this number.
It is not difficult to see that Xn satisfies the recurrence
Xn =Xn−1+Xn−3 (1) for all n ≥ 3 (since we can enter vertex n either from vertex n − 1 or from vertex n − 3). For
thebasecases,X0 =X1 =X2 =1.
From this recurrence, it is straightforward to obtain an algorithm that computes Xn using
O(n) arithmetic operations. But we can do better. . .
(a) (10 pts) Prove that for all m, n ≥ 2,
Xm+n = XmXn + Xm−2Xn−1 + Xm−1Xn−2.
[Hint: in Gm+n, a path from vertex 0 to vertex m + n may either go through vertex m,
or skip over m in two possible ways. . . ]
(b) (10 pts) Use part (a) (and Eq. (1))1 to express X2n, X2n−1, X2n−2 in terms of Xn, Xn−1, Xn−2.
(c) (45 pts) Using part (b), design and analyze an algorithm that computes Xn for a given n, using only O(log n) arithmetic operations.
(d) (35 pts) For large n, the number Xn is exponentially large (how many bits?), and so we can’t assume that arithmetic operations take constant time. Show that your algorithm in part (c) can be implemented in O(nlog2 3) time, if multiplications are done using Karatsuba’s algorithm. (In contrast, the naive approach using Eq. (1) would require O(n2) time when bit complexity is taken into account.)
[Note: If you are unable to do (a), you can still do (b)–(d), assuming the formula from (a).]
(a) Any path from 0 to m + n in Gm+n must satisfy exactly one of the following conditions:
􏰁 Type I: The path passes through m. The number of paths from 0 to m is Xm, and the number of paths from m to m+n is Xn. Thus, the number of paths of this type is XmXn.
1It may be helpful to know, from Eq. (1), that Xn−3 = Xn − Xn−1, for example. 4

􏰁 Type II: The path uses the edge from m−2 to m+1. The number of paths from 0 to m−2 is Xm−2, and the number of paths from m+1 to m+n is Xn−1. Thus, the number of paths of this type is Xm−2Xn−1.
􏰁 Type III: The path uses the edge from m−1 to m+2. The number of paths from 0 to m−1 is Xm−1, and the number of paths from m+2 to m+n is Xn−2. Thus, the number of paths of this type is Xm−1Xn−2.
It follows that the total number of paths from 0 to m + n is given by Xm+n = XmXn + Xm−2Xn−1 + Xm−1Xn−2.
Xn2 + 2Xn−1Xn−2
X2n = X2n−1 =
by (a) with m = n
by (a) with m = n − 1
since Xn−3 = Xn − Xn−1
by (a) with m,n replaced by n−1
Xn−1Xn + Xn−3Xn−1 + Xn2−2
= Xn−1Xn + (Xn − Xn−1)Xn−1 + Xn2−2
= 2XnXn−1 − Xn2−1 + Xn2−2
Xn2−1 + 2Xn−2Xn−3
(c) Given n ≥ 2, the following algorithm returns the triple (Xn,Xn−1,Xn−2) (to compute
= Xn2−1 + 2(Xn − Xn−1)Xn−2
since Xn−3 = Xn − Xn−1 Xn, we just call compute-triple(n) and extract the first argument of the output):
compute-triple(n):
1. if n = 2 then return (1,1,1)
2. if n = 3 then return (2,1,1)
2. (a, b, c) = compute-triple(⌊n/2⌋)
3. if n is even then
4. return (a2 +2bc, 2ab−b2 +c2, b2 +2(a−b)c) 5. else return (a2 +b2 +2ac, a2 +2bc, 2ab−b2 +c2)
Explanation. Line 2 computes a = X⌊n/2⌋, b = X⌊n/2⌋−1, and c = X⌊n/2⌋−2. Correctness of the case of even n (line 4) follows directly from part (b) (with n replaced by n/2). For the case of odd n (line 5), part (b) (with n replaced by ⌊n/2⌋) gives Xn−1 = a2 + 2bc, Xn−2 = 2ab−b2 +c2, and Xn−3 = b2 +2(a−b)c. By Equation 1, we have Xn = Xn−1 +Xn−3 =(a2 +2bc)+(b2 +2(a−b)c)=a2 +b2 +2ac.
Analysis. Let T(n) be the number of arithmetic operations performed by compute- triple(n). Line 4 or 5 requires O(1) arithmetic operations. Thus, we get the following
recurrence:
􏰪T(⌊n/2⌋)+O(1) ifn>2 T(n) = O(1) if n ≤ 2.
It is well known that this recurrence solves to O(logn) (it is the same recurrence as binary search).
(d) First note that Xn = Xn−1 + Xn−3 ≤ 2Xn−1. It follows that Xn ≤ 2n, and so Xn is an O(n)-bit integer.
Redefine T(n) to be the running time of compute-triple(n). Now, line 4 or 5 requires O(1) additions/subtractions and multiplications of numbers with O(n/2) = O(n) bits.

Each such addition/subtraction takes O(n) time, and by Karatsuba’s algorithm, each such multiplication takes O(nlog2 3) time. Thus, we get the following recurrence:
􏰪T(⌊n/2⌋)+O(nlog23) ifn>2 T(n) = O(1) if n ≤ 2.
One way to solve this recurrence is to apply the Master theorem (e.g., in Jeff’s notes, Section II.3). Since (n/2)log2 3 = κnlog2 3 with κ = 1/3 < 1, we have T(n) = O(n1.59). [Alternatively, we can directly expand the recurrence and obtain a geometric series: T (n) ≤ O(nlog2 3 + (n/2)log2 3 + (n/4)log2 3 + · · · ) = O(nlog2 3 􏰆∞i=0(1/2i)log2 3) = O(nlog2 3 􏰆∞i=0(1/3)i) = O(nlog2 3).] Alternate Solution to (a) by induction: (written by ) Letm∈Nwithm≥2. Inductiononn. Base case: n=2,n=3,n=4. Then, we have Xm+n = Xm+2. By the given recurrence, Xm+2 = Xm+1 + Xm−1 Xm+2 = Xm + Xm−1 + Xm−2 BecauseX0 =X1 =X2 =1, Xm+2 =Xm ∗X2 +Xm−1 ∗X0 +Xm−2 ∗X1 The same logic can be applied for cases 3, 4... Inductive Hypothesis: Let k ∈ N. with k ≥ 5 and suppose Xm+n =Xm∗Xn+Xm−1∗Xn−2+Xm−2∗Xn−1 istrueforall2≤n≤k. Inductive Step: By the given recurrence, Xm+(k+1) =Xm ∗Xk +Xm ∗Xk−2 By the Inductive Hypothesis, Xm+(k+1) = (Xm∗Xk+Xm−1∗Xk−2+Xm−2∗Xk−1)+(Xm∗Xk−2+Xm−1∗Xk−4+Xm−2∗Xk−3) Rearranging, Xm+(k+1) = Xm ∗ (Xk + Xk−2) + Xm−1 ∗ (Xk−2 + Xk−4) + Xm−2 ∗ (Xk−1 + Xk−3) By the given recurrence, Xm+(k+1) = Xm ∗ Xk+1 + Xm−1 ∗ Xk−1 + Xm−2Xk ∴ By the principle of strong induction, Xm+n = Xm ∗ Xn + Xm−1 ∗ Xn−2 + Xm−2 ∗ Xn−1 holds for all n ∈ N with n ≥ 2. 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com