About the book

Ever wonder how Google finds your perfect search result in milliseconds? Or how your GPS maps the fastest route to your destination? It's all thanks to the clever search algorithms invented by great software engineers who needed to solve some complex search problems.

Search algorithms are everywhere! From finding your friend's profile on Facebook to suggesting the best route on a map, these algorithms are constantly sifting through mountains of data, searching for what you're looking for. Search is at the core of all these real-world technology problems.

This book is your guide to essential search methods used across different fields. I've carefully curated these algorithms from a vast collection, selecting those that form the building blocks. Understanding and applying these algorithms will provide you with the necessary baseline to explore more complex ones. Plus, you might even be able to create your own algorithm tailored to the problem you're solving. Each section explains the ideas clearly and includes Python code you can use in your projects. All the code is free and available on my GitHub page under the MIT license.

By the end, you'll have the skills to explore both simple and complex decision-making. Whether it's managing supply chains or designing smart robots, these essential search methods will guide you through tough challenges and help you discover solutions you didn't know were there.

Chapters

17Introduction

Book Organization • Code Samples • Setting up the python enviroment • Online resources

20Time Complexity of Algorithms

Big O Notation • Common Notations • Calculating Time complexity • Demystifying Logarithmic Time complexity • Common Time Complexities • NP and P • Bibliography

Part I - Basic Search Algorithms

30Linear search

How it works • Implementation • Time Complexity Analysis • Advantages • Limitations • Applications • Bibliography

35Binary search

How it works • Implementation • Time Complexity Analysis • Advantages • Limitations • Applications • Bibliography

39Ternary search

How it works • Implementation • Time Complexity Analysis • Applications • Bibliography

44Jump search

How it works • Implementation • Time Complexity Analysis • Advantages • Limitations • Applications • Bibliography

48Indexed Sequential Search

How it works • Implementation • Time Complexity Analysis • Advantages • Limitations • Applications • Bibliography

54Interpolation Search

How it works • Implementation • Time Complexity Analysis • Advantages • Limitations • Applications • Bibliography

60Exponential Search

How it works • Implementation • Time Complexity Analysis • Advantages • Limitations • Applications • Bibliography

66Fibonacci Search

How it works • Implementation • Time Complexity Analysis • Advantages • Limitations • Applications • Bibliography

Part II - Hash Based Search

74Basics

Hash table • How Hashing Works • Types of Hash Functions • Hash Collisions • Bibliography

82Hash Table Search

How it works • Implementation • Time Complexity Analysis • Advantages • Limitations • Applications • Bibliography

87Bloom Filter

How it works • Implementation • Time Complexity Analysis • Advantages • Limitations • Applications • Bibliography

96Cuckoo Filter

Cuckoo hashing • Cuckoo Filter implementation • Time complexity Analysis • Cuckoo filters vs Bloom Filters • Advantages • Limitations • Bibliography

Part III - AI Search Algorithms

111Hill Climbing Algorithm

How it works • Implementation • Variants of Hill Climbing Algorithm • Advantages • Disadvantages • Applications • Bibliography

120Monte Carlo Tree Search (MCTS)

Playing Tic-Tac-Toe with Monte Carlo Tree Search • Implementation • Visualization • Advantages • Limitations • Applications • Bibliography

135Simulated Annealing

How it works • The Traveling Salesman Problem (TSP) using Simulated • Annealing • Simulated Annealing for TSP Problem Step-by-Step Guide • Implementation • Visualization • Advantages • Limitations • Applications • Bibliography

150Tabu search

Basic principle • Components of TS • How it works • Implementation • Visualization • Advantages • Limitations • Applications • Bibliography

167Branch and Bound Algorithms

Branch and Bound algorithm • How it works • Implementation • Advantages • Limitations • Applications • Bibliography

184Beam search

How it works • Implementation • Visualization • Time Complexity Analysis • Advantages • Limitations • Applications • Bibliography

196Iterative Deepening Depth-First Search (IDDFS)

How it works • Implementation • Time Complexity Analysis • Advantages • Limitations • Applications • Bibliography

204Ant Colony Optimization (ACO)

Explanation of Ant Colony Optimization • Implementation • Visualization • Advantages • Limitations • Applications • Bibliography

