中文算法导论答案非常不错资源-CSDN文库

共8个文件

pdf：8个

算法导论答案

需积分: 9 165 浏览量 2009-12-11 21:42:53 上传评论收藏 469KB RAR 举报

资源推荐

资源详情

资源评论

收起资源包目录

.rar （8个子文件）

习题答案

ps1sol.pdf 110KB

ps4sol.pdf 70KB

ps8sol.pdf 69KB

ps6sol.pdf 103KB

ps5sol.pdf 104KB

ps2sol.pdf 119KB

ps3sol.pdf 95KB

ps9sol.pdf 70KB

Introduction to Algorithms October 1, 2004

Massachusetts Institute of Technology 6.046J/18.410J

Professors Piotr Indyk and Charles E. Leiserson Handout 9

Problem Set 2 Solutions

Reading: Chapters 5-9, excluding 5.4 and 8.4

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 in the exercises.

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

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

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 the essay should provide the following:

1. A description of the algorithm in English and, if helpful, pseudo-code.

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. Full credit will be given only to correct algorithms

which are which are described clearly. Convoluted and obtuse descriptions will receive low marks.

Exercise 2-1. Do Exercise 5.2-4 on page 98 in CLRS.

Exercise 2-2. Do Exercise 8.2-3 on page 170 in CLRS.

Problem 2-1. Randomized Evaluation of Polynomials

In this problem, we consider testing the equivalence of two polynomials in a ﬁnite ﬁeld.

A ﬁeld is a set of elements for which there are addition and multiplication operations that satisfy

commutativity, associativity, and distributivity. Each element in a ﬁeld must have an additive and

multiplicative identity, as well as an additive and multiplicative inverse. Examples of ﬁelds include

the real and rational numbers.

A ﬁnite ﬁeld has a ﬁnite number of elements. In this problem, we consider the ﬁeld of integers

modulo p. That is, we consider two integers a and b to be “equal” if and only if they have the same

remainder when divided by p, in which case we write a ≡ b mod p. This ﬁeld, which we denote as

Z/p, has p elements, {0, . . . , p − 1}.

�

Handout 9: Problem Set 2 Solutions

Consider a polynomial in the ﬁeld Z/p:

a(x) = a

mod p (1)

i=0

A root or zero of a polynomial is a value of x for which a(x) = 0. The following theorem describes

the number of zeros for a polynomial of degree n.

Theorem 1 A polynomial a(x) of degree n has at most n distinct zeros.

Polly the Parrot is a very smart bird that likes to play math games. Today, Polly is thinking of a

polynomial a(x) over the ﬁeld Z/p. Though Polly will not tell you the coefﬁcients of a(x), she

will happily evaluate a(x) for any x of your choosing. She challenges you to ﬁgure out whether or

not a is equivalent to zero (that is, whether ∀x ∈ {0, . . . , p − 1} : a(x) ≡ 0 mod p).

Throughout this problem, assume that a(x) has degree n, where n < p.

(a) Using a randomized query, describe how much information you can obtain after a

single interaction with Polly. That is, if a is not equivalent to zero, then for a query x

chosen uniformly at random from {0, . . . , p−1}, what is the probability that a(x) = 0?

What if a is equivalent to zero?

Solution:

If a is not equivalent to zero, then the probability that a(x) = 0 is at most n/p. By

Theorem 1, a has at most n distinct zeros in {0, . . . , p − 1}. As we are choosing x

uniformly at random from {0, . . . , p − 1}, the probability of choosing any given x in

the ﬁeld is 1/p. Thus, the probability that the chosen x is a zero of a is at most n/p.

If a is equivalent to zero, then the probability that a(x) = 0 is 1. By deﬁnition, if a is

equivalent to zero, then a(x) = 0 for all x ∈ {0, . . . , p − 1}.

(b) If n = 10 and p = 101, how many interactions with Polly do you need to be 99%

certain whether or not a is equivalent to zero?

Solution:

Our strategy is to send k queries to Polly, each time evaluating a(x) for a random

x as described in Part (a). If each query evaluates to zero, then we report that a is

equivalent to zero. Otherwise, we report that a is not equivalent to zero.

In the event that a is equivalent to zero, then our report will always be correct (even

for k = 1). Thus, we focus on the case when a is not equivalent to zero. If we ﬁnd

that any query does not evaluate to zero, then our report will also be correct (since a

is not equivalent to zero for a certain x).

Handout 9: Problem Set 2 Solutions

The problem thus becomes: if a is not equivalent to zero, choose k such that the

probability that all k queries evaluate to zero is no more than 1%. Let � denote the

margin of error in the general case (� = 1% in this part), and let Q

be a random

variable indicating the result of the ith query. The constraint is as follows:

� ≥ Pr[Q

= 0 and Q

= 0 and . . . and Q

= 0]

= Pr[Q

= 0]Pr[Q

= 0] . . . Pr[Q

= 0]

≥ (n/p)

The ﬁrst step follows from the fact that all of the queries are independent. The second

step utilizes the bound from Part (a). Solving for k, we have:

(n/p)

≤ �

k lg(n/p) ≤ lg �

k ≥ lg �/ lg(n/p)

The last step above utilizes the assumption that n < p, and thus lg(n/p) < 0.

Substituting � = 0.01, n = 10 and p = 101 gives k ≥ 1.991. Thus, k = 2 ensures that

