CS3000 HW
report代做 | 代做Data structure | 代写Algorithm | assignment – 本题是一个利用Algorithm进行练习的代做, 对Algorithm的流程进行训练解析, 是比较有代表性的report/Data structure/Algorithm等代写方向, 这个项目是assignment代写的代写题目
1.) Recall from our discussion of a min-heap that binary trees can be implemented with arrays. Suppose we have a “SpecialHeap” Data structure implemented in this way, in memory that has already been zeroed out. A GROW() operation adds a new complete level to the tree in constant time (containing 2L nodes), by just changing a “node count” variable that specifies where there the real values in memory end. A CHANGE(L, v) operation changes all values at a particular level L to value v, and takes time proportional to the number of nodes at that level. A TEARDOWN() operation sums all values and destroys the tree in time proportional to its number of levels , since the values in a level are all identical and therefore it only needs to look at one value in a level to calculate its sum in constant time.
a.) Find the cost of N operations if we assume the last is a TEARDOWN and the rest are GROW operations, and then use aggregate analysis to find the amortized costs of each. (Don’t assume the process can be sped up by the fact that all the values in the tree are zero – use the times given in the problem statement.) b.) Use the potential method to arrive at the same amortized costs as part (a). Clearly state what your potential function is, and what the terms in your calculation of the amortized cost mean. c.) Now apply the same potential method that you used in (b) to CHANGE. Is this a reasonable amortized cost, or would using the accounting method be likely to reveal a better cost?
2.) Show the results of these operations on an empty tree of the given kind. You only need to show the results after the steps in bold (and will only be graded on these). (a) Normal binary search tree: Insert 5, Insert 4, Insert 3, Insert 2, Insert 0, Insert 1. (b) Red-black tree: Insert 5, Insert 4, Insert 3 , Insert 2. (c) B-Tree, t =2: Insert 5, Insert 4, Insert 3, Insert 2 , Insert 0, Insert 1.
3.) 2-MACHINE-JOB-SCHEDULING is the following problem: Given N jobs with different natural number times t 1 to tN to complete them, is there a way to allocate the jobs to two machines so that both machines finish by deadline D? (For example, for times {1,2,3,4} and deadline 5, the answer is yes because machine 1 could get 3+2=5 and machine 2 could get 4+1=5. Also, throughout this problem, repetition of values in the input is acceptable, even when we speak of sets and subsets; {1,1,1,1} with deadline 2 could be an input with an answer of “yes”.) a.) Prove that 2-MACHINE-JOB-SCHEDULING is in NP by showing that a certificate (“proof of yes”) could be checked in polynomial time. (Describe what the certificate consists of, then explain why checking it takes time polynomial in the size of the input.) b.) Prove that this problem is NP-Hard by showing how, if we could solve this problem in polynomial time, we could solve the NP-complete problem SUBSET-SUM in polynomial time. SUBSET-SUM is the variant of KNAPSACK where we must decide whether a set of natural numbers {s 1 , s2, …, sN} contains a subset that sums to a target number T. (Hint: When constructing your 2-machine problem instance, there are 3 cases: T is exactly half the sum of all numbers, T is more than half the sum, and T is less than half the sum. Try showing how each of these cases could work (they are listed in order of roughly increasing difficulty). You will need to introduce a new job in the second and third cases that allows you to balance everything
- state how big it is and how we know where to look for the SUBSET-SUM solution.) c.) If we combine the facts from parts (a) and (b), what have we proven about 2-MACHINE-JOB- SCHEDULING?
d.) Suppose we now introduce a new problem, PARTITION, and show how a polynomial solution to it could be used to solve 2-MACHINE-JOB-SCHEDULING in polynomial time. What does this prove about PARTITION?
4.) These questions review key concepts from earlier in the course. (This problem is worth about a third of the overall assignment.)
(a) Write pseudocode for a divide-and-conquer approach to checking whether a tree is a valid binomial heap tree (as covered in this week’s lecture – not just a min heap). A heap node contains a value field and an array of children C. You can assume that if the children aren’t in order of increasing size, the heap is invalid. It’s a min-heap, so be sure it obeys the heap property. Be sure to pass in no additional arguments , maintain no global variables , and write no helper functions in order to have as pure a divide-and-conquer solution as possible. You may, as usual, pass up additional information.
b.) One greedy (and suboptimal) approach to the NP-hard problem of finding the maximal VERTEX-COVER would be to greedily add whatever vertices touch the most uncovered edges to the cover. Write pseudocode for this that runs in amortized O(|E| + |V| log |V|) time. Feel free to use hash tables (or, simply, sets that can be updated and checked in constant time).
c.) Consider an alternate version of the Interval Scheduling problem in which the goal is not to book the most requests, but to find a schedule with no slack time that uses the fewest requests. (The requests still consist of specific start and end times.) Write pseudocode for a dynamic programming Algorithm that does this. A schedule with no slack starts at 00:00 and ends at 23:59, and has each finish time of the last request equal to the start time of the next. You can assume there a finite number of request times, since they are all clock times of the form XX:XX. Return the set of optimal requests.
d.) In a class with undergraduate TAs, there are a fair number of conflicts of interest; each TA has a long list of these that covers about half the class. Still, you suspect that a fair allocation of grading should be possible despite this. Suggest an approach that will allocate N assignments to T TAs, and moreover, that will find an allocation where no TA gets more than 1 assignment over the TA average, nor less than 1 assignment below the TA average, assuming that such a solution exists. The approach should run in O(N^2 T) time. Be specific about any necessary graph constructions.
5.) (This programming part is worth less than usual – more like a “normal” problem. There is no HackerRank challenge for it, but attach your code to your Blackboard submission.) In this programming experiment, we’re going to experiment with a simulation of an ArrayList, or growable array.
Write a program that runs the following experiment 25 times: *Create a new ArrayList with the default capacity of ten items. *Insert 2i integers into your ArrayList, where i is the number of the experiment (zero- indexing.) *For each run, report two times: the average time to insert over all insertions for the run, and the slowest time for any insertion during that run. (For the first average, you can include the time to use the for loop, but don’t include the time to create the array.)
Include your results in your PDF – for example:
1: avg: 59597 ns; maxTime: 26579 ns 2: avg: 5628 ns; maxTime: 6701 ns 4: avg: 1958 ns; maxTime: 3611 ns [etc up to 2^24]
Then give a brief analysis of whether the results match our expectations for the ArrayList.