Algorithms

Free

Description

Contents

Reviews

Language

English

ISBN

978-1-792-64483-2

Preface

About This Book

Prerequisites

Additional References

About the Exercises

Steal This Book!

Acknowledgments

Caveat Lector!

Table of Contents

Introduction

What is an algorithm?

Multiplication

Lattice Multiplication

Duplation and Mediation

Compass and Straightedge

Congressional Apportionment

A Bad Example

Describing Algorithms

Specifying the Problem

Describing the Algorithm

Analyzing Algorithms

Correctness

Running Time

Exercises

Recursion

Reductions

Simplify and Delegate

Tower of Hanoi

Mergesort

Correctness

Analysis

Quicksort

Correctness

Analysis

The Pattern

Recursion Trees

♥Ignoring Floors and Ceilings Is Okay, Honest

♥Linear-Time Selection

Quickselect

Good pivots

Analysis

Sanity Checking

Fast Multiplication

Exponentiation

Exercises

Backtracking

N Queens

Game Trees

Subset Sum

Correctness

Analysis

Variants

The General Pattern

Text Segmentation (Interpunctio Verborum)

Index Formulation

♥Analysis

Variants

Longest Increasing Subsequence

Longest Increasing Subsequence, Take 2

Optimal Binary Search Trees

♥Analysis

Exercises

Dynamic Programming

Mātrāvṛtta

Backtracking Can Be Slow

Memo(r)ization: Remember Everything

Dynamic Programming: Fill Deliberately

Don't Remember Everything After All

♥Aside: Even Faster Fibonacci Numbers

Whoa! Not so fast!

Interpunctio Verborum Redux

The Pattern: Smart Recursion

Warning: Greed is Stupid

Longest Increasing Subsequence

First Recurrence: Is This Next?

Second Recurrence: What's Next?

Edit Distance

Recursive Structure

Recurrence

Dynamic Programming

Subset Sum

Optimal Binary Search Trees

Dynamic Programming on Trees

Exercises

Greedy Algorithms

Storing Files on Tape

Scheduling Classes

General Pattern

Huffman Codes

Stable Matching

Some Bad Ideas

The Boston Pool and Gale-Shapley Algorithms

Running Time

Correctness

Optimality!

Exercises

Basic Graph Algorithms

Introduction and History

Basic Definitions

Representations and Examples

Data Structures

Adjacency Lists

Adjacency Matrices

Comparison

Whatever-First Search

Analysis

Important Variants

Stack: Depth-First

Queue: Breadth-First

Priority Queue: Best-First

Disconnected Graphs

Directed Graphs

Graph Reductions: Flood Fill

Exercises

Depth-First Search

Preorder and Postorder

Classifying Vertices and Edges

Detecting Cycles

Topological Sort

Implicit Topological Sort

Memoization and Dynamic Programming

Dynamic Programming in Dags

Strong Connectivity

Strong Components in Linear Time

Kosaraju and Sharir’s Algorithm

♥Tarjan’s Algorithm

Exercises

Minimum Spanning Trees

Distinct Edge Weights

The Only Minimum Spanning Tree Algorithm

Borůvka’s Algorithm

This is the MST Algorithm You Want

Jarník’s (“Prim’s”) Algorithm

♥Improving Jarník’s Algorithm

Kruskal’s Algorithm

Exercises

Shortest Paths

Shortest Path Trees

♥Negative Edges

The Only SSSP Algorithm

Unweighted Graphs: Breadth-First Search

Directed Acyclic Graphs: Depth-First Search

Best-First: Dijkstra’s Algorithm

No Negative Edges

♥Negative Edges

Relax ALL the Edges: Bellman-Ford

Moore’s Improvement

Dynamic Programming Formulation

Exercises

All-Pairs Shortest Paths

Introduction

Lots of Single Sources

Reweighting

Johnson's Algorithm

Dynamic Programming

Divide and Conquer

Funny Matrix Multiplication

(Kleene-Roy-)Floyd-Warshall(-Ingerman)

Exercises

Maximum Flows & Minimum Cuts

Flows

Cuts

The Maxflow-Mincut Theorem

Ford and Fulkerson's augmenting-path algorithm

♥Irrational Capacities

Combining and Decomposing Flows

Edmonds and Karp's Algorithms

Fattest Augmenting Paths

Shortest Augmenting Paths

Further Progress

Exercises

Applications of Flows and Cuts

Edge-Disjoint Paths

Vertex Capacities and Vertex-Disjoint Paths

Bipartite Matching

Tuple Selection

Exam Scheduling

Disjoint-Path Covers

Minimal Faculty Hiring

Baseball Elimination

Project Selection

Exercises

NP-Hardness

A Game You Can't Win

P versus NP

NP-hard, NP-easy, and NP-complete

♥Formal Definitions (HC SVNT DRACONES)

Reductions and Sat

3Sat (from CircuitSat)

Maximum Independent Set (from 3Sat)

The General Pattern

Clique and Vertex Cover (from Independent Set)

Graph Coloring (from 3Sat)

Hamiltonian Cycle

From Vertex Cover

From 3Sat

Variants and Extensions

Subset Sum (from Vertex Cover)

Caveat Reductor!

Other Useful NP-hard Problems

Choosing the Right Problem

A Frivolous Real-World Example

♥On Beyond Zebra

Polynomial Space

Exponential Time

Excelsior!

Exercises

Index

Index of People

Index of Pseudocode

Image Credits

Colophon

The book hasn't received reviews yet.