Log In
Or create an account ->
Imperial Library
Home
About
News
Upload
Forum
Help
Login/SignUp
Index
Cover
Title
Copyright
Dedication
Contents at a Glance
Contents
About the Author
About the Technical Reviewer
Acknowledgments
Preface
Chapter 1: Introduction
What’s All This, Then?
What the book is about:
What the book covers only briefly or partially:
What the book isn’t about:
Why Are You Here?
Some Prerequisites
What’s in This Book
Summary
If You’re Curious …
Exercises
References
Chapter 2: 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
Chapter 3: 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
Chapter 4: 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
Chapter 5: 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
Chapter 6: 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
Chapter 7: 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
Chapter 8: 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
Chapter 9: 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
Chapter 10: 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
Chapter 11: 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 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
Appendix A: Pedal to the Metal: Accelerating Python
Appendix B: List of Problems and Algorithms
Problems
Algorithms and Data Structures
Appendix C: Graph Terminology
Appendix D: 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
← Prev
Back
Next →
← Prev
Back
Next →