Algorithms are the heart and soul of computer science. Their applications range from network routing and computational genomics to public-key cryptography and machine learning. Studying algorithms can make you a better programmer, a clearer thinker, and a master of technical interviews. Algorithms Illuminated is an accessible introduction to the subject for anyone with at least a little programming experience. The exposition emphasizes the big picture and conceptual understanding over low-level implementation and mathematical details---like a transcript of what an expert algorithms tutor would say over a series of one-on-one lessons. Part 2 covers graph search and applications, shortest paths, and the usage and implementation of several data structures (heaps, search trees, hash tables, and bloom filters). Contents......Page 3 Preface......Page 5 Some Vocabulary......Page 10 Few Applications......Page 11 Measuring the Size of Graph......Page 12 Representing a Graph......Page 16 Problems......Page 22 Overview......Page 24 Breadth-first Search & Shortest Paths......Page 34 Computing Connected Components......Page 43 Depth-first Search......Page 49 Topological Sort......Page 54 Computing Strongly Connected Components......Page 63 Structure of the Web......Page 75 Problems......Page 80 Single-Source Shortest Path Problem......Page 85 Dijkstra Algorithm......Page 89 Why is Dijkstra Algorithm correct......Page 92 Implementation & Running Time......Page 98 Problems......Page 100 Data Structures Overview......Page 104 Supported Operations......Page 107 Applications......Page 110 Speeding up Dijkstra Algorithm......Page 115 Implementation Details......Page 121 Problems......Page 132 Sorted Arrays......Page 135 Search Trees Supported Operations......Page 138 Implementation Details......Page 140 Balanced Search Trees......Page 154 Problems......Page 158 Supported Operations......Page 160 Applications......Page 163 Implementation - High-Level Ideas......Page 168 Further Implementation Details......Page 182 Bloom Filters Basics......Page 187 Bloom Filters Heuristic Analysis......Page 193 Problems......Page 199 The Gist......Page 202 Big-O Notation......Page 203 Examples......Page 204 Big-Omega & Big-Theta Notation......Page 206 Solutions......Page 209 Index......Page 212 Accessible, no-nonsense, and programming language-agnostic introduction to algorithms. Includes solutions to all quizzes and selected problems, and a series of YouTube videos by the author accompanies the book. Part 2 covers graph search and its applications, shortest-path algorithms, and the applications and implementation of several data heaps, search trees, hash tables, and bloom filters. (Part 1 is not a prerequisite.)
