Algorithms Illuminated (Part 2): Graph Algorithms and Data Structures

✍ Scribed by Tim Roughgarden

• Publisher: Soundlikeyourself Publishing, LLC
• Year: 2018
• Tongue: English
• Leaves: 222
• Category: Library

✦ Synopsis

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).

✦ Table of Contents

Preface
Graphs: The Basics
Some Vocabulary
A Few Applications
Measuring the Size of a Graph
Representing a Graph
Problems
Graph Search and Its Applications
Overview
Breadth-First Search and Shortest Paths
Computing Connected Components
Depth-First Search
Topological Sort
Computing Strongly Connected Components
The Structure of the Web
Problems
Dijkstra's Shortest-Path Algorithm
The Single-Source Shortest Path Problem
Dijkstra's Algorithm
Why Is Dijkstra's Algorithm Correct?
Implementation and Running Time
Problems
The Heap Data Structure
Data Structures: An Overview
Supported Operations
Applications
Speeding Up Dijkstra's Algorithm
Implementation Details
Problems
Search Trees
Sorted Arrays
Search Trees: Supported Operations
Implementation Details
Balanced Search Trees
Problems
Hash Tables and Bloom Filters
Supported Operations
Applications
Implementation: High-Level Ideas
Further Implementation Details
Bloom Filters: The Basics
Bloom Filters: Heuristic Analysis
Problems
Quick Review of Asymptotic Notation
The Gist
Big-O Notation
Examples
Big-Omega and Big-Theta Notation
Solutions to Selected Problems
Index