Source code online books for professionals by professionals



Download 4,67 Mb.
Pdf ko'rish
bet263/266
Sana31.12.2021
Hajmi4,67 Mb.
#213682
1   ...   258   259   260   261   262   263   264   265   266
Bog'liq
2 5296731884800181221

Contents
About the Author ����������������������������������������������������������������������������������������������������������������
xv
About the Technical Reviewer ������������������������������������������������������������������������������������������
xvii
Acknowledgments �������������������������������������������������������������������������������������������������������������
xix
Preface ������������������������������������������������������������������������������������������������������������������������������
xxi
Chapter 1
 


Introduction �����������������������������������������������������������������������������������������������������
1
What’s All This, Then? ��������������������������������������������������������������������������������������������������������������������
2
What the book is about: �����������������������������������������������������������������������������������������������������������������������������������������
3
What the book covers only briefly or partially: ������������������������������������������������������������������������������������������������������
3
What the book isn’t about: �������������������������������������������������������������������������������������������������������������������������������������
3
Why Are You Here? ������������������������������������������������������������������������������������������������������������������������
3
Some Prerequisites �����������������������������������������������������������������������������������������������������������������������
4
What’s in This Book �����������������������������������������������������������������������������������������������������������������������
5
Summary ���������������������������������������������������������������������������������������������������������������������������������������
6
If You’re Curious …  ����������������������������������������������������������������������������������������������������������������������
6
Exercises ���������������������������������������������������������������������������������������������������������������������������������������
6
References ������������������������������������������������������������������������������������������������������������������������������������
7
Chapter 2
 


The Basics �������������������������������������������������������������������������������������������������������
9
Some Core Ideas in Computing �����������������������������������������������������������������������������������������������������
9
Asymptotic Notation ��������������������������������������������������������������������������������������������������������������������
10
It’s Greek to Me! ��������������������������������������������������������������������������������������������������������������������������������������������������
12
Rules of the Road ������������������������������������������������������������������������������������������������������������������������������������������������
14
Taking the Asymptotics for a Spin �����������������������������������������������������������������������������������������������������������������������
15



 Contents
viii
Three Important Cases ����������������������������������������������������������������������������������������������������������������������������������������
18
Empirical Evaluation of Algorithms ����������������������������������������������������������������������������������������������������������������������
19
Implementing Graphs and Trees ��������������������������������������������������������������������������������������������������
22
Adjacency Lists and the Like �������������������������������������������������������������������������������������������������������������������������������
24
Adjacency Matrices ���������������������������������������������������������������������������������������������������������������������������������������������
27
Implementing Trees ���������������������������������������������������������������������������������������������������������������������������������������������
30
A Multitude of Representations ���������������������������������������������������������������������������������������������������������������������������
33
Beware of Black Boxes ����������������������������������������������������������������������������������������������������������������
34
Hidden Squares ���������������������������������������������������������������������������������������������������������������������������������������������������
35
The Trouble with Floats����������������������������������������������������������������������������������������������������������������������������������������
36
Summary �������������������������������������������������������������������������������������������������������������������������������������
38
If You’re Curious … ���������������������������������������������������������������������������������������������������������������������
39
Exercises �������������������������������������������������������������������������������������������������������������������������������������
39
References ����������������������������������������������������������������������������������������������������������������������������������
40
Chapter 3
 


Counting 101 �������������������������������������������������������������������������������������������������
43
The Skinny on Sums ��������������������������������������������������������������������������������������������������������������������
43
More Greek ����������������������������������������������������������������������������������������������������������������������������������������������������������
44
Working with Sums ���������������������������������������������������������������������������������������������������������������������������������������������
44
A Tale of Two Tournaments ����������������������������������������������������������������������������������������������������������
45
Shaking Hands �����������������������������������������������������������������������������������������������������������������������������������������������������
45
The Hare and the Tortoise ������������������������������������������������������������������������������������������������������������������������������������
47
Subsets, Permutations, and Combinations ����������������������������������������������������������������������������������
50
Recursion and Recurrences ��������������������������������������������������������������������������������������������������������
53
Doing It by Hand ��������������������������������������������������������������������������������������������������������������������������������������������������
53
A Few Important Examples ����������������������������������������������������������������������������������������������������������������������������������
55
Guessing and Checking ���������������������������������������������������������������������������������������������������������������������������������������
58
The Master Theorem: A Cookie-Cutter Solution ���������������������������������������������������������������������������������������������������
60
So What Was All That About? �������������������������������������������������������������������������������������������������������
63
Summary �������������������������������������������������������������������������������������������������������������������������������������
64



 Contents
