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

CS 430 – Spring 2023

INTRODUCTION TO ALGORITHMS

HOMEWORK #4

DUE 23:59 April 6 (Thursday)

● Assignment Instruction

• Teamwork is NOT allowed.

• Submit your answers in PDF version to the Blackboard.

• No late submission accepted.

• All solutions should be explained.

!! Any unrecognized handwriting causing ambiguity will result in a zero to your solutions!!

1.   (5 pts) Sally is hosting an Internet auction to sell at most n widgets and maximize her      income from the sale. She receives m bids, each of the form "I want exactly ki widgets for di dollars," for i = 1,2,..., m. (you can assume each ki and each di are integers) Characterize her optimization problem similar to a problem we covered in class. Explain the                 algorithm to solve her problem and prove it is optimal. How does the solution change if each bidder is willing to accept partial lots (an integer amount less than ki widgets)?

2.   We consider the problem of placing towers along a straight road, so that every building  on the road receives cellular service. Assume that a building receives cellular service if it is within one mile of a tower.

2a. (5pts)Devise an algorithm that uses the minimum number of towers possible to          provide cell service to d buildings located at positions x1, x2, . . . , xd from the start of the road.

2b.(5pts) Prove that the algorithm you devised produces an optimal solution, that is, that it uses the fewest towers possible to provide cellular service to all buildings.

3.    (5pts) An array cost[] consists of integers. costi  is the cost to climb from step i. Once costi is paid, you can choose 1 or  2 steps to take forward. Initially,  you can start from either    step 0 or step 1. Please design an algorithm to return the minimal cost to arrive at the top of the stairs, which is step n.

For example:

cost[]=(1,100,1,1,1,90,1,1,80,1)

The minimal cost is 6.

Solution:

Start from step 0;

Pay 1, and take 2 steps, reaches step2;

Pay 1, and take 2 steps, reaches step4;

Pay 1, and take 2 steps, reaches step6;

Pay 1, and take 1 step, reaches step7;

Pay 1, and take 2 steps, reaches step9;

Pay 1, and take 1 step, reaches the top.

Total cost: 6