Algorithms illuminated Part 3 Greedy Algorithms and Dynamic Programming

Description

Contents......Page 3 Preface......Page 5 Greedy Algorithm Design Paradigm......Page 10 Scheduling Problem......Page 13 Developing Greedy Algorithm......Page 15 Proof of Correctness......Page 21 Codes......Page 32 Codes as Trees......Page 37 Huffman Greedy Algorithm......Page 41 Proof of Correctness......Page 50 Problem Definition......Page 61 Prim Algorithm......Page 66 Speeding up Prim Algorithm via Heaps......Page 71 Prim Algorithm - Proof of Correctness......Page 78 Kruskal Algorithm......Page 85 Speeding up Kruskal Algorithm via Union-Find......Page 90 Kruskal Algorithm - Proof of Correctness......Page 100 Application - Single-Link Clustering......Page 103 Intro to Dynamic Programming......Page 112 Weighted Independent Set Problem......Page 113 Linear-Time Algorithm for WIS in Paths......Page 117 Reconstruction Algorithm......Page 125 Principles of Dynamic Programming......Page 127 Knapsack Problem......Page 132 Sequence Alignment......Page 146 Optimal Binary Search Trees......Page 157 Shortest Paths with Negative Edge Lengths......Page 176 Bellman-Ford Algorithm......Page 181 All-Pairs Shortest Path Problem......Page 194 Floyd-Warshall Algorithm......Page 196 Epilogue - Field Guide to Algorithm Design......Page 210 Hints & Solutions......Page 212 Index......Page 220