Hetland Python Algorithms

Mastering Basic Algorithms in the Python Language
2. Auflage 2014
ISBN: 978-1-4842-0055-1
Verlag: APRESS
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 303 Seiten, eBook

Python Algorithms, Second Edition explains the Python approach to algorithm analysis and design. Written by Magnus Lie Hetland, author of Beginning Python, this book is sharply focused on classical algorithms, but it also gives a solid understanding of fundamental algorithmic problem-solving techniques. The book deals with some of the most important and challenging areas of programming and computer science in a highly readable manner. It covers both algorithmic theory and programming practice, demonstrating how theory is reflected in real Python programs. Well-known algorithms and data structures that are built into the Python language are explained, and the user is shown how to implement and evaluate others.

Zielgruppe

Popular/general

Autoren/Hrsg.

Hetland, Magnus Lie

Inhaltsverzeichnis

1;Contents at a Glance;3
2;Contents;293
3;About the Author;300
4;About the Technical Reviewer;301
5;Acknowledgments;302
6;Preface;303
7;Chapter 1: Introduction;5
7.1;What’s All This, Then?;6
7.2;Why Are You Here?;7
7.3;Some Prerequisites;8
7.4;What’s in This Book;9
7.5;Summary;10
7.6;If You’re Curious …;10
7.7;Exercises;10
7.8;References;11
8;Chapter 2: The Basics;12
8.1;Some Core Ideas in Computing;12
8.2;Asymptotic Notation;13
8.2.1;It’s Greek to Me!;15
8.2.2;Rules of the Road;17
8.2.3;Taking the Asymptotics for a Spin;18
8.2.4;Three Important Cases;21
8.2.5;Empirical Evaluation of Algorithms;22
8.3;Implementing Graphs and Trees;25
8.3.1;Adjacency Lists and the Like;27
8.3.2;Adjacency Matrices;30
8.3.3;Implementing Trees;33
8.3.4;A Multitude of Representations;36
8.4;Beware of Black Boxes;37
8.4.1;Hidden Squares;38
8.4.2;The Trouble with Floats;39
8.5;Summary;41
8.6;If You’re Curious …;42
8.7;Exercises;42
8.8;References;43
9;Chapter 3: Counting 101;45
9.1;The Skinny on Sums;45
9.1.1;More Greek;46
9.1.2;Working with Sums;46
9.2;A Tale of Two Tournaments;47
9.2.1;Shaking Hands;47
9.2.2;The Hare and the Tortoise;49
9.3;Subsets, Permutations, and Combinations;52
9.4;Recursion and Recurrences;55
9.4.1;Doing It by Hand;55
9.4.2;A Few Important Examples;57
9.4.3;Guessing and Checking;60
9.4.4;The Master Theorem: A Cookie-Cutter Solution;62
9.5;So What Was All That About?;65
9.6;Summary;66
9.7;If You’re Curious ...;67
9.8;Exercises;67
9.9;References;68
10;Chapter 4: Induction and Recursion ... and Reduction;69
10.1;Oh, That’s Easy!;70
10.2;One, Two, Many;71
10.3;Mirror, Mirror;73
10.4;Designing with Induction (and Recursion);77
10.4.1;Finding a Maximum Permutation;78
10.4.2;The Celebrity Problem;82
10.4.3;Topological Sorting;84
10.5;Stronger Assumptions;87
10.6;Invariants and Correctness;88
10.7;Relaxation and Gradual Improvement;89
10.8;Reduction + Contraposition = Hardness Proof;90
10.9;Problem Solving Advice;91
10.10;Summary;92
10.11;If You’re Curious ...;92
10.12;Exercises;93
10.13;References;94
11;Chapter 5: Traversal: The Skeleton Key of Algorithmics;95
11.1;A Walk in the Park;101
11.1.1;No Cycles Allowed;102
11.1.2;How to Stop Walking in Circles;103
11.2;Go Deep!;104
11.2.1;Depth-First Timestamps and Topological Sorting (Again);106
11.3;Infinite Mazes and Shortest (Unweighted) Paths;108
11.4;Strongly Connected Components;111
11.5;Summary;114
11.6;If You’re Curious ...;114
11.7;Exercises;114
11.8;References;115
12;Chapter 6: Divide, Combine, and Conquer;116
12.1;Tree-Shaped Problems: All About the Balance;116
12.2;The Canonical D&C Algorithm;118
12.3;Searching by Halves;119
12.3.1;Traversing Search Trees ... with Pruning;121
12.3.2;Selection;124
12.4;Sorting by Halves;126
12.4.1;How Fast Can We Sort?;128
12.5;Three More Examples;128
12.5.1;Closest Pair;128
12.5.2;Convex Hull;130
12.5.3;Greatest Slice;131
12.6;Tree Balance ... and Balancing *;132
12.7;Summary;137
12.8;If You’re Curious ...;138
12.9;Exercises;138
12.10;References;139
13;Chapter 7: Greed Is Good? Prove It!;140
13.1;Staying Safe, Step by Step;140
13.2;The Knapsack Problem;144
13.2.1;Fractional Knapsack;144
13.2.2;Integer Knapsack;144
13.3;Huffman’s Algorithm;145
13.3.1;The Algorithm;146
13.3.2;The First Greedy Choice;148
13.3.3;Going the Rest of the Way;148
13.3.4;Optimal Merging;149
13.4;Minimum Spanning Trees;150
13.4.1;The Shortest Edge;150
13.4.2;What About the Rest?;152
13.4.3;Kruskal’s Algorithm;152
13.4.4;Prim’s Algorithm;154
13.5;Greed Works. But When?;156
13.5.1;Keeping Up with the Best;156
13.5.2;No Worse Than Perfect;158
13.5.3;Staying Safe;158
13.6;Summary;160
13.7;If You’re Curious …;161
13.8;Exercises;161
13.9;References;162
14;Chapter 8: Tangled Dependencies and Memoization;163
14.1;Don’t Repeat Yourself;164
14.2;Shortest Paths in Directed Acyclic Graphs;170
14.3;Longest Increasing Subsequence;172
14.4;Sequence Comparison;175
14.5;The Knapsack Strikes Back;178
14.6;Binary Sequence Partitioning;180
14.7;Summary;183
14.8;If You’re Curious …;183
14.9;Exercises;184
14.10;References;185
15;Chapter 9: From A to B with Edsger and Friends;186
15.1;Propagating Knowledge;187
15.2;Relaxing like Crazy;188
15.3;Finding the Hidden DAG;193
15.4;All Against All;196
15.5;Far-Fetched Subproblems;197
15.6;Meeting in the Middle;200
15.7;Knowing Where You’re Going;202
15.8;Summary;205
15.9;If You’re Curious ...;206
15.10;Exercises;206
15.11;References;207
16;Chapter 10:Matchings, Cuts, and Flows;208
16.1;Bipartite Matching;209
16.2;Disjoint Paths;211
16.3;Maximum Flow;214
16.4;Minimum Cut;217
16.5;Cheapest Flow and the Assignment Problem *;218
16.6;Some Applications;220
16.7;Summary;223
16.8;If You’re Curious …;223
16.9;Exercises;223
16.10;References;224
17;Chapter 11: Hard Problems and (Limited) Sloppiness;225
17.1;Reduction Redux;226
17.2;Not in Kansas Anymore?;228
17.3;Meanwhile, Back in Kansas …;230
17.4;But Where Do You Start? And Where Do You Go from There?;233
17.5;A Ménagerie of Monsters;237
17.5.1;Return of the Knapsack;237
17.5.2;Cliques and Colorings;238
17.5.3;Paths and Circuits;240
17.6;When the Going Gets Tough, the Smart Get Sloppy;243
17.7;Desperately Seeking Solutions;245
17.8;And the Moral of the Story Is …;247
17.9;Summary;248
17.10;If You’re Curious …;249
17.11;Exercises;249
17.12;References;250
18;Chapter 12:Pedal to the Metal: Accelerating Python;252
19;Chapter 13:List of Problems and Algorithms;256
19.1;Problems;256
19.2;Algorithms and Data Structures;259
20;Chapter 14:Graph Terminology;263
21;Chapter 15:Hints for Exercises;268
21.1;Chapter 1;268
21.2;Chapter 2;268
21.3;Chapter 3;270
21.4;Chapter 4;271
21.5;Chapter 5;273
21.6;Chapter 6;274
21.7;Chapter 7;275
21.8;Chapter 8;277
21.9;Chapter 9;278
21.10;Chapter 10;279
21.11;Chapter 11;280
22;Index;283

Über Autor(innen)

Magnus Lie Hetland is an experienced Python programmer, having used the language since the late 1990s. He is also an associate professor of algorithms at the Norwegian University of Science and Technology, having taught algorithms for the better part of a decade. Hetland is the author of Practical Python and Beginning Python, first and second editions, as well as several scientific papers.