You are previewing Beginning Algorithms.
O'Reilly logo
Beginning Algorithms

Book Description

Beginning Algorithms

A good understanding of algorithms, and the knowledge of when to apply them, is crucial to producing software that not only works correctly, but also performs efficiently. This is the only book to impart all this essential information-from the basics of algorithms, data structures, and performance characteristics to the specific algorithms used in development and programming tasks.

Packed with detailed explanations and instructive examples, the book begins by offering you some fundamental data structures and then goes on to explain various sorting algorithms. You'll then learn efficient practices for storing and searching by way of hashing, trees, sets, and maps. The authors also share tips on optimization techniques and ways to avoid common performance pitfalls. In the end, you'll be prepared to build the algorithms and data structures most commonly encountered in day-to-day software development.

What you will learn from this book

  • The basics of algorithms, such as iteration and recursion

  • Elementary data structures such as lists, stacks, and queues

  • Basic and advanced sorting algorithms including insertion sort, quicksort, and shell sort

  • Advanced data structures such as binary trees, ternary trees, and heaps

  • Algorithms for string searching, string matching, hashing, and computational geometry

  • How to use test-driven development techniques to ensure your code works as intended

  • How to dramatically improve the performance of your code with hands-on techniques for profiling and optimization

Who this book is for

This book is for anyone who develops applications, or is just beginning to do so, and is looking to understand algorithms and data structures. An understanding of computer programming is beneficial.

Wrox Beginning guides are crafted to make learning programming languages and technologies easier than you think, providing a structured, tutorial format that will guide you through all the techniques involved.

Examples link provided by the publisher.Errata link provided by the publisher.

