算法导论课后题和解答_算法导论课后题资源-CSDN文库

共21个文件

pdf：21个

算法导论

需积分: 15 8 浏览量 2009-01-11 15:31:42 上传评论收藏 1.39MB RAR 举报

资源推荐

资源详情

资源评论

收起资源包目录

[麻省理工学院-算法导论].Introduction.to.Algorithms.-.Homework.rar （21个子文件）

ps1sol.pdf 115KB

ps10sol.pdf 44KB

ps9sol.pdf 62KB

ps3.pdf 72KB

samples.pdf 139KB

ps5.pdf 165KB

ps8.pdf 193KB

ps3sol.pdf 110KB

ps2.pdf 51KB

ps7sol.pdf 334KB

ps4.pdf 147KB

ps8sol.pdf 426KB

ps6.pdf 153KB

ps6sol.pdf 197KB

ps10.pdf 33KB

ps9.pdf 37KB

ps5sol.pdf 225KB

ps4sol.pdf 221KB

ps2sol.pdf 82KB

ps7.pdf 47KB

ps1.pdf 207KB

Introduction to Algorithms Day 29

Massachusetts Institute of Technology 6.046J/18.410J

Singapore-MIT Alliance SMA5503

Professors Erik Demaine, Lee Wee Sun, and Charles E. Leiserson Handout 28

Problem Set 8 Solutions

MIT students: This problem set is due in lecture on Day 29.

Reading: Chapter 15, 16, 23

Both exercises and problems should be solved, but only the problems should be turned in.

Exercises are intended to help you master the course material. Even though you should not turn in

the exercise solutions, you are responsible for material covered by the exercises.

Mark the top of each sheet with your name, the course number, the problem number, your

recitation instructor and time, the date, and the names of any students with whom you collaborated.

MIT students: Each problem should be done on a separate sheet (or sheets) of three-hole punched

paper.

You will often be called upon to “give an algorithm” to solve a certain problem. Your write-up

should take the form of a short essay. A topic paragraph should summarize the problem you are

solving and what your results are. The body of your essay should provide the following:

1. A description of the algorithm in English and, if helpful, pseudocode.

2. At least one worked example or diagram to show more precisely how your algorithm works.

3. A proof (or indication) of the correctness of the algorithm.

4. An analysis of the running time of the algorithm.

Remember, your goal is to communicate. Graders will be instructed to take off points for convo-

luted and obtuse descriptions.

Handout 28: Problem Set 8 Solutions

Exercise 8-1. Do exercise 15.4-4 on page 356 of CLRS

Solution:

�

When computing a particular row of the -table, only the previous row is needed. Only two rows

need to be kept in memory at a time.

��

. If

��

, compute the LCS-LENGTH

�

otherwise compute

��

LCS-LENGTH

�

. In either case, use the method given in Exercise ?? to use

��

�

space.

Actually only one row need be kept in memory at a time. When an element of the current row

is computed, it should be stored in a temporary variable. After the next element is computed, the

previous element may be placed in the row.

Exercise 8-2. Do exercise 16.2-2 on page 384 of CLRS.

Solution:

��

�

represents the total value that can be taken from the ﬁrst

�

items when the knapsack can hold

�

Exercise 8-3. Do exercise 16.2-3 on page 384 of CLRS.

Solution:

Go greedy. Take the item with maximum value. This item also has the smallest weight and

��

therefore, the largest

�

ratio. One wouldn’t ever take something besides the optimal choice

because the optimal choice weighs at most as much and is worth as least as much as any other

item.

Exercise 8-4. Do exercise 23.2-2 on page 573 of CLRS.

Solution:

Use an array (or a ﬁeld) to store the distance of each node from the growing tree. Simply search

�

the entire list to ﬁnd the node with least distance. There are

�

iterations each taking

��

time

�

(for the search) for a total time of

��

Problem 8-1. Typesetting

In this problem you will write a program (real code that runs!) to solve the following typesetting

scenario. Because of the trouble you may encounter while programming, we advise you to

START THIS PROBLEM AS SOON AS POSSIBLE.

�

��

You have an input text consisting of a sequence of words of lengths

��

�

��

, where the

�

length of a word is the number of characters it contains. Your printer can only print with its built-in

Courier 10-point ﬁxed-width font set that allows a maximum of

�

characters per line. (Assume

�

Handout 28: Problem Set 8 Solutions

��

�

��

that

�

for all .) When printing words and on the same line, one space

character (blank) must be printed between the two words. In addition, any remaining space at the

end of the line is padded with blanks. Thus, if words

�

through

�

are printed on a line, the number

of extra space characters at the end of the line (after word

�

) is

�

��

�

��

There are many ways to divide a paragraph into multiple lines. To produce nice-looking output,

we want a division that ﬁlls each line as much as possible. A heuristic that has empirically shown

itself to be effective is to charge a cost of the cube of the number of extra space characters at the

end of each line. To avoid the unnecessary penalty for extra spaces on the last line, however, the

�

��

�

cost of the last line is

�

. In other words, the cost linecost

�

for printing words

�

through

�

on a

line is given by

�

if words

�

through

�

do not ﬁt on a line,

�

��

linecost

�

(i.e., last line),

�

��

�

��

�

��

�

otherwise

The total cost for typesetting a paragraph is the sum of the costs of all lines in the paragraph.

�

An optimal solution is an division of the words into lines in such a way that the total cost is

minimized.

(a) Argue that this problem exhibits optimal substructure.

Solution:

�

��

�

Note that

�

is deﬁned to be

�

if the words

�

through do not ﬁt on a line to

guarantee that no lines in the optimal solution overﬂow. (This relies on the assumption

�

��

�

that the length of each word is not more than

�

.) Second, notice that

�

��

is deﬁned to be 0 when

�

