Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Recipe portions You want to make as many servings as you can of your secret recipe to bring to the potluck, but at most M servings fit in your insulated food container, and you have a budget of at most B that you can spend on it. The recipe has n ingredients. Ingredient i sold in packages with enough for b_i servings for price p_i. You can only make servings in integer quantities (e.g., cupcakes, rather than pudding.) Give an algorithm that finds the most servings up to M that you can bring within your budget, that runs in time O((nlogM)). (Page limit: 2 pages total. Algorithm description, 15 points. Short argument for correctness, 8 points. Time analysis and efficiency, 10 points.)

Subgraph with specified degrees You are given a bipartite graph G = (L,R,E) , and for each vertex in v ∈ L ∪ R a non-negative integer D(v). You need to decide whether there is an edge induced subgraph E⁰ ⊂ E so that, in E⁰, every vertex v has degree exactly D(v). Give an efficient algorithm to do this. (5 points clear algorithm, 18 points correctness proof, 10 points time analysis and efficiency. Full points for efficiency is O((|V |+|E|)|E|). 3 page limit. )

Betting game Flora and Susan are playing a game. They alternate turns, with Flora having the first turn. In turn I, the player can put any integer from 1 to I coins in the pot. (So Flora has to put 1 coin in, then Susan could put either 1 or 2 coins in, making the total either 2 or 3. Then Flora can put in either 1, 2 or 3 coins, making the pot have some total between 3 and 6.) A player wins if the number of coins in the pot at the end of their turn is exactly n. (Note that there will never be a number of coins greater than n in the pot, because if a number greater than n is reachable,

so is n, and the player will choose to win.) Give a dynamic programming algorithm that, given n , decides which player has a winning strategy for this game. Your algorithm should take time at most O(n³).

Your answer should be structured as follows:

1. Description of sub-problems (6 points)

2. Base Case(s) (2 points)

3. Recursion (with justification) (A complete proof by induction is NOTrequired. However, you should explain why the recursion makes sense and how it covers all possibilities) (8 points)

4. Order in which sub-problems are solved (3 points)

5. Form of output (how do we get the final answer?) (2 points)

6. Pseudocode (5 points)

7. Runtime analysis and efficiency (5 points)

8. A small example explained using an array or matrix holding answersto sub-problems (2 points)

No section should take more than a page, and most should be quite short.