Table of Contents for
Python Algorithms: Mastering Basic Algorithms in the Python Language, Second Edition

Version ebook / Retour

Cover image for bash Cookbook, 2nd Edition Python Algorithms: Mastering Basic Algorithms in the Python Language, Second Edition by Magnus Lie Hetland Published by Apress, 2015
  1. Cover
  2. Title
  3. Copyright
  4. Dedication
  5. Contents at a Glance
  6. Contents
  7. About the Author
  8. About the Technical Reviewer
  9. Acknowledgments
  10. Preface
  11. Chapter 1: Introduction
  12. Chapter 2: The Basics
  13. Chapter 3: Counting 101
  14. Chapter 4: Induction and Recursion … and Reduction
  15. Chapter 5: Traversal: The Skeleton Key of Algorithmics
  16. Chapter 6: Divide, Combine, and Conquer
  17. Chapter 7: Greed Is Good? Prove It!
  18. Chapter 8: Tangled Dependencies and Memoization
  19. Chapter 9: From A to B with Edsger and Friends
  20. Chapter 10: Matchings, Cuts, and Flows
  21. Chapter 11: Hard Problems and (Limited) Sloppiness
  22. Appendix A: Pedal to the Metal: Accelerating Python
  23. Appendix B: List of Problems and Algorithms
  24. Appendix C: Graph Terminology
  25. Appendix D: Hints for Exercises
  26. Index

Index

images  A

A* algorithm

AA-trees algorithms

Acceleration Tool Web Sites

Acyclic graphs

Algorithms

black boxes

book

graphs

adjacency lists

adjacency matrix

friends attribute

nutshell

mathematical sense

problem instances

random-access machine

trees

binary

multiway

rooted

turing machine

Alpha-beta pruning

Annihilators

Approximation algorithm

Arithmetic series

Assignment problem

Associativity

Asymptotic notation

algorithms

constant factors

mylist.sort( )

Python Call Graph

running times

statistical solutions

timeit module

trace module

average case

best case

black box

built-in functions

expressions

Greek letters

if statements

iteration counts

math refresher

factorial

fractional powers

logarithms

polynomial

Math Refresher

multiplying objects

Python lists

recurrences and

running times

sequential and nested cases

sort_w_check

sum function

worst case

images  B

Balanced tree structure

Balance factors

Baseball elimination problem

Bellman–Ford algorithm

Binary counting

Binary encoding

Binary search trees

Binary trees

knockout tournaments and

properties of, summarized

Binomial coefficient

Bin packing problem

Bipartite matching problems

applications of

augmenting path

canceling

definition

Gale-Shapley algorithm

graphs

iterative improvement

stable marriage problem

tr function

zigzagging/cycle path

Bisection search tree

Black boxes

floating-point numbers

hidden performance traps

redundancy

Bogosort algorithm

Boolean satisfiability (SAT)

Boost.Python tool

Branch-and-bound (B&B) technique

Breadth-first search (BFS) algorithm

A* algorithm

Dijkstra’s algorithm

double-ended queue

first-in first-out queue

Bucket sort algorithm

Bunch pattern

Busacker–Gowen algorithm

images  C

Celebrity problem

brute-force solution

naive_celeb function

solution

sparse graph

Cheapest augmenting path

Cheapest maximum flow

Choosing representatives problem

Christofides algorithm

Cinpy package

Circuit-SAT problem

Clique cover problem

Clique graph

Closest pair problems

Collections.Counter

Combinations

Combinatorial problems

Complexity

Compression

Conjunctive normal form (CNF)

Consistent matrix rounding

Convex hulls

Cook–Levin theorem

CorePy module

Cost scaling algorithm (CSA)

Counting sort algorithm

Ctypes module

Cython

images  D

Deadlocks

Depth-first search (DFS)

directed graphs

iterative

preorder/postorder processing

queue

with timestamps

topological sorting

topological sorting with

Digraphs

Dijkstra’s algorithm

Dinic’s algorithm

Directed acyclic graphs (DAGs)

Discrete mathematics

Disjoint paths

augmenting path, s-t network

canceling

edge connectivity

Menger’s theorem

rules

source and sink

statements

vertex-disjoint

distributivity

Divide-and-conquer (D&C) algorithms

balance

balanced decomposition

balancing methods

AA-tree

binary tree

node rotations

