Algorithms · Correctness proofs and asymptotic complexity
There are n jobs in fixed order with positive integer sizes s₁,…,sₙ, and d ≥ 1…
Problem
Algorithms practice problemThere are jobs in fixed order with positive integer sizes , and identical days. Each nonempty day receives one contiguous job block; jobs cannot split and empty days are allowed. Find the minimum possible maximum daily load in , where . Prove the feasibility test and optimization correct, and state the result for .
Hint
Hint** First test a proposed maximum load .
Check your work
Work the problem yourself first. Then open it in Training to check your answer and read the full worked solution.
Create a free account to check your answer and see the solution. Create a free account.
More Algorithms practice problems
- Let all logarithms have base 2, and let all functions have domain the positive integersCorrectness proofs and asymptotic complexity
- Two disjoint color classes contain r ≥ 1 red and b ≥ 1 blue planar pointsDivide-and-conquer algorithms
- Using only comparisons, return both minimum and maximum among n ≥ 1 distinct keysDivide-and-conquer algorithms
- Consider the invalid coding rule that repeatedly combines the two partial trees of…Greedy algorithms and exchange proofs
- The n vertices of a cycle are numbered 1,…,n, and vertex i has an integer weightGreedy algorithms and exchange proofs
- Given an undirected graph with up to five million vertices, produce exactly the…Dynamic programming and state design
- Prim’s algorithm starts at an arbitrary root and repeatedly adds a minimum-weight edge…Dynamic programming and state design
- Let T[0..n-1] be a text and P[0..m-1] a pattern over the same alphabet, where 1 ≤ m ≤ nGraph optimization and traversal algorithms
- Consider SET COVER parameterized by the universe size p=|U|, while the number m of…Reductions, NP-completeness, and approximation