第1页 / 共337页
第2页 / 共337页
第3页 / 共337页
第4页 / 共337页
第5页 / 共337页
第6页 / 共337页
第7页 / 共337页
第8页 / 共337页
Python Algorithms - Mastering Basic Algorithms in the Python Lan....pdf
Prelim
Contents at a Glance
Contents
About the Author
About the Technical Reviewer
Acknowledgments
Preface
Introduction
What’s All This, Then?
Why Are You Here?
Some Prerequisites
What’s in This Book
Summary
If You’re Curious …
Exercises
References
The Basics
Some Core Ideas in Computing
Asymptotic Notation
It’s Greek to Me!
Rules of the Road
Taking the Asymptotics for a Spin
Three Important Cases
Empirical Evaluation of Algorithms
Implementing Graphs and Trees
Adjacency Lists and the Like
Adjacency Matrices
Implementing Trees
A Multitude of Representations
Beware of Black Boxes
Hidden Squares
The Trouble with Floats
Summary
If You’re Curious …
Exercises
References
Counting 101
The Skinny on Sums
More Greek
Working with Sums
A Tale of Two Tournaments
Shaking Hands
The Hare and the Tortoise
Subsets, Permutations, and Combinations
Recursion and Recurrences
Doing It by Hand
A Few Important Examples
Guessing and Checking
The Master Theorem: A Cookie-Cutter Solution
So What Was All That About?
Summary
If You’re Curious …
Exercises
References
Induction and Recursion … and Reduction
Oh, That’s Easy!
One, Two, Many
Mirror, Mirror
Designing with Induction (and Recursion)
Finding a Maximum Permutation
The Celebrity Problem
Topological Sorting
Stronger Assumptions
Invariants and Correctness
Relaxation and Gradual Improvement
Reduction + Contraposition = Hardness Proof
Problem Solving Advice
Summary
If You’re Curious …
Exercises
References
Traversal: The Skeleton Key of Algorithmics
A Walk in the Park
No Cycles Allowed
How to Stop Walking in Circles
Go Deep!
Depth-First Timestamps and Topological Sorting (Again)
Infinite Mazes and Shortest (Unweighted) Paths
Strongly Connected Components
Summary
If You’re Curious …
Exercises
References
Divide, Combine, and Conquer
Tree-Shaped Problems: All About the Balance
The Canonical D&C Algorithm
Searching by Halves
Traversing Search Trees … with Pruning
Selection
Sorting by Halves
How Fast Can We Sort?
Three More Examples
Closest Pair
Convex Hull
Greatest Slice
Tree Balance … and Balancing
Summary
If You’re Curious …
Exercises
References
Greed Is Good? Prove It!
Staying Safe, Step by Step
The Knapsack Problem
Fractional Knapsack
Integer Knapsack
Huffman’s Algorithm
The Algorithm
The First Greedy Choice
Going the Rest of the Way
Optimal Merging
Minimum spanning trees
The Shortest Edge
What About the Rest?
Kruskal’s Algorithm
Prim’s Algorithm
Greed Works. But When?
Keeping Up with the Best
No Worse Than Perfect
Staying Safe
Summary
If You’re Curious …
Exercises
References
Tangled Dependencies and Memoization
Don’t Repeat Yourself
Shortest Paths in Directed Acyclic Graphs
Longest Increasing Subsequence
Sequence Comparison
The Knapsack Strikes Back
Binary Sequence Partitioning
Summary
If You’re Curious …
Exercises
References
From A to B with Edsger and Friends
Propagating Knowledge
Relaxing like Crazy
Finding the Hidden DAG
All Against All
Far-Fetched Subproblems
Meeting in the Middle
Knowing Where You’re Going
Summary
If You’re Curious …
Exercises
References
Matchings, Cuts, and Flows
Bipartite Matching
Disjoint Paths
Maximum Flow
Minimum Cut
Cheapest Flow and the Assignment Problem
Some Applications
Summary
If You’re Curious …
Exercises
References
Hard Problems and (Limited) Sloppiness
Reduction Redux
Not in Kansas Anymore?
Meanwhile, Back in Kansas …
But Where Do You Start? And Where Do You Go from There?
A ...
A Ménagerie of Monsters
Return of the Knapsack
Cliques and Colorings
Paths and Circuits
When the Going Gets Tough, the Smart Get Sloppy
Desperately Seeking Solutions
And the Moral of the Story Is …
Summary
If You’re Curious …
Exercises
References
Pedal to the Metal: Accelerating Python
List of Problems and Algorithms
Problems
Algorithms and Data Structures
Graph Terminology
Hints for Exercises
Chapter 1
Chapter 2
Chapter 3
Chapter 4
Chapter 5
Chapter 6
Chapter 7
Chapter 8
Chapter 9
Chapter 10
Chapter 11
Index
¦ ¦ ¦ ¦ Symbols and Numerics
¦ A
¦ B
¦ C
¦ D
¦ F
¦ E
¦ G
¦ I
¦ H
¦ J
¦ K
M
¦
L
¦
¦ P
¦ N
¦ O
¦ Q
¦ R
¦ S
¦ T
¦ U
¦ V
¦ W
¦ Z
CYAN
MAGENTA
YELLOW
BLACK
PANTONE 123 C
Magnus Lie Hetland,
Author of
Beginning Python: From
Novice to Professional,
Second Edition
Companion eBook
See last page for details
on $10 eBook version
SOURCE CODE ONLINE
www.apress.com
Shelve in:
Programming / Python
User level:
Intermediate – Advanced
BOOKS FOR PROFESSIONALS BY PROFESSIONALS®
THE EXPERT’S VOICE® IN OPEN SOURCE
Companion
eBook
Available
l
P
y
t
h
o
n
A
g
o
r
i
t
h
m
s
Python Algorithms: Mastering Basic
Algorithms in the Python Language
Dear Reader,
Python Algorithms 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 also gives a solid understanding
of fundamental algorithmic problem-solving techniques.
Python Algorithms deals with some of the most important and challenging
areas of programming and computer science in a highly pedagogic and read-
able manner. It covers both algorithmic theory and programming practice,
demonstrating how theory is reflected in real Python programs.
Python Algorithms explains well-known algorithms and data structures built
into the Python language, and shows you how to implement and evaluate others.
You’ll learn how to:
• Transform new problems to well-known algorithmic problems with efficient
solutions, or formally show that a solution is unfeasible.
• Analyze algorithms and Python programs both using mathematical tools and
basic experiments and benchmarks.
• Prove correctness, optimality, or bounds on approximation error for Python
programs and their underlying algorithms.
• Understand several classical algorithms and data structures in depth, and learn
to implement these efficiently in Python.
• Design and implement new algorithms for new problems, using time-tested
design principles and techniques.
Whether you’re a Python programmer who needs to learn about algorithmic prob-
lem-solving, or a student of Computer Science, this book will help you to under-
stand and implement classic algorithms, and it will help you create new ones.
THE APRESS ROADMAP
THE APRESS ROADMAP
Beginning Python,
Beginning Python,
Second Edition
Second Edition
Beginning
Beginning
Python Visualization
Python Visualization
Pro
Pro
Python
Python
Python
Python
Algorithms
Algorithms
Python
Algorithms
Mastering Basic Algorithms in the
Python Language
Learn to implement classic algorithms and design
new problem-solving algorithms using Python
ISBN 978-1-4302-3237-7
5 49 99
H
e
t
l
a
n
d
Magnus Lie Hetland
9 781430 232377
this print for content only—size & color not accurate
7.5 x 9.25 spine = 0.5" 336 page count 692 ppi
Python Algorithms
Mastering Basic Algorithms in the
Python Language
■ ■ ■
Magnus Lie Hetland
Python Algorithms: Mastering Basic Algorithms in the Python Language
Copyright © 2010 by Magnus Lie Hetland
All rights reserved. No part of this work may be reproduced or transmitted in any form or by any
means, electronic or mechanical, including photocopying, recording, or by any information
storage or retrieval system, without the prior written permission of the copyright owner and
the publisher.
ISBN-13 (pbk): 978-1-4302-3237-7
ISBN-13 (electronic): 978-1-4302-3238-4
Printed and bound in the United States of America 9 8 7 6 5 4 3 2 1
Trademarked names, logos, and images may appear in this book. Rather than use a trademark
symbol with every occurrence of a trademarked name, logo, or image we use the names, logos, and
images only in an editorial fashion and to the benefit of the trademark owner, with no intention of
infringement of the trademark.
The use in this publication of trade names, trademarks, service marks, and similar terms, even if
they are not identified as such, is not to be taken as an expression of opinion as to whether or not
they are subject to proprietary rights.
President and Publisher: Paul Manning
Lead Editor: Frank Pohlmann
Development Editor: Douglas Pundick
Technical Reviewer: Alex Martelli
Editorial Board: Steve Anglin, Mark Beckner, Ewan Buckingham, Gary Cornell,
Jonathan Gennick, Jonathan Hassell, Michelle Lowman, Matthew Moodie,
Duncan Parkes, Jeffrey Pepper, Frank Pohlmann, Douglas Pundick,
Ben Renow-Clarke, Dominic Shakeshaft, Matt Wade, Tom Welsh
Coordinating Editor: Adam Heath
Compositor: Mary Sudul
Indexer: Brenda Miller
Artist: April Milne
Cover Designer: Anna Ishchenko
Photo Credit: Kai T. Dragland
Distributed to the book trade worldwide by Springer Science+Business Media, LLC., 233 Spring
Street, 6th Floor, New York, NY 10013. Phone 1-800-SPRINGER, fax (201) 348-4505, e-mail
orders-ny@springer-sbm.com, or visit www.springeronline.com.
For information on translations, please e-mail rights@apress.com, or visit www.apress.com.
Apress and friends of ED books may be purchased in bulk for academic, corporate, or promotional
use. eBook versions and licenses are also available for most titles. For more information, reference
our Special Bulk Sales–eBook Licensing web page at www.apress.com/info/bulksales.
The information in this book is distributed on an “as is” basis, without warranty. Although every
precaution has been taken in the preparation of this work, neither the author(s) nor Apress shall
have any liability to any person or entity with respect to any loss or damage caused or alleged to be
caused directly or indirectly by the information contained in this work.
The source code for this book is available to readers at www.apress.com
For my students.
May your quest for knowledge be richly rewarded.
Contents at a Glance
■ CONTENTS
Contents...................................................................................................................vi
About the Author ...................................................................................................xiii
About the Technical Reviewer ...............................................................................xiv
Acknowledgments ..................................................................................................xv
Preface ..................................................................................................................xvi
■ Chapter 1: Introduction........................................................................................1
■ Chapter 2: The Basics ..........................................................................................9
■ Chapter 3: Counting 101 ....................................................................................45
■ Chapter 4: Induction and Recursion … and Reduction......................................71
■ Chapter 5: Traversal: The Skeleton Key of Algorithmics .................................101
■ Chapter 6: Divide, Combine, and Conquer........................................................125
■ Chapter 7: Greed Is Good? Prove It!.................................................................151
■ Chapter 8: Tangled Dependencies and Memoization .......................................175
■ Chapter 9: From A to B with Edsger and Friends.............................................199
■ Chapter 10: Matchings, Cuts, and Flows .........................................................221
■ Chapter 11: Hard Problems and (Limited) Sloppiness .....................................241
■ Appendix A: Pedal to the Metal: Accelerating Python .....................................271
■ Appendix B: List of Problems and Algorithms .................................................275
■ Appendix C: Graph Terminology.......................................................................285
■ Appendix D: Hints for Exercises.......................................................................291
■ Index ................................................................................................................307
v
■ CONTENTS
Contents
Contents at a Glance.................................................................................................v
About the Author ...................................................................................................xiii
About the Technical Reviewer ...............................................................................xiv
Acknowledgments ..................................................................................................xv
Preface ..................................................................................................................xvi
■ Chapter 1: Introduction........................................................................................1
What’s All This, Then? .....................................................................................................2
Why Are You Here? ..........................................................................................................3
Some Prerequisites .........................................................................................................4
What’s in This Book .........................................................................................................5
Summary .........................................................................................................................6
If You’re Curious … .........................................................................................................6
Exercises .........................................................................................................................7
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........................................................................................................16
Three Important Cases .........................................................................................................................19
Empirical Evaluation of Algorithms.......................................................................................................20
vi
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
