Assignment Help Example on Foundations of Algorithms Homework 6

(Assignment Help Example on Foundations of Algorithms Homework 6) Homework #6

All members of the collaboration group are expected to participate fully in solving collaborative problems, and peers will assess performance at the end of the assignment. Note, however, that each student is required to write up their solutions individually. Common solution descriptions from a collaboration group will not be accepted. Furthermore, to receive credit for a collaborative problem, each student in the collaboration group must actively and substantively contribute to the collaboration. (Assignment Help Example on Foundations of Algorithms Homework 6)

Self-Study Problems All of the following problems come from the textbook and have solutions posted on the web at

http://mitpress.mit.edu/algorithms.

You are permitted to use this site to examine solutions for these problems as a means of self-checking your solutions. These problems will not be graded. Only problems from Chapter 15 are included since the authors have not provided sample problems for chapter 29.

Problems: 15.2-5, 15.3-1, 15.4-4, 15-4, 16.1-4, 16.2-2, 16.2-7,

Problems for Grading 1. [20 points] Suppose you are consulting for a company that manufactures PC equipment and ships it

to distributors all over the country. For each of the next n weeks, they have a projected supply si of equipment (measured in pounds) that has to be shipped by an air freight carrier. Each week’s supply can be carried by one of two air freight companies, A or B.

• Company A charges a fixed rate r per pound (so it costs r × si to ship a week’s supply si). • Company B makes contracts for a fixed amount c per week, independent of the weight. However,

contracts with company B must be made in blocks of four consecutive weeks at a time.

A schedule for the PC company is a choice of air freight company (A or B) for each of the n weeks with the restriction that company B, whenever it is chosen, must be chosen for blocks of four contiguous weeks in time. The cost of the schedule is the total amount paid to company A and B, according to the description above.

Give a polynomial-time algorithm that takes a sequence of supply values s1, s2, . . . , sn and returns a schedule of minimum cost. For example, suppose r = 1, c = 10, and the sequence of values is

11, 9, 9, 12, 12, 12, 12, 9, 9, 11.

Then the optimal schedule would be to choose company A for the first three weeks, company B for the next block of four contiguous weeks, and then company A for the final three weeks.

2. [20 points] CLRS 29.4-3: Write down the dual of the maximum-flow linear program, as given in lines (29.47)–(29.50) on page 862 of the textbook. Explain how to interpret this formulation as a minimum- cut problem.

3. [20 points] Collaborative Problem: As some of you know well, and others of you may be interested to learn, a number of languages (including Chinese and Japanese) are written without spaces between the words. Consequently, software that works with text written in these languages must address the word segmentation problem—inferring likely boundaries between consecutive words in the text. If English were written without spaces, the analogous problem would consist of taking a string like “meetateight” and deciding that the best segmentation is “meet at eight” (and not “me et at eight” or “meet ate ight” (Assignment Help Example on Foundations of Algorithms Homework 6)

or any of a huge number of even less plausible alternatives). How could we automate this process?

A simple approach that is at least reasonably effective is to find a segmentation that simply max- imizes the cumulative “quality” of its individual constituent words. Thus, suppose you are given a black box that, for any string of letters x = x1x2 · · ·xk, will return a number quality(x). This number can be either positive or negative; larger numbers correspond to more plausible English words. (So quality(“me”) would be positive while quality(“ight”) would be negative.)

Given a long string of letters y = y1y2 · · · yn, a segmentation of y is a partition of its letters into contiguous blocks of letters, each block corresponding to a word in the segmentation. The total quality of a segmentation is determined by adding up the qualities of each of its blocks. (So we would get the right answer above provided that quality(“meet”) + quality(“at”) + quality(“eight”) was greater than the total quality of any other segmentation of the string.) Give an efficient algorithm that takes a string y and computes a segmentation of maximum total quality. You can treat a single call to the black box computing quality(x) as a single computational step. Prove the correctness of your algorithm and analyze its time complexity.

4. Collaborative Problem. In the course content, we explained how we can solve two-player zero-sum games using linear programming. One of the games we described is called “Rock-Paper-Scissors.” In this problem, we are going to examine this game more closely. Suppose we have the following “loss” matrix for Player 1 (i.e., we are showing how much Player 1 loses rather than gains, so reverse the sign): (Assignment Help Example on Foundations of Algorithms Homework 6)

A =

 0 1 −1−1 0 1 1 −1 0

 . (a) [10 points] What is the expected loss for Player 1 when Player 1 plays a mixed strategy x =

(x1, x2, x3) and Player 2 plays a mixed strategy y = (y1, y2, y3)?

(b) [10 points] Show that Player 1 can achieve a negative expected loss (i.e., an expected gain) if Player 2 plays any strategy other than y = (y1, y2, y3) =

( 1 3 ,

1 3 ,

1 3

) .

1 3 ,

1 3

) and y =

( 1 3 ,

1 3 ,

1 3

) form a Nash equilibrium.

(d) [10 points] Let x = ( 1 3 ,

1 3 ,

1 3

) as in part (c). Is it possible for (x,y) to be a Nash equilibrium for

some mixed strategy y′ ̸= ( 1 3 ,

1 3 ,

1 3

) ? Explain. (Assignment Help Example on Foundations of Algorithms Homework 6)

References

https://www.youtube.com/watch?v=05GSr4LBsOY

Assignment Help Example on Foundations of Algorithms Homework 6