Suppose you're consulting for a company that manufactures pc equipment

Foundations of Algorithms

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.

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”

1

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):

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

) .

(c) [10 points] Show that x = ( 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.

2

Applied Sciences

Architecture and Design

Biology

Business & Finance

Chemistry

Computer Science

Geography

Geology

Education

Engineering

English

Environmental science

Spanish

Government

History

Human Resource Management

Information Systems

Law

Literature

Mathematics

Nursing

Physics

Political Science

Psychology

Reading

Science

Social Science

Home

Blog

Archive

Contact

google+twitterfacebook

Copyright © 2019 HomeworkMarket.com