ix
If You’re Curious ��� ����������������������������������������������������������������������������������������������������������������������
65
Exercises �������������������������������������������������������������������������������������������������������������������������������������
65
References ����������������������������������������������������������������������������������������������������������������������������������
66
Chapter 4
 


Induction and Recursion ��� and Reduction ����������������������������������������������������
67
Oh, That’s Easy! ���������������������������������������������������������������������������������������������������������������������������
68
One, Two, Many ����������������������������������������������������������������������������������������������������������������������������
69
Mirror, Mirror �������������������������������������������������������������������������������������������������������������������������������
71
Designing with Induction (and Recursion) �����������������������������������������������������������������������������������
75
Finding a Maximum Permutation ������������������������������������������������������������������������������������������������������������������������
76
The Celebrity Problem �����������������������������������������������������������������������������������������������������������������������������������������
80
Topological Sorting ����������������������������������������������������������������������������������������������������������������������������������������������
82
Stronger Assumptions �����������������������������������������������������������������������������������������������������������������
85
Invariants and Correctness ���������������������������������������������������������������������������������������������������������
86
Relaxation and Gradual Improvement �����������������������������������������������������������������������������������������
87
Reduction + Contraposition = Hardness Proof ����������������������������������������������������������������������������
88
Problem Solving Advice ���������������������������������������������������������������������������������������������������������������
89
Summary �������������������������������������������������������������������������������������������������������������������������������������
90
If You’re Curious ��� ����������������������������������������������������������������������������������������������������������������������
90
Exercises �������������������������������������������������������������������������������������������������������������������������������������
91
References ����������������������������������������������������������������������������������������������������������������������������������
92
Chapter 5
 


Traversal: The Skeleton Key of Algorithmics �������������������������������������������������
93
A Walk in the Park �����������������������������������������������������������������������������������������������������������������������
99
No Cycles Allowed ���������������������������������������������������������������������������������������������������������������������������������������������
100
How to Stop Walking in Circles ��������������������������������������������������������������������������������������������������������������������������
101
Go Deep! ������������������������������������������������������������������������������������������������������������������������������������
102
Depth-First Timestamps and Topological Sorting (Again) ����������������������������������������������������������������������������������
104
Infinite Mazes and Shortest (Unweighted) Paths ����������������������������������������������������������������������
106
Strongly Connected Components ����������������������������������������������������������������������������������������������
109
Summary �����������������������������������������������������������������������������������������������������������������������������������
112



 Contents
x
If You’re Curious ��� ��������������������������������������������������������������������������������������������������������������������
112
Exercises �����������������������������������������������������������������������������������������������������������������������������������
112
References ��������������������������������������������������������������������������������������������������������������������������������
113
Chapter 6
 


Divide, Combine, and Conquer ���������������������������������������������������������������������
115
Tree-Shaped Problems: All About the Balance ��������������������������������������������������������������������������
115
The Canonical D&C Algorithm ���������������������������������������������������������������������������������������������������
117
Searching by Halves ������������������������������������������������������������������������������������������������������������������
118
Traversing Search Trees ��� with Pruning �����������������������������������������������������������������������������������������������������������
120
Selection ������������������������������������������������������������������������������������������������������������������������������������������������������������
123
Sorting by Halves ����������������������������������������������������������������������������������������������������������������������
125
How Fast Can We Sort? �������������������������������������������������������������������������������������������������������������������������������������
127
Three More Examples ����������������������������������������������������������������������������������������������������������������
127
Closest Pair ��������������������������������������������������������������������������������������������������������������������������������������������������������
127
Convex Hull ��������������������������������������������������������������������������������������������������������������������������������������������������������
129
Greatest Slice ����������������������������������������������������������������������������������������������������������������������������������������������������
130
Tree Balance ��� and Balancing
*
 �������������������������������������������������������������������������������������������������
