Data structures and algorithms using Python
By: Rance D. Necaise
Publisher: Wiley
Published: 2011
Place of publication: Hoboken, N.J
Language: eng
Number of pages: 520
ISBN-13: 9780470618295
Subjects: Python (Computer program language); Algorithms; Data structures (Computer science); COMPUTERS / Software Development & Engineering / General
Description: "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"--
Notes: Includes bibliographical references and (p. 509-510) index.
Table of contents: title: Preface
pagenum: xiii; label: Chapter 1
title: Abstract Data Types
pagenum: 1; label: 1.1
title: Introduction
pagenum: 1; label: 1.1.1
title: Abstractions
pagenum: 2; label: 1.1.2
title: Abstract Data Types
pagenum: 3; label: 1.1.3
title: Data Structures
pagenum: 5; label: 1.1.4
title: General Definitions
pagenum: 6; label: 1.2
title: The Date Abstract Data Type
pagenum: 7; label: 1.2.1
title: Defining the ADT
pagenum: 7; label: 1.2.2
title: Using the ADT
pagenum: 8; label: 1.2.3
title: Preconditions and Postconditions
pagenum: 9; label: 1.2.4
title: Implementing the ADT
pagenum: 10; label: 1.3
title: Bags
pagenum: 14; label: 1.3.1
title: The Bag Abstract Data Type
pagenum: 15; label: 1.3.2
title: Selecting a Data Structure
pagenum: 17; label: 1.3.3
title: List-Based Implementation
pagenum: 19; label: 1.4
title: Iterators
pagenum: 20; label: 1.4.1
title: Designing an Iterator
pagenum: 21; label: 1.4.2
title: Using Iterators
pagenum: 22; label: 1.5
title: Application: Student Records
pagenum: 23; label: 1.5.1
title: Designing a Solution
pagenum: 23; label: 1.5.2
title: Implementation
pagenum: 26; title: Exercises
pagenum: 28; title: Programming Projects
pagenum: 29; label: Chapter 2
title: Arrays
pagenum: 33; label: 2.1
title: The Array Structure
pagenum: 33; label: 2.1.1
title: Why Study Arrays?
pagenum: 34; label: 2.1.2
title: The Array Abstract Data Type
pagenum: 34; label: 2.1.3
title: Implementing the Array
pagenum: 36; label: 2.2
title: The Python List
pagenum: 41; label: 2.2.1
title: Creating a Python List
pagenum: 41; label: 2.2.2
title: Appending Items
pagenum: 42; label: 2.2.3
title: Extending a List
pagenum: 44; label: 2.2.4
title: Inserting Items
pagenum: 44; label: 2.2.5
title: List Slice
pagenum: 45; label: 2.3
title: Two-Dimensional Arrays
pagenum: 47; label: 2.3.1
title: The Array2D Abstract Data Type
pagenum: 47; label: 2.3.2
title: Implementing the 2-D Array
pagenum: 49; label: 2.4
title: The Matrix Abstract Data Type
pagenum: 52; label: 2.4.1
title: Matrix Operations
pagenum: 53; label: 2.4.2
title: Implementing the Matrix
pagenum: 55; label: 2.5
title: Application: The Game of Life
pagenum: 57; label: 2.5.1
title: Rules of the Game
pagenum: 57; label: 2.5.2
title: Designing a Solution
pagenum: 59; label: 2.5.3
title: Implementation
pagenum: 61; title: Exercises
pagenum: 64; title: Programming Projects
pagenum: 65; label: Chapter 3
title: Sets and Maps
pagenum: 69; label: 3.1
title: Sets
pagenum: 69; label: 3.1.1
title: The Set Abstract Data Type
pagenum: 70; label: 3.1.2
title: Selecting a Data Structure
pagenum: 72; label: 3.1.3
title: List-Based Implementation
pagenum: 72; label: 3.2
title: Maps
pagenum: 75; label: 3.2.1
title: The Map Abstract Data Type
pagenum: 76; label: 3.2.2
title: List-Based Implementation
pagenum: 77; label: 3.3
title: Multi-Dimensional Arrays
pagenum: 80; label: 3.3.1
title: The MultiArray Abstract Data Type
pagenum: 81; label: 3.3.2
title: Data Organization
pagenum: 81; label: 3.3.3
title: Variable-Length Arguments
pagenum: 85; label: 3.3.4
title: Implementing the MultiArray
pagenum: 86; label: 3.4
title: Application: Sales Reports
pagenum: 89; title: Exercises
pagenum: 95; title: Programming Projects
pagenum: 96; label: Chapter 4
title: Algorithm Analysis
pagenum: 97; label: 4.1
title: Complexity Analysis
pagenum: 97; label: 4.1.1
title: Big-O Notation
pagenum: 99; label: 4.1.2
title: Evaluating Python Code
pagenum: 104; label: 4.2
title: Evaluating the Python List
pagenum: 108; label: 4.3
title: Amortized Cost
pagenum: 111; label: 4.4
title: Evaluating the Set ADT
pagenum: 113; label: 4.5
title: Application: The Sparse Matrix
pagenum: 115; label: 4.5.1
title: List-Based Implementation
pagenum: 115; label: 4.5.2
title: Efficiency Analysis
pagenum: 120; title: Exercises
pagenum: 121; title: Programming Projects
pagenum: 122; label: Chapter 5
title: Searching and Sorting
pagenum: 125; label: 5.1
title: Searching
pagenum: 125; label: 5.1.1
title: The Linear Search
pagenum: 126; label: 5.1.2
title: The Binary Search
pagenum: 128; label: 5.2
title: Sorting
pagenum: 131; label: 5.2.1
title: Bubble Sort
pagenum: 132; label: 5.2.2
title: Selection Sort
pagenum: 136; label: 5.2.3
title: Insertion Sort
pagenum: 138; label: 5.3
title: Working with Sorted Lists
pagenum: 142; label: 5.3.1
title: Maintaining a Sorted List
pagenum: 142; label: 5.3.2
title: Merging Sorted Lists
pagenum: 143; label: 5.4
title: The Set ADT Revisited
pagenum: 147; label: 5.4.1
title: A Sorted List Implementation
pagenum: 147; label: 5.4.2
title: Comparing the Implementations
pagenum: 152; title: Exercises
pagenum: 152; title: Programming Projects
pagenum: 153; label: Chapter 6
title: Linked Structures
pagenum: 155; label: 6.1
title: Introduction
pagenum: 156; label: 6.2
title: The Singly Linked List
pagenum: 159; label: 6.2.1
title: Traversing the Nodes
pagenum: 159; label: 6.2.2
title: Searching for a Node
pagenum: 161; label: 6.2.3
title: Prepending Nodes
pagenum: 162; label: 6.2.4
title: Removing Nodes
pagenum: 163; label: 6.3
title: The Bag ADT Revisited
pagenum: 165; label: 6.3.1
title: A Linked List Implementation
pagenum: 165; label: 6.3.2
title: Comparing Implementations
pagenum: 167; label: 6.3.3
title: Linked List Iterators
pagenum: 168; label: 6.4
title: More Ways to Build a Linked List
pagenum: 169; label: 6.4.1
title: Using a Tail Reference
pagenum: 169; label: 6.4.2
title: The Sorted Linked List
pagenum: 171; label: 6.5
title: The Sparse Matrix Revisited
pagenum: 174; label: 6.5.1
title: An Array of Linked Lists Implementation
pagenum: 175; label: 6.5.2
title: Comparing the Implementations
pagenum: 178; label: 6.6
title: Application: Polynomials
pagenum: 179; label: 6.6.1
title: Polynomial Operations
pagenum: 179; label: 6.6.2
title: The Polynomial ADT
pagenum: 181; label: 6.6.3
title: Implementation
pagenum: 181; title: Exercises
pagenum: 189; title: Programming Projects
pagenum: 190; label: Chapter 7
title: Stacks
pagenum: 193; label: 7.1
title: The Stack ADT
pagenum: 193; label: 7.2
title: Implementing the Stack
pagenum: 195; label: 7.2.1
title: Using a Python List
pagenum: 195; label: 7.2.2
title: Using a Linked List
pagenum: 196; label: 7.3
title: Stack Applications
pagenum: 198; label: 7.3.1
title: Balanced Delimiters
pagenum: 199; label: 7.3.2
title: Evaluating Postfix Expressions
pagenum: 202; label: 7.4
title: Application: Solving a Maze
pagenum: 206; label: 7.4.1
title: Backtracking
pagenum: 207; label: 7.4.2
title: Designing a Solution
pagenum: 208; label: 7.4.3
title: The Maze ADT
pagenum: 211; label: 7.4.4
title: Implementation
pagenum: 214; title: Exercises
pagenum: 218; title: Programming Projects
pagenum: 219; label: Chapter 8
title: Queues
pagenum: 221; label: 8.1
title: The Queue ADT
pagenum: 221; label: 8.2
title: Implementing the Queue
pagenum: 222; label: 8.2.1
title: Using a Python List
pagenum: 222; label: 8.2.2
title: Using a Circular Array
pagenum: 224; label: 8.2.3
title: Using a Linked List
pagenum: 228; label: 8.3
title: Priority Queues
pagenum: 230; label: 8.3.1
title: The Priority Queue ADT
pagenum: 230; label: 8.3.2
title: Implementation: Unbounded Priority Queue
pagenum: 232; label: 8.3.3
title: Implementation: Bounded Priority Queue
pagenum: 235; label: 8.4
title: Application: Computer Simulations
pagenum: 237; label: 8.4.1
title: Airline Ticket Counter
pagenum: 237; label: 8.4.2
title: Implementation
pagenum: 239; title: Exercises
pagenum: 244; title: Programming Projects
pagenum: 246; label: Chapter 9
title: Advanced Linked Lists
pagenum: 247; label: 9.1
title: The Doubly Linked List
pagenum: 247; label: 9.1.1
title: Organization
pagenum: 247; label: 9.1.2
title: List Operations
pagenum: 248; label: 9.2
title: The Circular Linked List
pagenum: 253; label: 9.2.1
title: Organization
pagenum: 253; label: 9.2.2
title: List Operations
pagenum: 254; label: 9.3
title: Multi-Linked Lists
pagenum: 259; label: 9.3.1
title: Multiple Chains
pagenum: 259; label: 9.3.2
title: The Sparse Matrix
pagenum: 260; label: 9.4
title: Complex Iterators
pagenum: 262; label: 9.5
title: Application: Text Editor
pagenum: 263; label: 9.5.1
title: Typical Editor Operations
pagenum: 263; label: 9.5.2
title: The Edit Buffer ADT
pagenum: 266; label: 9.5.3
title: Implementation
pagenum: 268; title: Exercises
pagenum: 275; title: Programming Projects
pagenum: 275; label: Chapter 10
title: Recursion
pagenum: 277; label: 10.1
title: Recursive Functions
pagenum: 277; label: 10.2
title: Properties of Recursion
pagenum: 279; label: 10.2.1
title: Factorials
pagenum: 280; label: 10.2.2
title: Recursive Call Trees
pagenum: 281; label: 10.2.3
title: The Fibonacci Sequence
pagenum: 283; label: 10.3
title: How Recursion Works
pagenum: 283; label: 10.3.1
title: The Run Time Stack
pagenum: 284; label: 10.3.2
title: Using a Software Stack
pagenum: 286; label: 10.3.3
title: Tail Recursion
pagenum: 289; label: 10.4
title: Recursive Applications
pagenum: 290; label: 10.4.1
title: Recursive Binary Search
pagenum: 290; label: 10.4.2
title: Towers of Hanoi
pagenum: 292; label: 10.4.3
title: Exponential Operation
pagenum: 296; label: 10.4.4
title: Playing Tic-Tac-Toe
pagenum: 297; label: 10.5
title: Application: The Eight-Queens Problem
pagenum: 299; label: 10.5.1
title: Solving for Four-Queens
pagenum: 301; label: 10.5.2
title: Designing a Solution
pagenum: 303; title: Exercises
pagenum: 307; title: Programming Projects
pagenum: 308; label: Chapter 11
title: Hash Tables
pagenum: 309; label: 11.1
title: Introduction
pagenum: 309; label: 11.2
title: Hashing
pagenum: 311; label: 11.2.1
title: Linear Probing
pagenum: 312; label: 11.2.2
title: Clustering
pagenum: 315; label: 11.2.3
title: Rehashing
pagenum: 318; label: 11.2.4
title: Efficiency Analysis
pagenum: 320; label: 11.3
title: Separate Chaining
pagenum: 322; label: 11.4
title: Hash Functions
pagenum: 323; label: 11.5
title: The HashMap Abstract Data Type
pagenum: 325; label: 11.6
title: Application: Histograms
pagenum: 330; label: 11.6.1
title: The Histogram Abstract Data Type
pagenum: 330; label: 11.6.2
title: The Color Histogram
pagenum: 334; title: Exercises
pagenum: 337; title: Programming Projects
pagenum: 338; label: Chapter 12
title: Advanced Sorting
pagenum: 339; label: 12.1
title: Merge Sort
pagenum: 339; label: 12.1.1
title: Algorithm Description
pagenum: 340; label: 12.1.2
title: Basic Implementation
pagenum: 340; label: 12.1.3
title: Improved Implementation
pagenum: 342; label: 12.1.4
title: Efficiency Analysis
pagenum: 345; label: 12.2
title: Quick Sort
pagenum: 347; label: 12.2.1
title: Algorithm Description
pagenum: 348; label: 12.2.2
title: Implementation
pagenum: 349; label: 12.2.3
title: Efficiency Analysis
pagenum: 353; label: 12.3
title: How Fast Can We Sort?
pagenum: 353; label: 12.4
title: Radix Sort
pagenum: 354; label: 12.4.1
title: Algorithm Description
pagenum: 354; label: 12.4.2
title: Basic Implementation
pagenum: 356; label: 12.4.3
title: Efficiency Analysis
pagenum: 358; label: 12.5
title: Sorting Linked Lists
pagenum: 358; label: 12.5.1
title: Insertion Sort
pagenum: 359; label: 12.5.2
title: Merge Sort
pagenum: 362; title: Exercises
pagenum: 367; title: Programming Projects
pagenum: 368; label: Chapter 13
title: Binary Trees
pagenum: 369; label: 13.1
title: The Tree Structure
pagenum: 369; label: 13.2
title: The Binary Tree
pagenum: 373; label: 13.2.1
title: Properties
pagenum: 373; label: 13.2.2
title: Implementation
pagenum: 375; label: 13.2.3
title: Tree Traversals
pagenum: 376; label: 13.3
title: Expression Trees
pagenum: 380; label: 13.3.1
title: Expression Tree Abstract Data Type
pagenum: 382; label: 13.3.2
title: String Representation
pagenum: 383; label: 13.3.3
title: Tree Evaluation
pagenum: 384; label: 13.3.4
title: Tree Construction
pagenum: 386; label: 13.4
title: Heaps
pagenum: 390; label: 13.4.1
title: Definition
pagenum: 391; label: 13.4.2
title: Implementation
pagenum: 395; label: 13.4.3
title: The Priority Queue Revisited
pagenum: 398; label: 13.5
title: Heapsort
pagenum: 400; label: 13.5.1
title: Simple Implementation
pagenum: 400; label: 13.5.2
title: Sorting In Place
pagenum: 400; label: 13.6
title: Application: Morse Code
pagenum: 404; label: 13.6.1
title: Decision Trees
pagenum: 405; label: 13.6.2
title: The ADT Definition
pagenum: 406; title: Exercises
pagenum: 407; title: Programming Projects
pagenum: 410; label: Chapter 14
title: Search Trees
pagenum: 411; label: 14.1
title: The Binary Search Tree
pagenum: 412; label: 14.1.1
title: Searching
pagenum: 413; label: 14.1.2
title: Min and Max Values
pagenum: 415; label: 14.1.3
title: Insertions
pagenum: 417; label: 14.1.4
title: Deletions
pagenum: 420; label: 14.1.5
title: Efficiency of Binary Search Trees
pagenum: 425; label: 14.2
title: Search Tree Iterators
pagenum: 427; label: 14.3
title: AVL Trees
pagenum: 428; label: 14.3.1
title: Insertions
pagenum: 430; label: 14.3.2
title: Deletions
pagenum: 433; label: 14.3.3
title: Implementation
pagenum: 435; label: 14.4
title: The 2-3 Tree
pagenum: 440; label: 14.4.1
title: Searching
pagenum: 442; label: 14.4.2
title: Insertions
pagenum: 443; label: 14.4.3
title: Efficiency of the 2-3 Tree
pagenum: 449; title: Exercises
pagenum: 451; title: Programming Projects
pagenum: 452; label: Appendix A
title: Python Review
pagenum: 453; label: A.1
title: The Python Interpreter
pagenum: 453; label: A.2
title: The Basics of Python
pagenum: 454; label: A.2.1
title: Primitive Types
pagenum: 455; label: A.2.2
title: Statements
pagenum: 456; label: A.2.3
title: Variables
pagenum: 457; label: A.2.4
title: Arithmetic Operators
pagenum: 458; label: A.2.5
title: Logical Expressions
pagenum: 459; label: A.2.6
title: Using Functions and Methods
pagenum: 461; label: A.2.7
title: Standard Library
pagenum: 462; label: A.3
title: User Interaction
pagenum: 463; label: A.3.1
title: Standard Input
pagenum: 463; label: A.3.2
title: Standard Output
pagenum: 464; label: A.4
title: Control Structures
pagenum: 467; label: A.4.1
title: Selection Constructs
pagenum: 467; label: A.4.2
title: Repetition Constructs
pagenum: 469; label: A.5
title: Collections
pagenum: 472; label: A.5.1
title: Strings
pagenum: 472; label: A.5.2
title: Lists
pagenum: 473; label: A.5.3
title: Tuples
pagenum: 475; label: A.5.4
title: Dictionaries
pagenum: 475; label: A.6
title: Text Files
pagenum: 477; label: A.6.1
title: File Access
pagenum: 477; label: A.6.2
title: Writing to Files
pagenum: 478; label: A.6.3
title: Reading from Files
pagenum: 479; label: A.7
title: User-Defined Functions
pagenum: 480; label: A.7.1
title: The Function Definition
pagenum: 480; label: A.7.2
title: Variable Scope
pagenum: 483; label: A.7.3
title: Main Routine
pagenum: 483; label: Appendix B
title: User-Defined Modules
pagenum: 485; label: B.1
title: Structured Programs
pagenum: 485; label: B.2
title: Namespaces
pagenum: 486; label: Appendix C
title: Exceptions
pagenum: 489; label: C.1
title: Catching Exceptions
pagenum: 489; label: C.2
title: Raising Exceptions
pagenum: 490; label: C.3
title: Standard Exceptions
pagenum: 491; label: C.4
title: Assertions
pagenum: 491; label: Appendix D
title: Classes
pagenum: 493; label: D.1
title: The Class Definition
pagenum: 493; label: D.1.1
title: Constructors
pagenum: 494; label: D.1.2
title: Operations
pagenum: 495; label: D.1.3
title: Using Modules
pagenum: 497; label: D.1.4
title: Hiding Attributes
pagenum: 498; label: D.2
title: Overloading Operators
pagenum: 500; label: D.3
title: Inheritance
pagenum: 502; label: D.3.1
title: Deriving Child Classes
pagenum: 503; label: D.3.2
title: Creating Class Instances
pagenum: 504; label: D.3.3
title: Invoking Methods
pagenum: 505; label: D.4
title: Polymorphism
pagenum: 507