we are 99% certain whether or not a is equivalent to zero.

Later, you are given three polynomials: a(x), b(x), and c(x). The degree of a(x) is n, while b(x)

and c(x) are of degree n/2. You are interested in determining whether or not a(x) is equivalent to

b(x) ∗ c(x); that is, whether ∀x ∈ {0, . . . , p − 1} : a(x) ≡ b(x) ∗ c(x) mod p.

Professor Potemkin recalls that in Problem Set 1, you showed how to multiply polynomials in

�(n

(3)

) time. Potemkin suggests using this procedure to directly compare the polynomials.

However, recalling your fun times with Polly, you convince Potemkin that there might be an even

more efﬁcient procedure, if some margin of error is tolerated.

is equivalent to b(x) ∗ c(x). Analyze its running time and compare to Potemkin’s

proposal.

Solution:

The algorithm checks the equivalence of a(x) and b(x) ∗ c(x) by testing if a(x) −

b(x) ∗ c(x) is equivalent to zero. The testing is done using the randomized procedure

developed in Part (b), choosing k to ensure the desired level of certainty. Pseudocode

for the algorithm is as follows:

�

� �

Handout 9: Problem Set 2 Solutions

� Returns whether a(x) ≡ b(x) ∗ c(x) mod p ∀x ∈ {0, . . . , p − 1}

� Correct with probability at least 1 − �

EQUIV(a[0 . . . n], b[0 . . . n/2], c[0 . . . n/2], p, �)

1 k ← lg �/ lg(n/p)

2 for i ← 1 to k

3 do x ← RANDOM(0, q − 1)

4 a

�

← a(x)

5 b

�

← b(x)

6 c

�

← c(x)

7 if a

�

− b

�

∗ c ≡ 0 ( mod p)

8 then return false

9 return true

Correctness. For a given value of x, a(x) = b(x) ∗ c(x) if and only if a(x) − b(x) ∗

c(x) = 0. Thus, a(x) is equivalent to b(x) ∗ c(x) if and only if a(x) − b(x) ∗ c(x) is

equivalent to zero. Our solution to Part (b) shows how to determine with probability

at least 1 − � whether or not a given polynomial is equivalent to zero. Using this same

procedure, we test whether or not a(x) − b(x) ∗ c(x) is equivalent to zero, thereby

determining whether or not a(x) is equivalent to b(x) ∗ c(x).

Running time. We count the number of arithmetic operations in EQUIV. In this class,

we assume that steps 1 and 7 are �(1), as they are arithmetic operations on scalar

values; also, we assume that the call to R

ANDOM on line 3 is �(1). Each polynomial

evaluation on lines 4-6 is �(n), as an n-degree polynomial can be evaluated in �(n)

time using Horner’s rule. The loop runs k = lg �/ lg(n/p) times, performing �(n)

work on each iteration. The total runtime is thus T (n) = �(nlg �/ lg(n/p)).

Consider Potemkin’s proposal, with a runtime P (n) = �(n

(3)

), and let us evalu-

ate the conditions under which T (n) = O(P (n)). Note that, in the runtime of our

algorithm, we cannot consider p to be ﬁxed as n grows, since we require that n < p.

T (n) = O(P (n))

nlg �/ lg(n/p) ≤ cn

(3)

lg �/ lg(n/p) ≤ cn

(3)−1

(2)

That is, the running time of our algorithm is bounded above by the running time of

Potemkin’s algorithm so long as p and � satisfy Equation 2 for sufﬁciently large n.

For example, consider that p = c n for some c > 1 and � is a ﬁxed constant. Then

lg �/ lg(n/p) = lg �/ lg(1/c

�

) = �(1). Thus, the loop executes �(1) times and

the algorithm is has a running time of �(n), which is asymptotically faster than

Potemkin’s proposal.

On the other hand, if p = n + 1 while � remains ﬁxed, then lg �/ lg(n/p) =

lg �/ lg(n/(n + 1)) = lg �/(lg n − lg(n + 1))). Intuitively, one can see that this

评论收藏

内容反馈

hillox352009

粉丝: 11
资源: 10

中文算法导论答案非常不错

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

算法导论答案就中文版

算法导论中英文答案详解

算法导论课后答案 中文版

《算法导论(第二版)》(中文版)课后答案.pdf

算法导论中文版答案

算法导论中文第三版习题答案

算法导论答案（中文版，很全）

算法导论第二版课后答案中文完全版

算法导论答案 挺全的 有中文版和部分英文版

算法导论中文版答案详解

算法导论答案

算法导论的答案中文版

算法导论习题答案 中文版

算法导论答案 中文版

算法导论（第三版）基本完整中文版答案

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

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

AutoSAR标准协议4.2.2

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

NPPJSONViewer.zip

GD32替换STM32注意事项.pdf

XCP协议的规范文档

VS2015安装证书，JavaScript_ProjectSystem.msi，JavaScript_LanguageService.msi

CANoe通过CAPL脚本实现自动测试

蓝牙BLE协议中文版.pdf

BaiduOCR.zip

AD20官方中文教程.pdf

电路分析基础第二版PDF电子书免费下载

最新资源

算法导论课后答案中文版

算法导论答案挺全的有中文版和部分英文版

算法导论习题答案中文版

算法导论答案中文版

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