, where

�

is the total number of words; only the actual

last line has zero cost, not the recursive last lines of subproblems, which, since they

are not the last line overall, have the same cost formula as any other line.

�

Now, consider an optimal solution of printing words through . Let be the index

of the ﬁrst word printed on the last line of this solution. Then typesetting of words

��

�

must be optimal. Otherwise, we could paste in an optimal typesetting

of these words and improve the total cost of solution, a contradiction. Also note that

�

the same cut-and-paste argument can be applied if we take to be the index of the

�

��

ﬁrst word printed on the

�

th line, where

�

. Therefore this problem displays

optimal substructure.

(b) Recursively deﬁne the value of an optimal solution.

Solution:

�

Handout 28: Problem Set 8 Solutions

�

Let

�

be the optimal cost of printing words 1 through

�

. From part (a), it is clear

�

that given the optimal (i.e., the index of the ﬁrst word printed on the last line of an

optimal solution), we have

�

��

�

��

�

However, since we do not know what

�

is optimal, we need to consider every possible

�

, so our recursive deﬁnition of the optimal cost is

�

��

�

��

�

��

�

��

�

��

To accommodate this recursive deﬁnition, we deﬁne

�

��

�

running time and storage space of your algorithm.

Solution:

�

We calculate the values of the array from index 1 to , bottom up, which can be

�

��

�

done efﬁciently since each

��

for

�

will be available by the time

�

computed. To keep track of the actual optimal arrangement of the words, we record an

�

array

�

, where

��

is the

�

(in the recursive deﬁnition of ) which led to the optimal

�

��

. Then, after the arrays for

�

and

�

are computed, the optimal cost is

�

and the

��

optimal solution can be found by printing words

��

through

�

on the last line, words

��

�

��

�

through

��

�

on the next to last line, and so on.

�

��

�

A good optimization can be obtained by noticing that computing

�

takes

�

��

in general

��

�

time because of the summation in the formula. However, it

��

is possible to do this computation in

��

time with some additional pre-processing.

�

��

We create an auxiliary array

�

, where

�

is a cumulative sum of lengths of

�

words through

�

��

�

��

�

��

�

��

�

Filling in this array takes

��

time using recursion. In order to then compute

�

��

time, we modify the formula as follows:

�

if words

�

through

�

do not ﬁt into a line,

�

��

linecost

�

(i.e. last line),

�

��

�

��

�

��

�

��

�

otherwise

Handout 28: Problem Set 8 Solutions

��

�

This algorithm uses

��

space for the arrays and runs in

��

�

time, since each

�

value of takes up to calculations as each value of is considered. By noticing

��

that at most

��

words can ﬁt on a single line, we can reduce running time

�

��

�

—another signiﬁcant improvement—by considering only those

�

for which

�

��

�

��

when calculating each

�

(d) Write code (in any programming language you wish

) to print an optimal division of

the words into lines. For simplicity, assume that a word is any sequence of characters

that are not blanks. Thus, a word is a substring strictly between two space characters

or bounded by the beginning or end of the input.

Solution:

The following code is written in C. It is a straightforward implementation of the

�

��

�

algorithm described in part (c). The program takes as arguments the name

of the input ﬁle and a value for

�

, reads the input words from the ﬁle, computes the

optimal cost, and then reconstructs an optimal solution, which is printed out.

/* 6.046 Spring 1998 Problem 6-1(d) */

/* NOTE: This is an implementation of the O(nM) algorithm. */

/* DISCLAIMER: No effort has been made to streamline memory */

/* management or micro-optimize performance. */

/* standard header files */

#include <stdio.h>

#include <limits.h>

/* arbitrary data size limits, so no dynamic allocation needed */

#define WORD_NUM 1024 /* arbitrary max for number of input words */

#define WORD_LENGTH 32 /* arbitrary max for length of input words */

#define LINE_LENGTH 80 /* arbitrary max for length of output lines */

/* macros */

#define max(A, B) ((A) > (B) ? (A) : (B))

/* global array of words */

char words[WORD_NUM+1][WORD_LENGTH]; /* array for input words */

int auxL[WORD_NUM+1]; /* auxillary array for computing lengths

of lines - MM*/

/* function prototypes */

long linecost(int n, int M, int i, int j);

long dynamic_typeset(int n, int M, int p[]);

The solution will be written in C.

评论收藏

内容反馈

huangyime

粉丝: 0
资源: 6

算法导论课后题和解答

算法导论课后习题答案

算法导论课后习题完整答案

算法导论课后习题与思考题答案合集

算法导论-习题答案-含全部课后习题详细解答

《算法导论》第三版课后习题全解

算法导论第三版完整版答案

MIT算法导论课后习题及解答

算法导论思考题和课后解答题答案

MIT算法导论课后习题

算法导论+习题解答

算法导论（第二版）课后题解答 潘金贵译

算法导论（MIT)英文版、中文版及课后习题答案（一）

算法导论 第3版与习题解答

MIT算法导论习题解答（英文）

算法导论 第二版 课后题答案

算法导论英文版课后习题答案

算法导论 习题答案和源代码

算法导论习题解答中文版

算法导论习题解答（英文）

算法导论（MIT)英文版、中文版及课后习题答案(二)

算法导论第三版 答案

算法导论(part2)

Qt 5实现串口调试助手 （源工程文件、0积分下载）

【SystemVerilog】路科验证V2学习笔记（全600页）.pdf

AutoSAR标准协议4.2.2

光伏-储能并网系统仿真.rar

NPPJSONViewer.zip

最新资源

算法导论（第二版）课后题解答潘金贵译

算法导论第3版与习题解答

算法导论第二版课后题答案

算法导论习题答案和源代码

算法导论第三版答案

Qt 5实现串口调试助手（源工程文件、0积分下载）