# LateX代写 | Spring 2020, CMPSC 465 Final Exam

这个作业是用LateX解决排序问题

Spring 2020, CMPSC 465 Final Exam

The exam is due 9:50 am on May 7th. Submit the file on Gradescope. Late submissions are not

permitted.

Collaboration is not permitted on the exam. You should not discuss these problems with anybody

else, either in person or online. Also, looking up solutions to the problems online is forbidden. Your

only reference sources must be the required or recommended text books for this class.

Please aim to be clear and concise. The graders and the teaching staff should be able to easily

follow your work.

Your submission must be a single PDF file with 3 pages. Use letter-sized pages (8.5 inches by

11 inches) with 1-inch margins on all sides. Solve each problem on a separate page.

I strongly recommend using LaTeX (see Overleaf.com) to prepare the solutions. Alternately, you

can use R Markdown or Microsoft Word and convert the document to PDF. Legible PDF scans

of handwritten submissions are also okay if you follow the formatting guidelines above (3 pages,

1 problem on each page, letter-sized pages with 1-inch margins). If you violate the formatting

guidelines (e.g., plain text submissions, number of PDF pages not equal to 3, solutions not in

order, blurry scans, tex/docx files instead of PDF), the submission will not be graded.

This exam is for 10% of your class grade and there are three problems. The exam is for 20 points,

with Problems 2 and 3 worth 7 points each, and problem 1 worth 6 points. Answer all problems.

1

You are given two sorted lists of size m and n. Give a O(log m+log n) time algorithm for computing

the k

th largest element in the union of the two lists.

2

Consider the following 2SAT instance:

(x1 ∨ x2) ∧ (x2 ∨ x¯3) ∧ (¯x2 ∨ x4) ∧ (¯x1 ∨ x¯4)

Show the steps of the linear-time strongly connected components-based algorithm given in the

textbook to solve this problem.

Using a small example, briefly explain why this algorithm is not applicable for a 3SAT instance.

3

You are given an ordered list of m key-value pairs of the form hki

, vii, where ki and vi are both

positive integers. The list is ordered by the key k in increasing order, i.e., ki < ki+1, and all keys are distinct. Your goal is to select key-value pairs such that the sum of values is maximized, under the constraint that any two pairs in the chosen set have their keys differing by at least x, where x is some positive integer given as input. Give an efficient algorithm to maximize the value subject to the constraint. As an example, consider the four key-value pairs h1, 3i,h2, 6i,h4, 5i, and h11, 1i, and x = 5. Then, selecting h2, 6i and h11, 1i results in the maximum value of 7. On the other hand, if x were 2, the maximum value would be 12 (with three pairs selected). 1