CS/ECE 374 A (Spring 2022) Homework 5 (due March 3 Thursday at 10am)
Instructions: As in previous homeworks.
In algorithm design questions, usually an algorithm is best described by pseudocode (not actual code!), along with explanation or justification of correctness (especially if it is not obvious), and analysis of the running time. See https://courses.engr.illinois.edu/cs374/sp2022/A/hw_ policies.html#content.
Problem 5.1:
Copyright By PowCoder代写 加微信 powcoder
(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. . . ]
(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.] 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).]
1It may be helpful to know, from Eq. (1), that Xn−3 = Xn − Xn−1, for example. 2
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com