Learning Algorithms by Heineman, George T. -- Read -- Imperial Library of Trantor

Index

Foreword Preface

Who This Book Is For About the Code Conventions Used in This Book O’Reilly Online Learning How to Contact Us Acknowledgments

1. Problem Solving

What Is an Algorithm? Finding the Largest Value in an Arbitrary List Counting Key Operations Models Can Predict Algorithm Performance Find Two Largest Values in an Arbitrary List Tournament Algorithm Time Complexity and Space Complexity Summary Challenge Exercises

2. Analyzing Algorithms

Using Empirical Models to Predict Performance Multiplication Can Be Faster Performance Classes Asymptotic Analysis Counting All Operations Counting All Bytes When One Door Closes, Another One Opens Binary Array Search Almost as Easy as π Two Birds with One Stone Pulling It All Together Curve Fitting Versus Lower and Upper Bounds Summary Challenge Exercises

3. Better Living Through Better Hashing

Associating Values with Keys Hash Functions and Hash Codes A Hashtable Structure for (Key, Value) Pairs Detecting and Resolving Collisions with Linear Probing Separate Chaining with Linked Lists Removing an Entry from a Linked List Evaluation Growing Hashtables Analyzing the Performance of Dynamic Hashtables Perfect Hashing Iterate Over (key, value) Pairs Summary Challenge Exercises

4. Heaping It On

Max Binary Heaps Inserting a (value, priority) Removing the Value with Highest Priority Representing a Binary Heap in an Array Implementation of Swim and Sink Summary Challenge Exercises

5. Sorting Without a Hat

Sorting by Swapping Selection Sort Anatomy of a Quadratic Sorting Algorithm Analyze Performance of Insertion Sort and Selection Sort Recursion and Divide and Conquer Merge Sort Quicksort Heap Sort Performance Comparison of O(N log N) Algorithms Tim Sort Summary Challenge Exercises

6. Binary Trees: Infinity in the Palm of Your Hand

Getting Started Binary Search Trees Searching for Values in a Binary Search Tree Removing Values from a Binary Search Tree Traversing a Binary Tree Analyzing Performance of Binary Search Trees Self-Balancing Binary Trees Analyzing Performance of Self-Balancing Trees Using Binary Tree as (key, value) Symbol Table Using the Binary Tree as a Priority Queue Summary Challenge Exercises

7. Graphs: Only Connect!

Graphs Efficiently Store Useful Information Using Depth First Search to Solve a Maze Breadth First Search Offers Different Searching Strategy Directed Graphs Graphs with Edge Weights Dijkstra’s Algorithm All-Pairs Shortest Path Floyd–Warshall Algorithm Summary Challenge Exercises

8. Wrapping It Up

Python Built-in Data Types Implementing Stack in Python Implementing Queues in Python Heap and Priority Queue Implementations Future Exploration

Index