Table of Contents

  1. Copyright
  2. Credits
  3. About the Authors
  4. Acknowledgments
  5. Introduction
    1. Who Should Read This Book
    2. Prerequisite Knowledge
    3. What You Will Learn
    4. How to Use This Book
    5. Principles of the Approach
      1. Keep It Simple
      2. Don't Pre-optimize
      3. Use Interfaces
      4. Employ Testing
      5. Be Assertive
    6. What You Will Need
    7. Conventions
        1. How It Works
    8. Source Code
    9. Errata
    10. p2p.wrox.com
  6. 1. Getting Started
    1. 1.1. Defining Algorithms
    2. 1.2. Understanding Complexity in Relation to Algorithms
    3. 1.3. Understanding Big-O Notation
      1. 1.3.1. Constant Time: O(1)
      2. 1.3.2. Linear Time: O(N)
      3. 1.3.3. Quadratic Time: O(N2)
      4. 1.3.4. Logarithmic Time: O(log N) and O(N log N)
      5. 1.3.5. Factorial Time: O(N!)
    4. 1.4. Unit Testing
      1. 1.4.1. What Is Unit Testing?
      2. 1.4.2. Why Unit Testing Is Important
      3. 1.4.3. A JUnit Primer
      4. 1.4.4. Test-Driven Development
    5. 1.5. Summary
  7. 2. Iteration and Recursion
    1. 2.1. Performing Calculations
      1. 2.1.1.
        1. 2.1.1.1. How It Works
        2. 2.1.1.2. How It Works
    2. 2.2. Processing Arrays
      1. 2.2.1. Using Iterators to Overcome Array-based Problems
        1. 2.2.1.1. Iterator Operations
        2. 2.2.1.2. The Iterator Interface
        3. 2.2.1.3. The Iterable Interface
        4. 2.2.1.4. Iterator Idioms
        5. 2.2.1.5. Standard Iterators
          1. 2.2.1.5.1. Array Iterator
        6. 2.2.1.6. How It Works
        7. 2.2.1.7. How It Works
        8. 2.2.1.8. A Reverse Iterator
        9. 2.2.1.9. How It Works
        10. 2.2.1.10. How It Works
        11. 2.2.1.11. A Filtering Iterator
          1. 2.2.1.11.1. The Predicate Class
        12. 2.2.1.12. How It Works
        13. 2.2.1.13. How It Works
    3. 2.3. Recursion
      1. 2.3.1. Recursive Directory Tree Printer Example
      2. 2.3.2. Anatomy of a Recursive Algorithm
        1. 2.3.2.1. The Base Case
        2. 2.3.2.2. The General Case
    4. 2.4. Summary
    5. 2.5. Exercises
  8. 3. Lists
    1. 3.1. Understanding Lists
      1. 3.1.1.
        1. 3.1.1.1. How It Works
    2. 3.2. Testing Lists
      1. 3.2.1.
        1. 3.2.1.1. How It Works
        2. 3.2.1.2. How It Works
        3. 3.2.1.3. How It Works
        4. 3.2.1.4. How It Works
        5. 3.2.1.5. How It Works
        6. 3.2.1.6. How It Works
    3. 3.3. Implementing Lists
      1. 3.3.1. An Array List
        1. 3.3.1.1. How It Works
        2. 3.3.1.2. How It Works
        3. 3.3.1.3. How It Works
        4. 3.3.1.4. How It Works
        5. 3.3.1.5. How It Works
        6. 3.3.1.6. How It Works
        7. 3.3.1.7. How It Works
      2. 3.3.2. A Linked List
        1. 3.3.2.1. How It Works
        2. 3.3.2.2. How It Works
        3. 3.3.2.3. How It Works
        4. 3.3.2.4. How It Works
        5. 3.3.2.5. How It Works
        6. 3.3.2.6. How It Works
        7. 3.3.2.7. How It Works
        8. 3.3.2.8. How It Works
        9. 3.3.2.9. How It Works
    4. 3.4. Summary
    5. 3.5. Exercises
  9. 4. Queues
    1. 4.1. Understanding Queues
      1. 4.1.1. Queue Operations
      2. 4.1.2. The Queue Interface
    2. 4.2. A First-In-First-Out Queue
      1. 4.2.1.
        1. 4.2.1.1. How It Works
      2. 4.2.2. Implementing the FIFO Queue
    3. 4.3. Blocking Queues
      1. 4.3.1.
        1. 4.3.1.1. How It Works
        2. 4.3.1.2. How It Works
        3. 4.3.1.3. How It Works
        4. 4.3.1.4. How It Works
    4. 4.4. Example: A Call Center Simulator
      1. 4.4.1.
        1. 4.4.1.1. How It Works
        2. 4.4.1.2. How It Works
        3. 4.4.1.3. How It Works
        4. 4.4.1.4. How It Works
        5. 4.4.1.5. How It Works
      2. 4.4.2. Running the Application
    5. 4.5. Summary
    6. 4.6. Exercises
  10. 5. Stacks
    1. 5.1. Stacks
    2. 5.2. The Tests
      1. 5.2.1.
        1. 5.2.1.1. How It Works
        2. 5.2.1.2. How It Works
        3. 5.2.1.3. How It Works
    3. 5.3. Implementation
      1. 5.3.1.
        1. 5.3.1.1. How It Works
        2. 5.3.1.2. How It Works
    4. 5.4. Example: Implementing Undo/Redo
      1. 5.4.1. Testing Undo/Redo
        1. 5.4.1.1. How It Works
        2. 5.4.1.2. How It Works
    5. 5.5. Summary
  11. 6. Basic Sorting
    1. 6.1. The Importance of Sorting
    2. 6.2. Sorting Fundamentals
    3. 6.3. Understanding Comparators
      1. 6.3.1. Comparator Operations
      2. 6.3.2. The Comparator Interface
      3. 6.3.3. Some Standard Comparators
        1. 6.3.3.1. Working with the Natural Comparator
          1. 6.3.3.1.1. The Comparable Interface
        2. 6.3.3.2. How It Works
        3. 6.3.3.3. How It Works
        4. 6.3.3.4. Working with the Reverse Comparator
        5. 6.3.3.5. How It Works
        6. 6.3.3.6. How It Works
      4. 6.3.4. Understanding Bubble Sort
      5. 6.3.5. The ListSorter Interface
      6. 6.3.6. Testing AbstractListSorter
        1. 6.3.6.1. How It Works
        2. 6.3.6.2. How It Works
    4. 6.4. Working with a Selection Sort
      1. 6.4.1.
        1. 6.4.1.1. How It Works
        2. 6.4.1.2. How It Works
    5. 6.5. Understanding Insertion Sort
      1. 6.5.1.
        1. 6.5.1.1. How It Works
        2. 6.5.1.2. How It Works
    6. 6.6. Understanding Stability
    7. 6.7. Comparing the Basic Sorting Algorithms
      1. 6.7.1. CallCountingListComparator
      2. 6.7.2. ListSorterCallCountingTest
      3. 6.7.3. Understanding the Algorithm Comparison
    8. 6.8. Summary
    9. 6.9. Exercises
  12. 7. Advanced Sorting
    1. 7.1. Understanding the Shellsort Algorithm
      1. 7.1.1.
        1. 7.1.1.1. How It Works
        2. 7.1.1.2. How It Works
    2. 7.2. Understanding Quicksort
      1. 7.2.1.
        1. 7.2.1.1. How It Works
        2. 7.2.1.2. How It Works
    3. 7.3. Understanding the Compound Comparator and Stability
      1. 7.3.1.
        1. 7.3.1.1. How It Works
    4. 7.4. Understanding the Mergesort Algorithm
      1. 7.4.1. Merging
      2. 7.4.2. The mergesort Algorithm
        1. 7.4.2.1. How It Works
    5. 7.5. Comparing the Advanced Sorting Algorithms
    6. 7.6. Summary
    7. 7.7. Exercises
  13. 8. Priority Queues
    1. 8.1. Understanding Priority Queues
      1. 8.1.1. A Simple Priority Queue Example
    2. 8.2. Working with Priority Queues
      1. 8.2.1. Understanding the Unsorted List Priority Queue
        1. 8.2.1.1. How It Works
      2. 8.2.2. Understanding the Sorted List Priority Queue
        1. 8.2.2.1. How It Works
      3. 8.2.3. Understanding Heap-ordered Priority Queues
        1. 8.2.3.1. Sink or Swim
        2. 8.2.3.2. How It Works
    3. 8.3. Comparing the Priority Queue Implementations
    4. 8.4. Summary
    5. 8.5. Exercises
  14. 9. Binary Searching and Insertion
    1. 9.1. Understanding Binary Searching
      1. 9.1.1. Binary Search Approaches
      2. 9.1.2. A List Searcher
        1. 9.1.2.1. How It Works
        2. 9.1.2.2. How It Works
        3. 9.1.2.3. How It Works
        4. 9.1.2.4. Recursive Binary Searcher
        5. 9.1.2.5. How It Works
      3. 9.1.3. Iterative Binary Searcher
        1. 9.1.3.1. How It Works
      4. 9.1.4. Assessing the List Searcher's Performance
        1. 9.1.4.1. Linear Searching for Comparison
        2. 9.1.4.2. How It Works
        3. 9.1.4.3. Tests for Performance
        4. 9.1.4.4. How It Works
        5. 9.1.4.5. How It Works
    2. 9.2. Understanding Binary Insertion
      1. 9.2.1. A List Inserter
        1. 9.2.1.1. How It Works
        2. 9.2.1.2. How It Works
      2. 9.2.2. Assessing Performance
        1. 9.2.2.1. How It Works
    3. 9.3. Summary
  15. 10. Binary Search Trees
    1. 10.1. Understanding Binary Search Trees
      1. 10.1.1. Minimum
      2. 10.1.2. Maximum
      3. 10.1.3. Successor
      4. 10.1.4. Predecessor
      5. 10.1.5. Search
      6. 10.1.6. Insertion
      7. 10.1.7. Deletion
      8. 10.1.8. In-order Traversal
      9. 10.1.9. Pre-order Traversal
      10. 10.1.10. Post-order Traversal
      11. 10.1.11. Balancing
    2. 10.2. Testing and Implementing a Binary Search Tree
      1. 10.2.1.
        1. 10.2.1.1. How It Works
        2. 10.2.1.2. How It Works
        3. 10.2.1.3. How It Works
        4. 10.2.1.4. How It Works
    3. 10.3. Assessing Binary Search Tree Performance
      1. 10.3.1.
        1. 10.3.1.1. How It Works
    4. 10.4. Summary
    5. 10.5. Exercises
  16. 11. Hashing
    1. 11.1. Understanding Hashing
    2. 11.2. Working with Hashing
      1. 11.2.1.
        1. 11.2.1.1. How It Works
        2. 11.2.1.2. How It Works
      2. 11.2.2. Linear Probing
        1. 11.2.2.1. How It Works
      3. 11.2.3. Bucketing
        1. 11.2.3.1. How It Works
    3. 11.3. Assessing Performance
      1. 11.3.1.
        1. 11.3.1.1. How It Works
    4. 11.4. Summary
    5. 11.5. Exercises
  17. 12. Sets
    1. 12.1. Understanding Sets
      1. 12.1.1.
        1. 12.1.1.1. How It Works
      2. 12.1.2. Testing Set Implementations
        1. 12.1.2.1. How It Works
    2. 12.2. A List Set
      1. 12.2.1.
        1. 12.2.1.1. How It Works
    3. 12.3. A Hash Set
      1. 12.3.1.
        1. 12.3.1.1. How It Works
    4. 12.4. A Tree Set
      1. 12.4.1.
        1. 12.4.1.1. How It Works
    5. 12.5. Summary
    6. 12.6. Exercises
  18. 13. Maps
    1. 13.1. Understanding Maps
      1. 13.1.1.
        1. 13.1.1.1. How It Works
        2. 13.1.1.2. How It Works
    2. 13.2. Testing Map Implementations
      1. 13.2.1.
        1. 13.2.1.1. How It Works
    3. 13.3. A List Map
      1. 13.3.1.
        1. 13.3.1.1. How It Works
    4. 13.4. A Hash Map
      1. 13.4.1.
        1. 13.4.1.1. How It Works
    5. 13.5. A Tree Map
      1. 13.5.1.
        1. 13.5.1.1. How It Works
    6. 13.6. Summary
    7. 13.7. Exercises
  19. 14. Ternary Search Trees
    1. 14.1. Understanding Ternary Search Trees
      1. 14.1.1. Searching for a Word
      2. 14.1.2. Inserting a Word
      3. 14.1.3. Prefix Searching
      4. 14.1.4. Pattern Matching
    2. 14.2. Putting Ternary Search Trees into Practice
      1. 14.2.1.
        1. 14.2.1.1. How It Works
        2. 14.2.1.2. How It Works
    3. 14.3. Crossword Helper Example
      1. 14.3.1.
        1. 14.3.1.1. How It Works
    4. 14.4. Summary
    5. 14.5. Exercise
  20. 15. B-Trees
    1. 15.1. Understanding B-Trees
    2. 15.2. Putting B-Trees into Practice
      1. 15.2.1.
        1. 15.2.1.1. How It Works
        2. 15.2.1.2. How It Works
    3. 15.3. Summary
    4. 15.4. Exercises
  21. 16. String Searching
    1. 16.1. A Generic String Searcher Interface
      1. 16.1.1.
        1. 16.1.1.1. How It Works
    2. 16.2. A Generic Test Suite
      1. 16.2.1.
        1. 16.2.1.1. How It Works
    3. 16.3. A Brute-Force Algorithm
      1. 16.3.1.
        1. 16.3.1.1. How It Works
        2. 16.3.1.2. How It Works
    4. 16.4. The Boyer-Moore Algorithm
      1. 16.4.1. Creating the Tests
        1. 16.4.1.1. How It Works
      2. 16.4.2. Implementing the Algorithm
        1. 16.4.2.1. How It Works
        2. 16.4.2.2. How It Works
        3. 16.4.2.3. How It Works
    5. 16.5. A String Match Iterator
      1. 16.5.1.
        1. 16.5.1.1. How It Works
    6. 16.6. Comparing the Performance
      1. 16.6.1. Measuring Performance
        1. 16.6.1.1. How It Works
        2. 16.6.1.2. How It Works
      2. 16.6.2. How They Compare
    7. 16.7. Summary
  22. 17. String Matching
    1. 17.1. Understanding Soundex
      1. 17.1.1.
        1. 17.1.1.1. How It Works
        2. 17.1.1.2. How It Works
    2. 17.2. Understanding Levenshtein Word Distance
      1. 17.2.1.
        1. 17.2.1.1. How It Works
        2. 17.2.1.2. How It Works
    3. 17.3. Summary
  23. 18. Computational Geometry
    1. 18.1. A Quick Geometry Refresher
      1. 18.1.1. Coordinates and Points
      2. 18.1.2. Lines
      3. 18.1.3. Triangles
      4. 18.1.4. Finding the Intersection of Two Lines
      5. 18.1.5. Slope
      6. 18.1.6. Crossing the y Axis
    2. 18.2. Finding the Intersection Point
      1. 18.2.1.
        1. 18.2.1.1. How It Works
        2. 18.2.1.2. How It Works
        3. 18.2.1.3. How It Works
        4. 18.2.1.4. How It Works
        5. 18.2.1.5. How It Works
    3. 18.3. Finding the Closest Pair of Points
      1. 18.3.1.
        1. 18.3.1.1. How It Works
        2. 18.3.1.2. How It Works
        3. 18.3.1.3. How It Works
        4. 18.3.1.4. How It Works
    4. 18.4. Summary
    5. 18.5. Exercises
  24. 19. Pragmatic Optimization
    1. 19.1. Where Optimization Fits In
    2. 19.2. Understanding Profiling
    3. 19.3. The FileSortingHelper Example Program
      1. 19.3.1.
        1. 19.3.1.1. How It Works
      2. 19.3.2. Profiling with hprof
      3. 19.3.3. Profiling with JMP
    4. 19.4. Understanding Optimization
    5. 19.5. Putting Optimization into Practice
      1. 19.5.1.
        1. 19.5.1.1. How It Works
        2. 19.5.1.2. How It Works
        3. 19.5.1.3. How It Works
    6. 19.6. Summary
  25. A. Further Reading
  26. B. Resources
  27. C. Bibliography
  28. D. Answers to Exercises
    1. D.1. Chapter 2
      1. D.1.1. Chapter 2
      2. D.1.2. Chapter 3
      3. D.1.3. Chapter 4
      4. D.1.4. Chapter 6
      5. D.1.5. Chapter 7
      6. D.1.6. Chapter 8
      7. D.1.7. Chapter 10
      8. D.1.8. Chapter 11
      9. D.1.9. Chapter 12
      10. D.1.10. Chapter 13
      11. D.1.11. Chapter 14
      12. D.1.12. Chapter 15
      13. D.1.13. Chapter 18