131
Summary �����������������������������������������������������������������������������������������������������������������������������������
136
If You’re Curious ��� ��������������������������������������������������������������������������������������������������������������������
137
Exercises �����������������������������������������������������������������������������������������������������������������������������������
137
References ��������������������������������������������������������������������������������������������������������������������������������
138
Chapter 7
 


Greed Is Good? Prove It!  �����������������������������������������������������������������������������
139
Staying Safe, Step by Step ��������������������������������������������������������������������������������������������������������
139
The Knapsack Problem ��������������������������������������������������������������������������������������������������������������
143
Fractional Knapsack ������������������������������������������������������������������������������������������������������������������������������������������
143
Integer Knapsack �����������������������������������������������������������������������������������������������������������������������������������������������
143
Huffman’s Algorithm ������������������������������������������������������������������������������������������������������������������
144
The Algorithm ����������������������������������������������������������������������������������������������������������������������������������������������������
145
The First Greedy Choice �������������������������������������������������������������������������������������������������������������������������������������
147
Going the Rest of the Way����������������������������������������������������������������������������������������������������������������������������������
147
Optimal Merging ������������������������������������������������������������������������������������������������������������������������������������������������
148



 Contents
xi
Minimum Spanning Trees ����������������������������������������������������������������������������������������������������������
149
The Shortest Edge ���������������������������������������������������������������������������������������������������������������������������������������������
149
What About the Rest? ����������������������������������������������������������������������������������������������������������������������������������������
151
Kruskal’s Algorithm��������������������������������������������������������������������������������������������������������������������������������������������
151
Prim’s Algorithm ������������������������������������������������������������������������������������������������������������������������������������������������
153
Greed Works� But When? �����������������������������������������������������������������������������������������������������������
155
Keeping Up with the Best ����������������������������������������������������������������������������������������������������������������������������������
155
No Worse Than Perfect ��������������������������������������������������������������������������������������������������������������������������������������
157
Staying Safe ������������������������������������������������������������������������������������������������������������������������������������������������������
157
Summary �����������������������������������������������������������������������������������������������������������������������������������
159
If You’re Curious … �������������������������������������������������������������������������������������������������������������������
160
Exercises �����������������������������������������������������������������������������������������������������������������������������������
160
References ��������������������������������������������������������������������������������������������������������������������������������
161
Chapter 8
 


Tangled Dependencies and Memoization�����������������������������������������������������
163
Don’t Repeat Yourself ����������������������������������������������������������������������������������������������������������������
164
Shortest Paths in Directed Acyclic Graphs ��������������������������������������������������������������������������������
170
Longest Increasing Subsequence ���������������������������������������������������������������������������������������������
172
Sequence Comparison ��������������������������������������������������������������������������������������������������������������
175
The Knapsack Strikes Back �������������������������������������������������������������������������������������������������������
178
Binary Sequence Partitioning ����������������������������������������������������������������������������������������������������
180
Summary �����������������������������������������������������������������������������������������������������������������������������������
183
If You’re Curious … �������������������������������������������������������������������������������������������������������������������
183
Exercises �����������������������������������������������������������������������������������������������������������������������������������
184
References ��������������������������������������������������������������������������������������������������������������������������������
185
Chapter 9
 


From A to B with Edsger and Friends ����������������������������������������������������������
187
Propagating Knowledge ������������������������������������������������������������������������������������������������������������
188
Relaxing like Crazy ��������������������������������������������������������������������������������������������������������������������
189
Finding the Hidden DAG ������������������������������������������������������������������������������������������������������������
194
All Against All �����������������������������������������������������������������������������������������������������������������������������
197



 Contents
xii
Far-Fetched Subproblems ���������������������������������������������������������������������������������������������������������
198
Meeting in the Middle ���������������������������������������������������������������������������������������������������������������
201
Knowing Where You’re Going ����������������������������������������������������������������������������������������������������
203
Summary �����������������������������������������������������������������������������������������������������������������������������������
206
If You’re Curious ��� ��������������������������������������������������������������������������������������������������������������������
207
Exercises �����������������������������������������������������������������������������������������������������������������������������������
207
References ��������������������������������������������������������������������������������������������������������������������������������
208
Chapter 10
 


