Source code online books for professionals by professionals

Document Outline

• Contents at a Glance
• Contents
• About the Author
• About the Technical Reviewer
• Acknowledgments
• Preface
• Chapter 1: Introduction
  • What’s All This, Then?
  • 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
• Chapter 12: Pedal to the Metal: Accelerating Python
• Chapter 13: List of Problems and Algorithms
  • Problems
  • Algorithms and Data Structures
• Chapter 14: Graph Terminology
• Chapter 15: 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