node splitting

node types

pseudonode

binary search

binary trees

Binary heaps

insertion

linear scan

mapping

tree property

convex hulls

dicts

hashing

heapq module

implementation of

loglinear

merge sort

priority queue

processors

puzzle-solving

RCS

recurrences

recursive calls

selection algorithm

heap

linear time

pivot

skyline problem

slicing

sorted arrays

sorting

heapsort

merge sort

quicksort

stirling’s approximation

Timsort

unbalanced decomposition

Doctors on vacation problem

Double-ended queues

Dynamic arrays

Dynamic programming (DP)

binary sequence partitioning

expected optimal search cost

matrix chain multiplication

optimal search tree problem

parsing arbitrary context free languages

recursive relationships

split points

binomial coefficient calculation

brute-force solution

caching

DAG shortest path algorithm

iterative version

linear-time algorithm

reaching

recursive version

sequential decision process

DRY principle

Fibonacci numbers

knapsack problem

bounded and unbounded versions

iterative solution

iterative version

memoization

pseudopolynomial

LCS problem

code

comparing sequences

iterative solution

memoized implementation

longest increasing subsequence

direct recursive implementation

iterative solution

recursive decomposition and induction

@memo decorator

memoization

memoizing decorator

overlapping subproblems

Pascal’s triangle

path counting

recursion trees

recursive decomposition

sequence comparison

tangled dependencies

images  E

Edge cover problem

Edge-disjoint paths

Edmonds–Karp algorithm

Element uniqueness

Euler tours (Euler circuits)

Exponential series

images  F

F2PY tool

Flow problems

applications of

circulations

and cut problems

Floyd–Warshall algorithm

Ford–Fulkerson method

For loop

Functions

images  G

Gale–Shapley algorithm

Gauss, Carl Friedrich

Geometric series

Gnomesort algorithm

Gnomesort function

GPULib package

Graphs

coloring

friends attribute

libraries

Graphine

Graph-tool

NetworkX

python-graph

nutshell

representations

adjacency lists

adjacency matrix

subproblem graph

Graph’s nodes

Graph terminology

acyclic graphs

antiparallel edges

cycle path

DAG

definition

neighbors edges

path

rooted tree

spanning tree

supergraph

trees

types of

underlying undirected graph

Graph Theory

Greedy algorithms

compatible intervals

exchange argument

filling the puzzle

knapsack problem

making change problem

matching problem

optimal schedule

optimization problem

partial schedule

partial solution

proof by cases

resource scheduling

solution pieces

solution without gaps/inversions

stable marriage problem

subset sum problem

time intervals

two-part approach

images  H

Halting problem

Hamilton cycle problem

Handshake problems

Handshake recurrence

Hard problems

NPC (see NP-complete problems (NPC))

NTM

in polynomial time

P vs. NP

reduction

binoculars

Castor and Pollux

complexity classes

nodes represent problems

zip line

Hashing

Hash tables

Heapsort algorithm

Huffman’s algorithm

compression application

greedy choice property

heap

implementation

optimal merging

optimal substructure

text compress and decompress

uniform probability

weighted balancing

images  I

Icosian game

Independent set problem

Induction

balance factors

checkerboard puzzle

correctness proofs

handshake formula

inductive hypothesis

inductive step

loop invariants

relaxation

reverse induction

Insertion sort algorithm

Integers programming

Interpolation search algorithm

Iteration method

Iterative deepening depth-first search (IDDFS)

images  J

Johnson’s algorithm

Just-in-time (JIT) compiler

images  K

Kaliningrad

k-CNF-SAT

k-coloring

Knapsack algorithm

Knapsack problem

bin packing

integer programming

linear programming

partition

subset sum problem

knockout tournaments

König’s theorem

Kosaraju’s algorithm

Kruskal’s algorithm

images  L

Label function

linear running time

Linked lists arrays

llvm-py package

logarithmic algorithms

Longest increasing subsequence (LIS) problem

Longest-path problem

Lower bounds

images  M

Master theorem

Matching problems

Math module

Max-flow problem

Maximum flow

augmenting path, network

BFS

bfs_aug function

canceling

capacity

disjoint path rules

Edmonds-Karp algorithm

Ford-Fulkerson method

labeling

size/magnitude

Maximum protection

induction

assumptions

matching problem

permutation

recursion

counting sort algorithm

