Problem Solving with Algorithms and Data Structures Using Python

by Miller, Bradley N.

• ISBN13: 9781590280539
• ISBN10: 1590280539
• Format: Paperback
• Copyright: 2005-09-01
• Publisher: Franklin Beedle & Assoc
• More Book Details
• Purchase Benefits

Table of Contents

Preface	viii
Introduction	1	(50)
Objectives	1	(1)
Getting Started	1	(1)
What Is Computer Science?	2	(5)
What Is Programming?	4	(1)
Why Study Data Structures and Abstract Data Types?	5	(1)
Why Study Algorithms?	6	(1)
Review of Basic Python	7	(40)
Getting Started with Data	8	(1)
Primitive Classes	8	(2)
Built-in Collections	10	(9)
Control Structures	19	(6)
Defining Functions	25	(1)
Object-Oriented Programming in Python: Defining Classes	26	(1)
A Fraction Class	26	(8)
Inheritance: Logic Gates and Circuits	34	(13)
Summary	47	(1)
Key Terms	48	(1)
Discussion Questions	48	(1)
Programming Exercises	48	(3)
Basic Data Structures	51	(48)
Objectives	51	(1)
What Are Linear Structures?	51	(1)
Stacks	52	(22)
What is a Stack?	52	(2)
The Stack Abstract Data Type	54	(1)
Implementing a Stack in Python	55	(2)
Simple Balanced Parentheses	57	(3)
Balanced Symbols (A General Case)	60	(2)
Converting Decimal Numbers to Binary Numbers	62	(3)
Infix, Prefix and Postfix Expressions	65	(2)
Conversion of Infix Expressions to Prefix and Postfix Expressions	67	(1)
General Infix-to-Postfix Conversion	68	(3)
Postfix Evaluation	71	(3)
Queues	74	(14)
What Is a Queue?	75	(1)
The Queue Abstract Data Type	76	(1)
Implementing a Queue in Python	77	(2)
Simulation: Hot Potato	79	(2)
Simulation: Printing Tasks	81	(1)
Main Simulation Steps	82	(1)
Python Implementation	83	(4)
Discussion	87	(1)
Deque	88	(5)
What Is a Deque?	88	(1)
The Deque Abstract Data Type	88	(1)
Implementing a Deque in Python	89	(2)
Palindrome-Checker	91	(2)
Summary	93	(1)
Key Terms	94	(1)
Discussion Questions	94	(1)
Programming Exercises	95	(4)
Recursion	99	(30)
Objectives	99	(1)
What Is Recursion?	99	(6)
Calculating the Sum of a List of Numbers	99	(2)
The Three Laws of Recursion	101	(2)
Converting an Integer to a String in Any Base	103	(2)
Stack Frames: Implementing Recursion	105	(3)
Complex Recursive Problems	108	(17)
Tower of Hanoi	108	(3)
Sierpinski Triangle	111	(2)
Cryptography and Modular Arithmetic	113	(2)
Modular Arithmetic Theorems	115	(1)
Modular Exponentiation	116	(1)
The Greatest Common Divisor and Multiplicative Inverses	117	(4)
RSA Algorithm	121	(4)
Summary	125	(1)
Key Terms	125	(1)
Discussion Questions	125	(1)
Programming Exercises	126	(3)
Algorithm Analysis	129	(54)
Objectives	129	(1)
What Is Algorithm Analysis?	129	(12)
Big-O Notation	134	(2)
An Anagram Example	136	(1)
Solution 1: Checking Off	137	(1)
Solution 2: Sort and Compare	138	(1)
Solution 3: Brute Force	139	(1)
Solution 4: Count and Compare	140	(1)
Searching	141	(18)
The Sequential Search	141	(4)
The Binary Search	145	(2)
Hashing	147	(2)
Hash Functions	149	(3)
Collision Resolution	152	(3)
The Hash Table Class	155	(3)
Analysis of Hashing	158	(1)
Sorting	159	(19)
The Bubble Sort	159	(3)
The Selection Sort	162	(1)
The Insertion Sort	163	(4)
The Shell Sort	167	(3)
The Merge Sort	170	(4)
The Quick Sort	174	(4)
Summary	178	(1)
Key Terms	179	(1)
Discussion Questions	179	(2)
Programming Exercises	181	(2)
Trees	183	(54)
Objectives	183	(1)
Examples of Trees	183	(4)
Vocabulary and Definitions	187	(2)
Implementation	189	(8)
List of Lists Representation	190	(2)
Nodes and References	192	(5)
Binary Tree Applications	197	(11)
Parse Tree	197	(7)
Tree Traversals	204	(4)
Binary Search Trees	208	(15)
Search Tree Operations	209	(1)
Search Tree Implementation	209	(13)
Search Tree Analysis	222	(1)
Priority Queues with Binary Heaps	223	(9)
Binary Heap Operations	224	(1)
Binary Heap Implementation	225	(1)
The Structure Property	225	(1)
The Heap Order Property	226	(1)
Heap Operations	226	(6)
Summary	232	(1)
Key Terms	233	(1)
Discussion Questions	233	(2)
Programming Exercises	235	(2)
Graphs	237	(44)
Objectives	237	(1)
Vocabulary and Definitions	238	(2)
Representation	240	(6)
An Adjacency Matrix	240	(2)
An Adjacency List	242	(1)
Implementation	242	(4)
Graph Algorithms	246	(31)
A Breadth First Search	246	(1)
The Word Ladder Problem	246	(7)
Depth First Search	253	(1)
The Knights Tour Problem	253	(7)
General Depth First Search	260	(3)
Topological Sorting	263	(2)
Strongly Connected Components	265	(4)
Shortest Path Problems	269	(4)
Spanning Trees	273	(4)
Summary	277	(1)
Key Terms	278	(1)
Discussion Questions	279	(1)
Programming Exercises	280	(1)
Advanced Topics	281	(68)
Objectives	281	(1)
Lists Revisited Linked Lists	281	(17)
The List Abstract Data Type	282	(1)
Implementing a List in Python: Linked Lists	283	(1)
The Node Class	284	(2)
The List Class	286	(12)
Analysis of Linked Lists	298	(1)
Recursion Revisited: Dynamic Programming	298	(7)
Dictionaries Revisited: Skip Lists	305	(13)
The Map Abstract Data Type	305	(1)
Implementing a Dictionary in Python	306	(4)
Searching a Skip List	310	(2)
Adding Key-Value Pairs to a Skip List	312	(4)
Building the Map	316	(1)
Analysis of a Skip List	317	(1)
Trees Revisited: Quantizing Images with Oct Trees	318	(15)
A Quick Review of Digital Images	318	(2)
Quantizing an Image	320	(2)
An Improved Quantization Algorithm Using Oct Trees	322	(11)
Graphs Revisited: Pattern Matching	333	(9)
Biological Strings	334	(1)
Simple Comparison	334	(2)
Using Graphs: Finite State Automata	336	(2)
Using Graphs: Knuth-Morris-Pratt	338	(4)
Summary	342	(1)
Key Terms	343	(1)
Discussion Questions	343	(1)
Programming Exercises	344	(5)
Appendix A: Graphics Packages for Python	349