Data Structures and Algorithms Using Python

by Rance D. Necaise (College of William and Mary)

• ISBN13: 9780470618295
• ISBN10: 0470618299
• Format: Paperback
• Copyright: 2010-12-01
• Publisher: Wiley

Summary

More and more programmers are turning to Python and this book will give them the understanding they need. Necaise introduces the basic array structure and explores the fundamentals of implementing and using multi-dimensional arrays. The underlying mechanisms of many of Python's built-in data structures and constructs are covered. A number of ADTs and applications are discussed as threads throughout the book to allow for multiple implementations as new data structures are introduced. Real-world applications of the various chapter topics are also presented. This gives programmers complete coverage of abstraction and the basic data structures and algorithms in the Python language.

Table of Contents

Abstract Data Types	p. 1
Introduction	p. 1
Abstractions	p. 2
Abstract Data Types	p. 4
Data Structures	p. 5
The Date ADT	p. 6
Preconditions and Postconditions	p. 8
Using the ADT	p. 8
Implementing the ADT	p. 8
The Bag ADT	p. 14
Using the ADT	p. 15
Selecting a Data Structure	p. 16
The Class Definition	p. 18
Iterators	p. 19
The Set ADT	p. 22
Using the ADT	p. 24
Implementing the ADT	p. 25
The Map ADT	p. 28
Defining the ADT	p. 29
Implementing the Map ADT	p. 30
Alternate Implementation	p. 33
Application: Histograms	p. 35
Building a Histogram	p. 37
Implementing the Histogram ADT	p. 37
Programming Problems	p. 40
Arrays and Vectors	p. 43
The Array Structure	p. 43
Simulating an Array	p. 44
The Array ADT	p. 45
Implementing the ADT	p. 46
The Python List (Vector)	p. 47
Multi-Dimensional Arrays	p. 54
The MultiArray ADT	p. 54
Data Organization	p. 55
Variable Length Arguments	p. 59
MultiArray Implementation	p. 60
The Matrix ADT	p. 64
Matrix Operations	p. 65
Implementing the ADT	p. 67
Application: The Game of Life	p. 69
Rules of the Game	p. 70
Designing a Solution	p. 72
ADT Implementation	p. 74
Exercises	p. 77
Programming Problems	p. 78
Algorithm Analysis	p. 81
Complexity Analysis	p. 82
Big-O Notation	p. 83
Classes of Algorithms	p. 87
Empirical Analysis	p. 88
Evaluating ADT Implementations	p. 88
Evaluating the Python List	p. 89
Evaluating the Set ADT	p. 91
Searching	p. 92
Linear Search	p. 92
Binary Search	p. 95
Working with Ordered Lists	p. 99
Building An Ordered List	p. 99
Merging Ordered Lists	p. 100
The Set ADT Revisited	p. 106
Application: The Sparse Matrix	p. 112
Implementation	p. 112
Analysis	p. 116
Exercises	p. 118
Programming Problems	p. 120
The Linked List	p. 123
A Linked Structure	p. 124
The Singly-Linked List	p. 124
Basic Operations	p. 124
Evaluating the Linked List	p. 124
The Bag ADT Revisited	p. 124
Implementation Details	p. 124
Linked List Iterator	p. 124
Using a Tail Pointer	p. 124
The Ordered Linked List	p. 124
The Sparse Matrix Revisited	p. 124
The New Implementation	p. 124
Comparing Implementations	p. 124
Application: Polynomials	p. 124
Polynomial Operations	p. 124
The Polynomial ADT	p. 124
ADT Implementation	p. 124
Exercises	p. 124
Programming Problems	p. 124
Advanced Linked Lists	p. 125
Doubly-Linked List	p. 126
Organization	p. 126
List Operations	p. 126
Circular Linked List	p. 126
Organization	p. 126
List Operations	p. 126
Multi-Linked Lists	p. 126
Multiple Chains	p. 126
The Sparse Matrix	p. 126
Complex Iterators	p. 126
Application: Text Editor	p. 126
Typical Editor Operations	p. 126
The Edit Buffer ADT	p. 126
Implementing the ADT	p. 126
Exercises	p. 126
Programming Problems	p. 126
Stacks	p. 127
The Stack ADT	p. 128
Implementing the Stack	p. 128
Vector Based	p. 128
Linked List Version	p. 128
Stack Applications	p. 128
Balanced Delimiters	p. 128
Evaluating Postfix Expressions	p. 128
Application: Solving a Maze	p. 128
Backtracking	p. 128
Designing a Solution	p. 128
The Maze ADT	p. 128
ADT Implementation	p. 128
Exercises	p. 128
Programming Problems	p. 128
Queues	p. 129
The Queue ADT	p. 129
Implementing the Queue	p. 129
Vector Based	p. 129
Circular Array	p. 129
Linked List Version	p. 129
The Priority Queue	p. 129
Application: Computer Simulations	p. 129
Airline Ticket Counter	p. 129
Class Specifications	p. 129
Exercises	p. 129
Programming Problems	p. 129
Hash Tables	p. 131
Introduction	p. 131
Hash Functions	p. 131
Open Addressing	p. 131
Linear Probing	p. 131
Collision Resolution	p. 131
Bucket Hashing	p. 131
Hashing Efficiency	p. 131
The Map ADT Revisited	p. 131
Application: The Color Histogram	p. 131
Exercises	p. 131
Programming Problems	p. 131
Recursion	p. 133
Recursive Functions	p. 133
Properties of Recursion	p. 133
Classic Example: The Factorial Function	p. 133
Greatest Common Divisor	p. 133
Recursion and Stacks	p. 133
The Towers of Hanoi	p. 133
Backtracking Revisited	p. 133
The Eight-Queens Problem	p. 133
Solving the Four-Queens	p. 133
Recursive Solution	p. 133
Application: Sudoku Puzzles	p. 133
Exercises	p. 133
Programming Problems	p. 133
Binary Trees and Heaps	p. 135
Tree Structure	p. 135
The Binary Tree	p. 135
Traversals	p. 135
Arithmetic Expresssions	p. 135
Tree Threading	p. 135
Heaps	p. 135
Insertions	p. 135
Removals	p. 135
Evaluating the Heap	p. 135
The Priority Queue Revisited	p. 135
Application: Morse Code	p. 135
Exercises	p. 135
Programming Problems	p. 135
Advanced Search Trees	p. 137
The Binary Search Tree	p. 138
Searching	p. 138
Insertions	p. 138
Deletions	p. 138
Evaluating the BST	p. 138
AVL Trees	p. 138
Insertions	p. 138
Deletions	p. 138
Evaluating the AVL Tree	p. 138
2-3 Trees	p. 138
Splay Trees	p. 138
Application: Improved Map ADT	p. 138
Exercises	p. 138
Programming Problems	p. 138
Sorting Algorithms	p. 139
The Simple Algorithms	p. 140
Bubble Sort	p. 140
Selection Sort	p. 140
Insertion Sort	p. 140
Radix Sort	p. 140
Basic Algorithm	p. 140
Bucket Sorting	p. 140
Divide and Conquer	p. 140
Merge Sort	p. 140
Quick Sort	p. 140
Heap Sort	p. 140
Application: Empirical Analysis	p. 140
Exercises	p. 140
Programming Problems	p. 140
Python Review	p. 141
Basic Concepts	p. 141
Functions	p. 141
Sequence Types	p. 141
Classes	p. 141
Copying Objects	p. 141
Exceptions	p. 141
Object-Oriented Programming	p. 143
Introduction	p. 143
Encapsulation	p. 143
Inheritance	p. 143
Polymorphism	p. 143
Table of Contents provided by Publisher. All Rights Reserved.