CSCI-GA.1170-001/002 Fundamental Algorithms
代写Algorithm – 这道题目是Algorithm进行代写任务, 是比较有代表性的Algorithm等代写方向
Problem Set 5
Problem 5-1 (Roller coaster) 7 points
We will call an arrayB[1… n]a roller coasterifB[1]< B[2],B[2]> B[3],B[3]< B[4] and so on. More formally:B[2i]> B[2i+ 1] andB[2i1]< B[2i] for alli. Give a linear Algorithm that any given arrayAwithndistinct elements transforms into a roller coaster arrayB. Namely,Bmust contain exactly the samendistinct elements asA, but must also be a roller coaster. Briefly argue correctness and the run time of your algorithm. (Hint: A median may be useful here.)
Problem 5-2 (Too Fast and … Furious) 8 points
You receive a sales call from a new start-up calledMYPD(which stands for Manage Your Pri- orities… Differently). The MYPD agent tells you that they just developed a ground-breaking comparison-basedpriority queue. This queue implementsInsertin time log 2 (
n) andExtractmax in time
log 2 n. Explain to the agent that the company can soon be sued by its competitors be- cause either (1) the queue is not comparison-based; or (2) the queue implementation is not correct; or (3) the running time they claim cannot be so good. To put differently, no such comparison-based priority queue can exist. (Hint: Be very precise with the constantcs.t. log 2 (n!)cnlogn.)
Problem 5-3 (Lower Bound for Min-Element) 11 points
Recall that there exists a trivial algorithm for searching for a minimal element of an array of size nthat needs exactly (n1) comparisons. The purpose of this problem is to prove that this is optimal solution. You can assume that elements of the input array are distinct. As usual, you can represent any comparison-based algorithm for Min-Element problem as a binary decision tree, whose internal nodes are labeled by (i:j) (meaning compareA[i] andA[j]), and a left child is chosen if and only iffA[i]< A[j] (recall, we assume distinct elements). And the leaves are labeled by the index imeaning that the smallest element in the arrange isA[i].
(a) (2 points warm-up) Show that the naive counting leaves application of decisional tree
method (like the one used for sorting lower bound) will only give a very suboptimal lower
bound (logn) for the Min-Element problem.
(b) (3 points) Here we will try to enrich the decisional tree by adding some additional infoS(v)
to every vertexv. Precisely,S(v) is the set of all indicesiwhich are consistent with all the
comparisons made from theroottov(excludingvitself), where consistent means that there
PS 5, Page 1
exists an arrayAwhose minimum isA[i] and the nodevis reached on inputi. For example,
ifvis any (reachable) leaf labeled byi, thenS(v) ={i}(as otherwise the algorithm would
not be correct). Assuming the root noderootis labeled (i:j), describeS(root),S(root.left)
andS(root.right).
(Hint: What element is impossible to be minimal if you know thatA[i]< A[j]?)
(c) (3 points) Generalize part (b): show that for every vertexvwe have:S(v.left) =S(v)\{.. .}
andS(v.right) =S(v)\{.. .}(you need to fill dots on your own).
(d) (3 points) Use (c) to prove that in any valid decision tree for Min-Element,anyleaf (which
is stronger thansomeleaf) must have depth at least (n1). (Hint: Think about|S(v)|as
vgoes from root to this leaf.)
Problem 5-4 (Choosing the Right Tool) 9 points
For each example choose one of the following sorting algorithms and carefully justify your choice: HeapSort,RadixSort,CountingSort. Give the expected runtime for your choice as precisely as possible. If you choose Radix Sort then give a concrete choice for the basis (i.e. the value of r in the book) and justify it. (Hint: We assume that the array itself is stored in memory, so before choosing the fastest algorithm, make sure you have the space to run it!)
(a) (3 points) Sort the length 2^16 arrayAof 128-bit integers on a device with 100MB of RAM.
(b) (3 points) Sort the length 2^24 arrayAof 256-bit integers on a device with 600MB of RAM.
(c) (3 points) Sort the length 2^16 arrayAof 16-bit integers on a device with 1GB of RAM.
Problem 5-5 (Finding the Major Elements) 6 (+9) points
Let us say that a numberxisc-majorfor ann-element arrayA, if more thann/celements ofA are equal tox.
(a) (6 points) GiveO(n)-time algorithm to find all 2-major elements ofA. How many could there
be? Briefly argue correctness of your algorithm. (Hint: You may make calls to theSelect
algorithm discussed in class and textbook.)
(b) (9 points) [Extra Credit] GiveO(cn)-time algorithm to find allc-major elements ofA. How
many could there be? Briefly argue correctness of your algorithm. (Hint: You may make
calls to theSelectalgorithm discussed in class and textbook.)
PS 5, Page 2