Problem 1: Knapsack Variant (Pseudocode)

Consider the following version of Knapsack. Given are two weight limits W1 and W2, where W1 ≤ W2. Given are also n items (w1, c1),(w2, c2), . . . ,(wn, cn), where wi is the weight and ci the cost of the i-th item. We want to find a subset of these items of the highest cost, where the subset weights at least W1 and at most W2. Give an O(nW2) algorithm for this problem. (Re Block Crusher (Kattis) call that the cost (respectively weight) of a subset is the sum of the costs (respectively weights) of the items in the subset.)

Problem 2: Minimum Spanning Tree with Repeated Costs (Proof)

Consider the Minimum Cost Spanning Tree problem on an undirected graph G = (V, E) with a cost ce ≥ 0 on each edge, where the costs may not all be different. If the costs are not all distinct, there can in general be many distinct minimum-cost solutions. Suppose we are given a spanning tree T ⊆ E with the guarantee that, for every e ∈ T, e belongs to some minimum-cost spanning tree in G. Can we conclude that T itself must be a minimum-cost spanning tree in G? Give a proof or counterexample with explanation.

Problem 3: Block Crusher (Kattis)

Solve the “Block Crusher”, which you can find at this web address: https://open.kattis. com/problems/blockcrusher This is a coding problem; be sure to follow the relevant instructions for testing and submitting.

Problem 4: Continuous Median (Kattis)

Solve the “Continuous Median” problem, which you can find at this web address: https: //open.kattis.com/problems/continuousmedian This is a coding problem; be sure to follow the relevant instructions for testing and submitting. An O(n 2 ) algorithm will not be fast enough to pass all the tests, and will receive at most 3 points out of 10. You need to get the running time down to o(n 2 ), and ideally, O(n log n).

Hint 1: Suppose “median” in the problem statement were replaced by “min” (or “max”). How would you solve that problem? Suppose we added the additional condition that, after even-numbered inputs, you must return the min value, and thereafter treat it as having been deleted from the data set. How would you solve it now?

Hint 2: Notice that the median element is (ignoring rounding for now) the maximum element of the bottom half of the input, and the minimum element of the top half of the input. How can you make use of that fact?

Hint 3: Choosing the right data structure is essential.

The price is based on these factors:

Academic level

Number of pages

Urgency

Basic features

- Free title page and bibliography
- Unlimited revisions
- Plagiarism-free guarantee
- Money-back guarantee
- 24/7 support

On-demand options

- Writer’s samples
- Part-by-part delivery
- Overnight delivery
- Copies of used sources
- Expert Proofreading

Paper format

- 275 words per page
- 12 pt Arial/Times New Roman
- Double line spacing
- Any citation style (APA, MLA, Chicago/Turabian, Harvard)

Delivering a high-quality product at a reasonable price is not enough anymore.

That’s why we have developed 5 beneficial guarantees that will make your experience with our service enjoyable, easy, and safe.

You have to be 100% sure of the quality of your product to give a money-back guarantee. This describes us perfectly. Make sure that this guarantee is totally transparent.

Read moreEach paper is composed from scratch, according to your instructions. It is then checked by our plagiarism-detection software. There is no gap where plagiarism could squeeze in.

Read moreThanks to our free revisions, there is no way for you to be unsatisfied. We will work on your paper until you are completely happy with the result.

Read moreYour email is safe, as we store it according to international data protection rules. Your bank details are secure, as we use only reliable payment systems.

Read moreBy sending us your money, you buy the service we provide. Check out our terms and conditions if you prefer business talks to be laid out in official language.

Read more