Algorithms
- Length: 472 pages
- Edition: 1
- Language: English
- Publisher: Independently published
- Publication Date: 2019-06-13
- ISBN-10: 1792644833
- ISBN-13: 9781792644832
- Sales Rank: #373678 (See Top 100 Books)
This textbook grew out of a collection of lecture notes that I wrote for various algorithms classes at the University of Illinois at Urbana-Champaign, which I have been teaching about once a year since January 1999. Spurred by changes of our undergraduate theory curriculum, I undertook a major revision of my notes in 2016; this book consists of a subset of my revised notes on the most fundamental course material, mostly reflecting the algorithmic content of our new required junior-level theory course.
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 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
Donate to keep this site alive
To access the Link, solve the captcha.
1. Disable the AdBlock plugin. Otherwise, you may not get any links.
2. Solve the CAPTCHA.
3. Click download link.
4. Lead to download server to download.