算法导论习题答案MITpress

需积分: 9 66 浏览量更新于2023-03-16 评论 3 收藏 298KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

Solutions for Introduction to algorithms

second edition

Philip Bille

The author of this document takes absolutely no responsibility for the contents. This is merely

a vague suggestion to a solution to some of the exercises posed in the book Introduction to algo-

rithms by Cormen, Leiserson and Rivest. It is very likely that there are many errors and that the

solutions are wrong. If you have found an error, have a better solution or wish to contribute in

some constructive way please send a message to beetle@it.dk.

It is important that you try hard to solve the exercises on your own. Use this document only as

a last resort or to check if your instructor got it all wrong.

Please note that the document is under construction and is updated only sporadically. Have

fun with your algorithms.

Best regards,

Philip Bille

Last update: December 9, 2002

DocuCom PDF Trial

www.pdfwizard.com

󰂼󰇒󰆘

3.1 − 1

Let f(n), g(n) be asymptotically nonnegative. Show that max(f(n), g(n)) = Θ(f(n) + g(n)). This

means that there exists positive constants c

, c

and n

such that,

0 6 c

(f(n) + g(n)) 6 max(f(n), g(n)) 6 c

(f(n) + g(n))

for all n > n

Selecting c

= 1 clearly shows the third inequality since the maximum must be smaller than

the sum. c

should be selected as 1/2 since the maximum is always greater than the weighted

average of f(n) and g(n). Note the signiﬁcance of the “asymptotically nonnegative” assumption.

The ﬁrst inequality could not be satisﬁed otherwise.

3.1 − 4

n+1

= O(2

) since 2

n+1

= 2 · 2

6 2 · 2

! However 2

is not O(2

): by deﬁnition we have

= (2

)

which for no constant c asymptotically may be less than or equal to c ·2

3 − 4

Let f(n) and g(n) be asymptotically positive functions.

a. No, f(n) = O(g(n)) does not imply g(n) = O(f(n)). Clearly, n = O(n

) but n

6= O(n).

b. No, f(n) + g(n) is not Θ(min(f(n), g(n))). As an example notice that n + 1 6= Θ(min(n, 1)) =

Θ(1).

c. Yes, if f(n) = O(g(n)) then lg(f(n)) = O(lg(g(n))) provided that f(n) > 1 and lg(g(n)) > 1

are greater than or equal 1. We have that:

f(n) 6 cg(n) ⇒lg f(n) 6 lg(cg(n)) = lg c + lg g(n)

To show that this is smaller than b lg g(n) for some constant b we set lg c + lg g(n) = b lg g(n).

Dividing by lg g(n) yields:

b =

lg(c) + lg g(n)

lg g(n)

lg c

lg g(n)

+ 1 6 lg c + 1

The last inequality holds since lg g(n) > 1.

d. No, f(n) = O(g(n)) does not imply 2

f(n)

= O(2

g(n)

). If f(n) = 2n and g(n) = n we have that

2n 6 2 · n but not 2

6 c2

for any constant c by exercise 3.1 − 4.

e. Yes and no, if f(n) < 1 for large n then f(n)

< f(n) and the upper bound will not hold.

Otherwise f(n) > 1 and the statement is trivially true.

f. Yes, f(n) = O(g(n)) implies g(n) = Ω(f(n)). We have f(n) 6 cg(n) for positive c and thus

1/c · f(n) 6 g(n).

g. No, clearly 2

66 c2

n/2

= c

√

for any constant c if n is sufﬁciently large.

h. By a small modiﬁcation to exercise 3.1−1 we have that f(n)+o(f(n)) = Θ(max(f(n), o(f(n)))) =

Θ(f(n)).

DocuCom PDF Trial

www.pdfwizard.com

剩余50页未读，继续阅读

sunwaysshe

粉丝: 13
资源: 25

会员权益专享

算法导论习题答案 MIT press

评论0

会员权益专享

最新资源

算法导论习题答案 MIT press

评论0

顺序排程法，倒序排程法和基于事件的模拟排程法分别适合什么样的场景

oscarHibernate5.jar

国产神通数据库用到的jdbc驱动包、集成Hibernate用到的jar包

mit算法导论 课件

算法导论第三版答案 pdf

mit算法导论bellman笔记

算法导论 csdn pdf

算法导论第三版答案中文pdf

算法导论 下载 csdn

awz3 算法导论 电子书

算法导论 baase gelder

算法导论第三版第四章答案

算法导论中文版pdf

算法导论pdf完整版

算法导论23章算法导论23章最小生成树习题

算法导论 第三版pdf

clrs算法导论pdf

算法导论第三版instructor’s manual

生物信息学算法导论 solution

算法导论第三版epub

会员权益专享

最新资源

mit算法导论课件

算法导论下载 csdn

awz3 算法导论电子书

算法导论第三版pdf