没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
Introduction to Algorithms, Third Edition
Supplemental Content
This page contains supplemental content for Introduction to Algorithms, Third Edition.
Bug reports:
A list of known bugs and errata may be found here. Please review this list before sending a
new bug report. Reports of previously-unreported bugs, misprints, and other errata may be
sent to algorithm-bugs@mitpress.mit.edu.
Solutions to exercises and problems:
As of the third edition, solutions for a select set of exercises and problems are available here
in PDF format:
• Chapter 2: Getting Started
• Chapter 3: Growth of Functions
• Chapter 4: Divide-and-Conquer
• Chapter 5: Probabilistic Analysis and Randomized Algorithms
• Chapter 6: Heapsort
• Chapter 7: Quicksort
• Chapter 8: Sorting in Linear Time
• Chapter 9: Medians and Order Statistics
• Chapter 11: Hash Tables
• Chapter 12: Binary Search Trees
• Chapter 13: Red-Black Trees
• Chapter 14: Augmenting Data Structures
• Chapter 15: Dynamic Programming
• Chapter 16: Greedy Algorithms
• Chapter 17: Amortized Analysis
• Chapter 21: Data Structures for Disjoint Sets
• Chapter 22: Elementary Graph Algorithms
• Chapter 23: Minimum Spanning Trees
• Chapter 24: Single-Source Shortest Paths
• Chapter 25: All-Pairs Shortest Paths
• Chapter 26: Maximum Flow
Instructor's Manual:
An instructor’s manual is available to instructors who have adopted the book for course use.
The manual is not available to students, or to those studying the book on their own.
Instructors with access to the manual must agree not to share the manual’s password, to make
any of the solutions publicly accessible, on the Web or otherwise, or to make any of their own
solutions publicly available.
Instructors using the MIT Press English language edition of the book may request access to
the online instructor’s manual here
.
Instructors using the book in another language should contact the publisher licensing the book
in that language.
clrscode3e:
The clrscode3e package gives you pseudocode in the style of the third edition.
You can download the package and its documentation here.
Professor jokes:
Wondering about the professor names in the text? The jokes are explained here.
Book details:
Complete details for the cloth edition of Introduction to Algorithms, Third Edition (available
worldwide)
Complete details for the international student paperback edition of Introduction to Algorithms,
Third Edition (available outside the U.S. and Canada)
Charles Leiserson discusses the third edition:
As of the third edition, this textbook is published exclusively by the MIT Press.
Please refer any other inquiries to the appropriate representative of the MIT Press
Selected Solutions for Chapter 2:
Getting Started
Solution to Exercise 2.2-2
SELECTION-SORT.A/
n D A:length
for j D 1 to n 1
smallest D j
for i D j C 1 to n
if AŒi < AŒsmallest
smallest D i
exchange AŒj with AŒsmallest
The algorithm maintains the loop invariant that at the start of each iteration of the
outer for loop, the subarray AŒ1 : : j 1 consists of the j 1 smallest elements
in the array AŒ1 : : n, and this subarray is in sorted order. After the first n 1
elements, the subarray AŒ1 : : n 1 contains the smallest n 1 elements, sorted,
and therefore element AŒn must be the largest element.
The running time of the algorithm is ‚.n
2
/ for all cases.
Solution to Exercise 2.2-4
Modify the algorithm so it tests whether the input satisfies some special-case con-
dition and, if it does, output a pre-computed answer. The best-case running time is
generally not a good measure of an algorithm.
Solution to Exercise 2.3-5
Procedure BINARY-SEARCH takes a sorted array A, a value , and a range
Œlow : : high of the array, in which we search for the value . The procedure com-
pares to the array entry at the midpoint of the range and decides to eliminate half
the range from further consideration. We give both iterative and recursive versions,
each of which returns either an index i such that AŒi D , or NIL if no entry of
2-2 Selected Solutions for Chapter 2: Getting Started
AŒlow : : high contains the value . The initial call to either version should have
the parameters A; ; 1; n.
ITERATIVE-BINARY-SEARCH.A; ; low; high/
while low high
mid D
b
.low C high/=2
c
if
==
AŒmid
return mid
elseif > AŒmid
low D mid C 1
else high D mid 1
return NIL
RECURSIVE-BINARY-SEARCH.A; ; low; high/
if low > high
return NIL
mid D
b
.low C high/=2
c
if
==
AŒmid
return mid
elseif > AŒmid
return RECURSIVE-BINARY-SEARCH.A; ; mid C 1; high/
else return RECURSIVE-BINARY-SEARCH.A; ; low; mid 1/
Both procedures terminate the search unsuccessfully when the range is empty (i.e.,
low > high) and terminate it successfully if the value has been found. Based
on the comparison of to the middle element in the searched range, the search
continues with the range halved. The recurrence for these procedures is therefore
T .n/ D T .n=2/ C ‚.1/, whose solution is T .n/ D ‚.lg n/.
Solution to Problem 2-4
a. The inversions are .1; 5/; .2; 5/; .3; 4/; .3; 5/; .4; 5/. (Remember that inversions
are specified by indices rather than by the values in the array.)
b. The array with elements from
f
1; 2; : : : ; n
g
with the most inversions is
hn; n 1; n 2; : : : ; 2; 1i. For all 1 i < j n, there is an inversion .i; j /.
The number of such inversions is
n
2
D n.n 1/=2.
c. Suppose that the array A starts out with an inversion .k; j /. Then k < j and
AŒk > AŒj . At the time that the outer for loop of lines 1–8 sets key D AŒj ,
the value that started in AŒk is still somewhere to the left of AŒj . That is,
it’s in AŒi, where 1 i < j , and so the inversion has become .i; j /. Some
iteration of the while loop of lines 5–7 moves AŒi one position to the right.
Line 8 will eventually drop key to the left of this element, thus eliminating the
inversion. Because line 5 moves only elements that are less than key, it moves
only elements that correspond to inversions. In other words, each iteration of
the while loop of lines 5–7 corresponds to the elimination of one inversion.
Selected Solutions for Chapter 2: Getting Started 2-3
d. We follow the hint and modify merge sort to count the number of inversions in
‚.n lgn/ time.
To start, let us define a merge-inversion as a situation within the execution of
merge sort in which the MERGE procedure, after copying AŒp : : q to L and
AŒq C 1 : : r to R, has values x in L and y in R such that x > y. Consider
an inversion .i; j /, and let x D AŒi and y D AŒj , so that i < j and x > y.
We claim that if we were to run merge sort, there would be exactly one merge-
inversion involving x and y. To see why, observe that the only way in which
array elements change their positions is within the MERGE procedure. More-
over, since MERGE keeps elements within L in the same relative order to each
other, and correspondingly for R, the only way in which two elements can
change their ordering relative to each other is for the greater one to appear in L
and the lesser one to appear in R. Thus, there is at least one merge-inversion
involving x and y. To see that there is exactly one such merge-inversion, ob-
serve that after any call of MERGE that involves both x and y, they are in the
same sorted subarray and will therefore both appear in L or both appear in R
in any given call thereafter. Thus, we have proven the claim.
We have shown that every inversion implies one merge-inversion. In fact, the
correspondence between inversions and merge-inversions is one-to-one. Sup-
pose we have a merge-inversion involving values x and y, where x originally
was AŒi and y was originally AŒj . Since we have a merge-inversion, x > y.
And since x is in L and y is in R, x must be within a subarray preceding the
subarray containing y. Therefore x started out in a position i preceding y’s
original position j , and so .i; j / is an inversion.
Having shown a one-to-one correspondence between inversions and merge-
inversions, it suffices for us to count merge-inversions.
Consider a merge-inversion involving y in R. Let ´ be the smallest value in L
that is greater than y. At some point during the merging process, ´ and y will
be the “exposed” values in L and R, i.e., we will have ´ D LŒi and y D RŒj
in line 13 of MERGE. At that time, there will be merge-inversions involving y
and LŒi; LŒi C 1; LŒi C 2; : : : ; LŒn
1
, and these n
1
i C 1 merge-inversions
will be the only ones involving y. Therefore, we need to detect the first time
that ´ and y become exposed during the MERGE procedure and add the value
of n
1
i C 1 at that time to our total count of merge-inversions.
The following pseudocode, modeled on merge sort, works as we have just de-
scribed. It also sorts the array A.
COUNT-INVERSIONS.A; p; r/
inersions D 0
if p < r
q D b.p C r/=2c
inersions D inersions C COUNT-INVERSIONS. A; p; q/
inersions D inersions C COUNT-INVERSIONS. A; q C 1; r/
inersions D inersions C MERGE-INVERSIONS.A; p; q; r/
return inersions
剩余71页未读,继续阅读
资源评论
- 冰枫琪缘2019-08-28经本人验证,这里面有很多答案是错误的,建议各位仔细审题后参照使用。不建议直接照抄。
sinat_22535507
- 粉丝: 0
- 资源: 2
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功