Table of Contents

  1. 1 Overview

    1. What Are Data Structures and Algorithms?

    2. Overview of Data Structures

    3. Overview of Algorithms

    4. Some Definitions

      1. Database

      2. Record

      3. Field

      4. Key

      5. Databases vs. Data Structures

    5. Programming in Python

      1. Interpreter

      2. Dynamic Typing

      3. Sequences

      4. Looping and Iteration

      5. Multivalued Assignment

      6. Importing Modules

      7. Functions and Subroutines

      8. List Comprehensions

      9. Exceptions

    6. Object-Oriented Programming

    7. Summary

    8. Questions

    9. Experiments

  2. 2 Arrays

    1. The Array Visualization Tool

      1. Searching

      2. The Duplicates Issue

    2. Using Python Lists to Implement the Array Class

      1. Creating an Array

      2. Accessing List Elements

      3. A Better Array Class Implementation

    3. The OrderedArray Visualization Tool

      1. Linear Search

    4. Binary Search

    5. Python Code for an OrderedArray Class

      1. Binary Search with the find() Method

      2. The OrderedArray Class

      3. Advantages of Ordered Arrays

    6. Logarithms

      1. The Equation

      2. The Opposite of Raising 2 to a Power

    7. Storing Objects

      1. The OrderedRecordArray Class

    8. Big O Notation

      1. Insertion in an Unordered Array: Constant

      2. Linear Search: Proportional to N

      3. Binary Search: Proportional to log(N)

      4. Don’t Need the Constant

    9. Why Not Use Arrays for Everything?

    10. Summary

    11. Questions

    12. Experiments

    13. Programming Projects

  3. 3 Simple Sorting

    1. How Would You Do It?

    2. Bubble Sort

      1. Bubble Sort on the Football Players

      2. The SimpleSorting Visualization Tool

      3. Python Code for a Bubble Sort

      4. Invariants

      5. Efficiency of the Bubble Sort

    3. Selection Sort

      1. Selection Sort on the Football Players

      2. A Brief Description

      3. A More Detailed Description

      4. The Selection Sort in the SimpleSorting Visualization Tool

      5. Python Code for Selection Sort

      6. Invariant

      7. Efficiency of the Selection Sort

    4. Insertion Sort

      1. Insertion Sort on the Football Players

      2. Partial Sorting

      3. The Marked Player

      4. The Insertion Sort in the SimpleSorting Visualization Tool

      5. Python Code for Insertion Sort

      6. Invariants in the Insertion Sort

      7. Efficiency of the Insertion Sort

      8. Python Code for Sorting Arrays

      9. Stability

    5. Comparing the Simple Sorts

    6. Summary

    7. Questions

    8. Experiments

    9. Programming Projects

  4. 4 Stacks and Queues

    1. Different Structures for Different Use Cases

      1. Storage and Retrieval Pattern

      2. Restricted Access

      3. More Abstract

    2. Stacks

      1. The Postal Analogy

      2. The Stack Visualization Tool

      3. Python Code for a Stack

      4. Stack Example 1: Reversing a Word

      5. Stack Example 2: Delimiter Matching

      6. Efficiency of Stacks

    3. Queues

      1. A Shifty Problem

      2. A Circular Queue

      3. The Queue Visualization Tool

      4. Python Code for a Queue

      5. Efficiency of Queues

      6. Deques

    4. Priority Queues

      1. The PriorityQueue Visualization Tool

      2. Python Code for a Priority Queue

      3. Efficiency of Priority Queues

      4. What About Search and Traversal?

    5. Parsing Arithmetic Expressions

      1. Postfix Notation

      2. Translating Infix to Postfix

      3. The InfixCalculator Tool

      4. Evaluating Postfix Expressions

    6. Summary

    7. Questions

    8. Experiments

    9. Programming Projects

  5. 5 Linked Lists

    1. Links

      1. References and Basic Types

      2. Relationship, Not Position

    2. The LinkedList Visualization Tool

      1. The Search Button

      2. The Delete Button

      3. The New Button

      4. The Other Buttons

    3. A Simple Linked List

      1. The Basic Linked List Methods

      2. Traversing Linked Lists

      3. Insertion and Search in Linked Lists

      4. Deletion in Linked Lists

    4. Double-Ended Lists

    5. Linked List Efficiency

    6. Abstract Data Types and Objects

      1. A Stack Implemented by a Linked List

      2. A Queue Implemented by a Linked List

      3. Data Types and Abstraction

      4. ADT Lists

      5. ADTs as a Design Tool

    7. Ordered Lists

      1. Python Code for Ordered Lists

      2. Efficiency of Ordered Linked Lists

      3. List Insertion Sort

    8. Doubly Linked Lists

      1. Insertion and Deletion at the Ends

      2. Insertion and Deletion in the Middle

      3. Doubly Linked List as Basis for Deques

    9. Circular Lists

    10. Iterators

      1. Basic Iterator Methods

      2. Other Iterator Methods

      3. Iterators in Python

    11. Summary

    12. Questions

    13. Experiments

    14. Programming Projects

  6. 6 Recursion

    1. Triangular Numbers

      1. Finding the nth Term Using a Loop

      2. Finding the nth Term Using Recursion

      3. What’s Really Happening?

      4. Characteristics of Recursive Routines

      5. Is Recursion Efficient?

      6. Mathematical Induction

    2. Factorials

    3. Anagrams

    4. A Recursive Binary Search

      1. Recursion Replaces the Loop

      2. Divide-and-Conquer Algorithms

    5. The Tower of Hanoi

      1. The TowerofHanoi Visualization Tool

      2. Moving Pyramids

      3. The Recursive Implementation

    6. Sorting with mergesort

      1. Merging Two Sorted Arrays

      2. Sorting by Merging

      3. Merging Subranges

      4. Testing the Code

      5. The Mergesort Visualization Tool

      6. Efficiency of the mergesort

    7. Eliminating Recursion

      1. Recursion and Stacks

      2. Simulating a Recursive Function: Triangular

      3. Rewriting a Recursive Procedure: mergesort

    8. Some Interesting Recursive Applications

      1. Raising a Number to a Power

      2. The Knapsack Problem

      3. Combinations: Picking a Team

    9. Summary

    10. Questions

    11. Experiments

    12. Programming Projects

  7. 7 Advanced Sorting

    1. Shellsort

      1. Insertion Sort: Too Many Copies

      2. N-Sorting

      3. Diminishing Gaps

      4. The AdvancedSorting Visualization Tool

      5. Python Code for the Shellsort

      6. Other Interval Sequences

      7. Efficiency of the Shellsort

    2. Partitioning

      1. The Partition Process

      2. The General Partitioning Algorithm

      3. Efficiency of the Partition Algorithm

    3. Quicksort

      1. The Basic Quicksort Algorithm

      2. Choosing a Pivot Value

      3. A First Quicksort Implementation

      4. Running Quicksort in the AdvancedSorting Visualization Tool

      5. The Details

      6. Degenerates to O(N2) Performance

      7. Median-of-Three Partitioning

      8. Handling Small Partitions

      9. The Full Quicksort Implementation

      10. Removing Recursion

      11. Efficiency of Quicksort

    4. Radix Sort

      1. Algorithm for the Radix Sort

      2. Designing a Radix Sort Program

      3. Efficiency of the Radix Sort

      4. Generalizing the Radix Sort

      5. Using a Counting Sort

    5. Timsort

      1. Efficiency of Timsort

    6. Summary

    7. Questions

    8. Experiments

    9. Programming Projects

  8. 8 Binary Trees

    1. Why Use Binary Trees?

      1. Slow Insertion in an Ordered Array

      2. Slow Searching in a Linked List

      3. Trees to the Rescue

      4. What Is a Tree?

    2. Tree Terminology

      1. Root

      2. Path

      3. Parent

      4. Child

      5. Sibling

      6. Leaf

      7. Subtree

      8. Visiting

      9. Traversing

      10. Levels

      11. Keys

      12. Binary Trees

      13. Binary Search Trees

    3. An Analogy

    4. How Do Binary Search Trees Work?

      1. The Binary Search Tree Visualization Tool

      2. Representing the Tree in Python Code

    5. Finding a Node

      1. Using the Visualization Tool to Find a Node

      2. Python Code for Finding a Node

      3. Tree Efficiency

    6. Inserting a Node

      1. Using the Visualization Tool to Insert a Node

      2. Python Code for Inserting a Node

    7. Traversing the Tree

      1. In-order Traversal

      2. Pre-order and Post-order Traversals

      3. Python Code for Traversing

      4. Traversing with the Visualization Tool

      5. Traversal Order

    8. Finding Minimum and Maximum Key Values

    9. Deleting a Node

      1. Case 1: The Node to Be Deleted Has No Children

      2. Case 2: The Node to Be Deleted Has One Child

      3. Case 3: The Node to Be Deleted Has Two Children

    10. The Efficiency of Binary Search Trees

    11. Trees Represented as Arrays

      1. Tree Levels and Size

    12. Printing Trees

    13. Duplicate Keys

    14. The BinarySearchTreeTester.py Program

    15. The Huffman Code

      1. Character Codes

      2. Decoding with the Huffman Tree

      3. Creating the Huffman Tree

      4. Coding the Message

    16. Summary

    17. Questions

    18. Experiments

    19. Programming Projects

  9. 9 2-3-4 Trees and External Storage

    1. Introduction to 2-3-4 Trees

      1. What’s in a Name?

      2. 2-3-4 Tree Terminology

      3. 2-3-4 Tree Organization

      4. Searching a 2-3-4 Tree

      5. Insertion

      6. Node Splits

      7. Splitting the Root

      8. Splitting on the Way Down

    2. The Tree234 Visualization Tool

      1. The Random Fill and New Tree Buttons

      2. The Search Button

      3. The Insert Button

      4. Zooming and Scrolling

      5. Experiments

    3. Python Code for a 2-3-4 Tree

      1. The __Node Class

      2. The Tree234 Class

      3. Traversal

      4. Deletion

    4. Efficiency of 2-3-4 Trees

      1. Speed

      2. Storage Requirements

    5. 2-3 Trees

      1. Node Splits

      2. Promoting Splits to Internal Nodes

      3. Implementation

      4. Efficiency of 2-3 Trees

    6. External Storage

      1. Accessing External Data

      2. Sequential Ordering

      3. B-Trees

      4. Indexing

      5. Complex Search Criteria

      6. Sorting External Files

    7. Summary

    8. Questions

    9. Experiments

    10. Programming Projects

  10. 10 AVL and Red-Black Trees

    1. Our Approach to the Discussion

    2. Balanced and Unbalanced Trees

      1. Degenerates to O(N)

      2. Measuring Tree Balance

      3. How Much Is Unbalanced?

    3. AVL Trees

      1. The AVLTree Visualization Tool

      2. Inserting Items with the AVLTree Visualization Tool

      3. Python Code for the AVL Tree

    4. The Efficiency of AVL Trees

    5. Red-Black Trees

      1. Conceptual

      2. Top-Down Insertion

      3. Bottom-Up Insertion

      4. Red-Black Tree Characteristics

    6. Using the Red-Black Tree Visualization Tool

      1. Flipping a Node’s Color

      2. Rotating Nodes

      3. The Insert Button

      4. The Search Button

      5. The Delete Button

      6. The Erase & Random Fill Button

    7. Experimenting with the Visualization Tool

      1. Experiment 1: Inserting Two Red Nodes

      2. Experiment 2: Rotations

      3. Experiment 3: Color Swaps

      4. Experiment 4: An Unbalanced Tree

      5. More Experiments

      6. The Red-Black Rules and Balanced Trees

      7. Null Children

    8. Rotations in Red-Black Trees

      1. Subtrees on the Move

    9. Inserting a New Node

      1. Preview of the Insertion Process

      2. Color Swaps on the Way Down

      3. Rotations After the Node Is Inserted

      4. Rotations on the Way Down

    10. Deletion

    11. The Efficiency of Red-Black Trees

    12. 2-3-4 Trees and Red-Black Trees

      1. Transformation from 2-3-4 to Red-Black

      2. Operational Equivalence

    13. Red-Black Tree Implementation

    14. Summary

    15. Questions

    16. Experiments

    17. Programming Projects

  11. 11 Hash Tables

    1. Introduction to Hashing

      1. Bank Account Numbers as Keys

      2. A Dictionary

      3. Hashing

      4. Collisions

    2. Open Addressing

      1. Linear Probing

      2. Python Code for Open Addressing Hash Tables

      3. Quadratic Probing

      4. Double Hashing

    3. Separate Chaining

      1. The HashTableChaining Visualization Tool

      2. Python Code for Separate Chaining

    4. Hash Functions

      1. Quick Computation

      2. Random Keys

      3. Nonrandom Keys

      4. Hashing Strings

      5. Folding

    5. Hashing Efficiency

      1. Open Addressing

      2. Separate Chaining

      3. Open Addressing Versus Separate Chaining

    6. Hashing and External Storage

      1. Table of File Pointers

      2. Nonfull Blocks

      3. Full Blocks

    7. Summary

    8. Questions

    9. Experiments

    10. Programming Projects

  12. 12 Spatial Data Structures

    1. Spatial Data

      1. Cartesian Coordinates

      2. Geographic Coordinates

    2. Computing Distances Between Points

      1. Distance Between Cartesian Coordinates

    3. Circles and Bounding Boxes

      1. Clarifying Distances and Circles

      2. Bounding Boxes

      3. The Bounding Box of a Query Circle in Cartesian Coordinates

      4. The Bounding Box of a Query Circle in Geographic Coordinates

      5. Implementing Bounding Boxes in Python

      6. The CircleBounds Subclass

      7. Determining Whether Two Bounds Objects Intersect

      8. Determining Whether One Bounds Object Lies Entirely Within Another

    4. Searching Spatial Data

    5. Lists of Points

      1. Creating an Instance of the PointList Class

      2. Inserting Points

      3. Finding an Exact Match

      4. Deleting a Point

      5. Traversing the Points

      6. Finding the Nearest Match

    6. Grids

      1. Implementing a Grid in Python

      2. Creating an Instance of the Grid Class

      3. Inserting Points

      4. Finding an Exact Match

      5. Big O and Practical Considerations

      6. Deleting and Traversing

      7. Finding the Nearest Match

      8. Does the Query Circle Fall Within a Layer?

      9. Does the Query Circle Intersect a Grid Cell?

      10. Generating the Sequence of Neighboring Cells to Visit

      11. Pulling It All Together: Implementing Grid’s findNearest()

    7. Quadtrees

      1. Creating an Instance of the QuadTree Class

      2. Inserting Points: A Conceptual Overview

      3. Avoiding Ambiguity

      4. The QuadTree Visualization Tool

      5. Implementing Quadtrees: The Node Class

      6. The insert Method

      7. Efficiency of Insertion

      8. Finding an Exact Match

      9. Efficiency of Exact Search

      10. Traversing the Points

      11. Deleting a Point

      12. Finding the Nearest Match

      13. Finding a Candidate Node

      14. Finding the Closest Node

      15. Pulling It All Together: Implementing QuadTree’s findNearest()

      16. Efficiency of findNearest()

    8. Theoretical Performance and Optimizations

    9. Practical Considerations

    10. Further Extensions

      1. Other Operations

      2. Higher Dimensions

    11. Summary

    12. Questions

    13. Experiments

    14. Programming Projects

  13. 13 Heaps

    1. Introduction to Heaps

      1. Priority Queues, Heaps, and ADTs

      2. Partially Ordered

      3. Insertion

      4. Removal

      5. Other Operations

    2. The Heap Visualization Tool

      1. The Insert Button

      2. The Make Random Heap Button

      3. The Erase and Random Fill Button

      4. The Peek Button

      5. The Remove Max Button

      6. The Heapify Button

      7. The Traverse Button

    3. Python Code for Heaps

      1. Insertion

      2. Removal

      3. Traversal

      4. Efficiency of Heap Operations

    4. A Tree-Based Heap

    5. Heapsort

      1. Sifting Down Instead of Up

      2. Using the Same Array

      3. The heapsort() Subroutine

      4. The Efficiency of Heapsort

    6. Order Statistics

      1. Partial Ordering Assists in Finding the Extreme Values

      2. The Efficiency of K Highest

    7. Summary

    8. Questions

    9. Experiments

    10. Programming Projects

  14. 14 Graphs

    1. Introduction to Graphs

      1. Definitions

      2. The First Uses of Graphs

      3. Representing a Graph in a Program

      4. Adding Vertices and Edges to a Graph

      5. The Graph Class

    2. Traversal and Search

      1. Depth-First

      2. Breadth-First

    3. Minimum Spanning Trees

      1. Minimum Spanning Trees in the Graph Visualization Tool

      2. Trees Within a Graph

      3. Python Code for the Minimum Spanning Tree

    4. Topological Sorting

      1. Dependency Relationships

      2. Directed Graphs

      3. Sorting Directed Graphs

      4. The Graph Visualization Tool

      5. The Topological Sorting Algorithm

      6. Cycles and Trees

      7. Python Code for the Basic Topological Sort

      8. Improving the Topological Sort

    5. Connectivity in Directed Graphs

      1. The Connectivity Matrix

      2. Transitive Closure and Warshall’s Algorithm

      3. Implementation of Warshall’s Algorithm

    6. Summary

    7. Questions

    8. Experiments

    9. Programming Projects

  15. 15 Weighted Graphs

    1. Minimum Spanning Tree with Weighted Graphs

      1. An Example: Networking in the Jungle

      2. The WeightedGraph Visualization Tool

      3. Building the Minimum Spanning Tree: Send Out the Surveyors

      4. Creating the Algorithm

    2. The Shortest-Path Problem

      1. Travel by Rail

      2. Dijkstra’s Algorithm

      3. Agents and Train Rides

      4. Finding Shortest Paths Using the Visualization Tool

      5. Implementing the Algorithm

      6. Python Code

    3. The All-Pairs Shortest-Path Problem

    4. Efficiency

    5. Intractable Problems

      1. The Knight’s Tour

      2. The Traveling Salesperson Problem

      3. Hamiltonian Paths and Cycles

    6. Summary

    7. Questions

    8. Experiments

    9. Programming Projects

  16. 16 What to Use and Why

    1. Analyzing the Problem

      1. What Kind of Data?

      2. How Much Data?

      3. What Operations and How Frequent?

      4. Who Will Maintain the Software?

    2. Foundational Data Structures

      1. Speed and Algorithms

      2. Libraries

      3. Arrays

      4. Linked Lists

      5. Binary Search Trees

      6. Balanced Search Trees

      7. Hash Tables

      8. Comparing the General-Purpose Storage Structures

    3. Special-Ordering Data Structures

      1. Stack

      2. Queue

      3. Priority Queue

      4. Comparison of Special-Ordering Structures

    4. Sorting

    5. Specialty Data Structures

      1. Quadtrees and Grids

      2. Graphs

    6. External Storage

      1. Sequential Storage

      2. Indexed Files

      3. B-trees

      4. Hashing

      5. Choosing Among External Storage Types

      6. Virtual Memory

    7. Onward

    8. Appendixes

  17. A Running the Visualizations

    1. For Developers: Running and Changing the Visualizations

      1. Getting Python

      2. Getting Git

      3. Getting the Visualizations

    2. For Managers: Downloading and Running the Visualizations

    3. For Others: Viewing the Visualizations on the Internet

    4. Using the Visualizations

  18. B Further Reading

    1. Data Structures and Algorithms

    2. Object-Oriented Programming Languages

    3. Object-Oriented Design (OOD) and Software Engineering

  19. C Answers to Questions

    1. Chapter 1, “Overview”

    2. Chapter 2, “Arrays”

    3. Chapter 3, “Simple Sorting”

    4. Chapter 4, “Stacks and Queues”

    5. Chapter 5, “Linked Lists”

    6. Chapter 6, “Recursion”

    7. Chapter 7, “Advanced Sorting”

    8. Chapter 8, “Binary Trees”

    9. Chapter 9, “2-3-4 Trees and External Storage”

    10. Chapter 10, “AVL and Red-Black Trees”

    11. Chapter 11, “Hash Tables”

    12. Chapter 12, “Spatial Data Structures”

    13. Chapter 13, “Heaps”

    14. Chapter 14, “Graphs”

    15. Chapter 15, “Weighted Graphs”

  20. Index

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
18.188.175.182