216Nearest Neighbor Search

Formal Definition • Approaches to Nearest Neighbor Search • Curse of Dimensionality • Time complexity analysis • Advantages • Limitations • Applications • Bibliography

Part IV - Graph Search Algorithms

233Basics

Graph Data structure • Common Implementations • Types of Graph-based algorithms • Search Strategies Uninformed and Informed Search • Bibliography

241Depth First Search (DFS)

How it Works • Implementation • Time Complexity Analysis • Advantages • Limitations • Choosing between DFS and BFS • Applications • Bibliography

251Breadth first search (BFS)

How it works • Implementation • Visualization • Time Complexity Analysis • Breadth-First Search vs. Depth-First Search • Advantages • Limitations • Applications • Bibliography

263Dijkstra’s algorithm

A brief history • How it Works • Implementation • Visualization • Time Complexity Analysis • Advantages • Limitations • Applications • Bibliography

282Uniform Cost Search

How it Works • Implementation • Visualization • Time Complexity Analysis • Advantages • Disadvantages • Applications • Bibliography

294Greedy Best-First Search

How it works • Implementation • Visualization • Time Complexity Analysis • Advantages • Limitations • Applications • Bibliography

304A* Search Algorithm

Heuristics and Cost function • How it works • Implementation • Visualization • Time Complexity Analysis • Advantages • Limitations • Applications • Bibliography

316B* Search Algorithm

How it works • Implementation • Bibliography

321Bidirectional Search

How it Works • Implementation • Time Complexity Analysis • Advantages • Limitations • Applications • Bibliography

328Kruskal’s Algorithm

Minimal Spanning Tree • Disjoint Set Data structure • The Kruskal Algorithm • Implementation • Visualization • Time complexity analysis • Advantages • Limitations • Algorithms •Bibliography

339Prim’s Algorithm

How it works • Implementation • Visualization • Time Complexity Analysis • Advantages • Limitations • Applications • Bibliography

347Floyd-Warshall algorithm

How it works • Implementation • Time Complexity Analysis • Applications • Bibliography

355The Bellman-Ford algorithm

How it works • Implementation • Time Complexity Analysis • Applications • Bibliography

Part V - Text and String Matching Algorithms

364Suffix Array

How it works • Implementation • Visualization • Time complexity • Advantages • Limitations • Applications • Bibliography

373Boyer-Moore Algorithm

How it works • Implementation • Visualization • Advantages • Limitations • Applications • Bibliography

385Knuth-Morris-Pratt (KMP) Algorithm

How it works • Implementation • Visualization • Time Complexity Analysis • Advantages • Limitations • Applications • Bibliography

396Rabin-Karp Algorithm

How it works • Implementation • Visualization • Time complexity • Advantages • Limitations • Bibliography

405Levenshtein distance

Calculating Levenshtein Distance • Representation of Levenshtein Distance • Implementation • Visualization • How is LD used in search? • Program for approximate string matching using levenshtein distance • Advantages • Limitations • Applications • Bibliography

Part VI - Data Structures for Search

416Arrays

Arrays in Python • Types of Arrays • Applications

421Linked Lists

Implementing a linked list in Python • Operations on linked lists • Advantages of linked lists • Disadvantages

423Queues

Working with Queues • Applications

426Heaps

Types of heaps • Working with Heap • Heaps vs. arrays • Applications

429Stack

Working with Stack • Applications

432Trie search

How it works • Implementation • Time Complexity Analysis • Advantages • Limitations • Applications

442Ternary Search Tree (TST)

Structure and Representation of Ternary Search Tree • Operations on Ternary Search Tree • Implementation • Visualization • How is a TST more space efficient than Trie? • Bibliography

Part VII - Appendix

455Python: Quick-Start Guide

Overview • Language Basics • Further Reading

468Acknowledgements

About the author

Muthukrishnan has over 15 years of hands-on expertise in crafting complex software solutions, in areas of artificial intelligence, computer vision, algorithms, data structures, and a variety of programming languages. He holds multiple patents and has worked in various startups throughout his career, including one he built himself, offering valuable exposure to the startup world. Presently, he holds a technical leadership position as an engineering manager, overseeing a team of software engineers developing intricate software systems intended for use by millions worldwide.