first-in, first-out queue

maive_max_perm function

recursive algorithm

reference counting

Maximum tension problems

Menger’s theorem

Merge sort algorithm

Mergesort function

Metaheuristics

Metrics

Minimum-cost flow problem

Minimum cut problem

applications of

duality

GPU processors

statements

Minimum spanning tree problem

Euclidean graph

Kruskal’s algorithm

find and union implementation

naïve Kruskal implementation

path compression

representative

Prim’s algorithm

breadth-first search

heapq library

priority-based traversals

priority queue

Multicommodity flow problem

Multiplicative constants

images  N

Nondeterministically polynomial (NP)

Nondeterministic Turing machine (NTM)

NP-complete problems (NPC)

Boolean expression

clause node encoding

clique cover

CNF

colorings

Cook-Levin theorem

Hamilton cycle problem

knapsack (see Knapsack problem)

NP-hard

NTM

paths and circuits

polynomial time reduction

SAT problem

transive reductions and

TSP

variable

NP-hard problem

Numba

NumPy library

NumPy package

images  O

Optimal decision trees

Ore’s algorithm

images  P

Partition problem

Perfect matching

Permutations

Polynomial (P)

Predecessor pointer

Prerequisites

Primality checking

Prim’s algorithm

Problems

clique graph

closest pair

compression

convex hull

graph coloring

independent set

optimal decision trees

sequence comparison

Problem solving advices

Pruning

Pseudopolynomials

Psyco

PyInline package

PyPy

Pyrex

PyStream package

Python

Call Graph

multiprocessing module

optimization tools

images  Q

Quadratic running time

images  R

Radix sort algorithm

Randomized select algorithm

Recurrences

basic, list of

checking

divide-and-conquer

relations

unraveling

Recursion

checkerboard covering problem

depth-first search

insertion sort

selection sort

tail recursion optimization

trees

working principle

Recursive algorithms

Reduction

contraposition

variations

working principle

Reference counting

Residual networks

Revision control systems (RCSs)

Root node

Round-robin tournaments

RPython

images  S

Sage tool

Satisfaction problem (SAT)

SciPy package

Searching problem

Selection algorithm

Selection sort

Sequence comparison

Sequence modification

Set covering problem

Shedskin

Shortest path problem

A* algorithm

BFS

implicit graph

potential function

Rubik’s Cube

Bellman-Ford algorithm

changed check

edges

logging packages

negative cycle

relax function

weighted graph

DAG

Dijkstra’s algorithm

BFS

bidirectional version

dummy nodes

hidden DAG

nagging doubt

traversal function

  vs. Prim’s algorithm

Floyd-Warshall algorithm

distance

memory recursive

heuristic algorithm

Johnson’s algorithm

relax function

shortcut

triangle inequality

Shortest-path problems

Sigma (∑)

Sloppiness

approximation algorithm

Hamilton cycle problem

minimum spanning tree

TSP problem

Sorting algorithms

Spanning tree

Square root

Strong induction

Strongly connected components (SCCs)

dfs_topsort function

directed graph

Kosaraju’s algorithm

latest finish time

Subsets

Subset sum problem

Supergraph

Supply and demand problem

SWIG tool

images  T

Tail recursion optimization

Timsort algorithm

Tools

Sage

Wolfram Alpha computational knowledge engine

Topological sorting

counting-based

DAG

Naïve algorithm

Python’s MRO

tsort command

Traveling Salesman Problem (TSP)

Traversals problem

best-first search

branch and bound approach

breadth-first search

circular buffers

connected components

adjacency sets

walk function

depth-first search

dodecahedron

dungeon map

edge types

flood fill

fringe/frontier nodes

goal-directed

IDDFS

infinite mazes

keep turning left strategy

backtracking

recursive tree-traversal

Tremaux’s algorithm

Königsberg bridge

node coloring

predecessors

pruning

shortest paths

tree

Traversal tree

Trees

binary tree

multiway tree

rooted trees

Trémaux’s algorithm

tr function

Twice around the tree algorithm

Two-dimensional adjacency array

images  U

Unladen Swallow

images  V

Variable changes

Variable substitution

Vertex cover

Vertex-disjoint paths

images  W, X, Y, Z

Weak induction

Weave package

Wheat and chessboard problems

While loop

Wolfram Alpha computational knowledge engine