Matchings, Cuts, and Flows  ����������������������������������������������������������������������
209
Bipartite Matching ���������������������������������������������������������������������������������������������������������������������
210
Disjoint Paths ����������������������������������������������������������������������������������������������������������������������������
212
Maximum Flow ��������������������������������������������������������������������������������������������������������������������������
215
Minimum Cut �����������������������������������������������������������������������������������������������������������������������������
218
Cheapest Flow and the Assignment Problem
*
 ���������������������������������������������������������������������������
219
Some Applications ���������������������������������������������������������������������������������������������������������������������
221
Summary �����������������������������������������������������������������������������������������������������������������������������������
224
If You’re Curious … �������������������������������������������������������������������������������������������������������������������
224
Exercises �����������������������������������������������������������������������������������������������������������������������������������
224
References ��������������������������������������������������������������������������������������������������������������������������������
225
Chapter 11
 


Hard Problems and (Limited) Sloppiness ��������������������������������������������������
227
Reduction Redux �����������������������������������������������������������������������������������������������������������������������
228
Not in Kansas Anymore? �����������������������������������������������������������������������������������������������������������
230
Meanwhile, Back in Kansas … �������������������������������������������������������������������������������������������������
232
But Where Do You Start? And Where Do You Go from There? ����������������������������������������������������
235
A Ménagerie of Monsters ����������������������������������������������������������������������������������������������������������
239
Return of the Knapsack �������������������������������������������������������������������������������������������������������������������������������������
239
Cliques and Colorings ����������������������������������������������������������������������������������������������������������������������������������������
240
Paths and Circuits ����������������������������������������������������������������������������������������������������������������������������������������������
242
When the Going Gets Tough, the Smart Get Sloppy �������������������������������������������������������������������
245
Desperately Seeking Solutions ��������������������������������������������������������������������������������������������������
247



 Contents
xiii
And the Moral of the Story Is … �����������������������������������������������������������������������������������������������
249
Summary �����������������������������������������������������������������������������������������������������������������������������������
250
If You’re Curious … �������������������������������������������������������������������������������������������������������������������
251
Exercises �����������������������������������������������������������������������������������������������������������������������������������
251
References ��������������������������������������������������������������������������������������������������������������������������������
252
Appendix A
 


Pedal to the Metal: Accelerating Python ���������������������������������������������������
255
Appendix B
 


List of Problems and Algorithms ���������������������������������������������������������������
259
Problems �����������������������������������������������������������������������������������������������������������������������������������
259
Algorithms and Data Structures ������������������������������������������������������������������������������������������������
262
Appendix C
 


Graph Terminology ������������������������������������������������������������������������������������
267
Appendix D
 


Hints for Exercises ������������������������������������������������������������������������������������
273
Chapter 1 �����������������������������������������������������������������������������������������������������������������������������������
273
Chapter 2 �����������������������������������������������������������������������������������������������������������������������������������
273
Chapter 3 �����������������������������������������������������������������������������������������������������������������������������������
275
Chapter 4 �����������������������������������������������������������������������������������������������������������������������������������
276
Chapter 5 �����������������������������������������������������������������������������������������������������������������������������������
278
Chapter 6 �����������������������������������������������������������������������������������������������������������������������������������
279
Chapter 7 �����������������������������������������������������������������������������������������������������������������������������������
280
Chapter 8 �����������������������������������������������������������������������������������������������������������������������������������
282
Chapter 9 �����������������������������������������������������������������������������������������������������������������������������������
283
Chapter 10 ���������������������������������������������������������������������������������������������������������������������������������
284
Chapter 11 ���������������������������������������������������������������������������������������������������������������������������������
285
Index ���������������������������������������������������������������������������������������������������������������������������������
289


xv

Download 4,67 Mb.

Do'stlaringiz bilan baham:
1   ...   258   259   260   261   262   263   264   265   266




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish