Data Structures and Algorithms in Python (An Indian Adaptation)

Description

Data Structures and Algorithms in Python offers a comprehensive, definitive introduction to data structures and algorithms, including their design, analysis, and implementation in Python. Utilizing a consistent object-oriented viewpoint throughout the book, it provides detailed algorithmic strategies for producing efficient realizations of common data structures such as arrays, stacks, queues, linked lists, trees, maps, hash tables, search trees, and graphs. The book also provides an in-depth analysis of algorithmic performance that helps readers to recognize common trade-offs between competing strategies. The book incorporates a host of pedagogical features, including illustrations, code fragments, and end-of-chapter exercises.

About the Author

Michael T. Goodrich is a Chancellor’s Professor in the Department of Computer Science at University of California, Irvine. Previously, he was a professor at Johns Hopkins University. His research interests include analysis, design, and implementation of algorithms, data security, cloud computing, graph drawing, and computational geometry. He is a Fulbright scholar and a fellow of the American Association for the Advancement of Science (AAAS), Association for Computing Machinery (ACM), and Institute of Electrical and Electronics Engineers (IEEE).

Roberto Tamassia is the Plastech Professor of Computer Science in the Department of Computer Science at Brown University. He is also the Director of Brown’s Center for Geometric Computing. His research interests include data security, applied cryptography, cloud computing, analysis, design, and implementation of algorithms, graph drawing, and computational geometry. He is a fellow of the American Association for the Advancement of Science (AAAS), Association for Computing Machinery (ACM), and Institute of Electrical and Electronics Engineers (IEEE).

Michael Goldwasser is currently a Professor in the Department of Mathematics and Computer Science at Saint Louis University and the Director of their Computer Science program. Previously, he was a faculty member in the Department of Computer Science at Loyola University Chicago. His research interests focus on the design and implementation of algorithms, having published work involving approximation algorithms, online computation, computational biology, and computational geometry. He is also active in the computer science education community.

Table of Contents

Book Review

Chapter 1 Introduction to Python

1.1 Python Overview

1.2 Objects in Python

1.3 Expressions, Operators, and Precedence

1.4 Control Flow

1.5 Functions

1.6 Simple Input and Output

1.7 Exception Handling

1.8 Iterators and Generators

1.9 Additional Python Conveniences

1.10 Scopes and Namespaces

1.11 Modules and the Import Statement

Chapter 2 Object-Oriented Programming

2.1 Goals, Principles, and Patterns

2.2 Software Development

2.3 Class Definitions

2.4 Inheritance

2.5 Namespaces and Object-Orientation

2.6 Shallow and Deep Copying

Chapter 3 Introduction to Data Structures and Algorithms

3.1 Data Structures

3.2 Experimental Studies

3.3 The Seven Functions Used in this Book

3.4 Analysis of Algorithms

3.5 Simple Justification Techniques

Chapter 4 Recursion

4.1 Examples Illustrating Recursion

4.2 Analyzing Recursive Algorithms

4.3 Further Examples of Recursion

4.4 Designing Recursive Algorithms

4.5 Eliminating Tail Recursion

Chapter 5 Array-Based Sequences

5.1 Python’s Sequence Types

5.2 Low-Level Arrays

5.3 Dynamic Arrays and Amortization

5.4 Efficiency of Python’s Sequence Types

5.5 Using Array-Based Sequences

5.6 Multidimensional Data Sets

Chapter 6 Stacks

6.1 Stacks

6.2 The Stack Abstract Data Type

6.3 Simple Array-Based Stack Implementation

Chapter 7 Queues

7.1 Queues

7.2 The Queue Abstract Data Type

7.3 Array-Based Queue Implementation

7.4 Double-Ended Queues

7.5 Circular Queues

Chapter 8 Linked Lists

8.1 Singly Linked Lists

8.2 Circularly Linked Lists

8.3 Doubly Linked Lists

8.4 The Positional List ADT

8.5 Sorting a Positional List

8.6 Link-Based vs. Array-Based Sequences

Chapter 9 Trees

9.1 General Trees

9.2 Binary Trees

9.3 Implementing Trees

9.4 Tree Traversal Algorithms

9.5 Case Study: An Expression Tree

Chapter 10 Priority Queues

10.1 The Priority Queue Abstract Data Type

10.2 Implementing a Priority Queue

10.3 Heaps

10.4 Adaptable Priority Queues

Chapter 11 Maps, Hash Tables, and Sets

11.1 Maps and Dictionaries

11.2 Hash Tables

11.3 Sorted Maps

11.4 Sets, Multisets, and Multimaps

Chapter 12 Search Trees

12.1 Binary Search Trees

12.2 Balanced Search Trees

12.3 AVL Trees

12.4 Splay Trees

12.5 (2, 4) Trees

12.6 Red-Black Trees

Chapter 13 Sorting Algorithms

13.1 Why Study Sorting Algorithms?

13.2 Merge-Sort

13.3 Quick-Sort

13.4 Studying Sorting through an Algorithmic Lens

13.5 Sorting with a Priority Queue

13.6 Comparing Sorting Algorithms

13.7 Python’s Built-In Sorting Functions

Chapter 14 Graph Algorithms

14.1 Graphs

14.2 Data Structures for Graphs

14.3 Graph Traversals

14.4 Transitive Closure

14.5 Directed Acyclic Graphs

14.6 Shortest Paths

14.7 Minimum Spanning Trees

Chapter 15 Text Processing

15.1 Abundance of Digitized Text

15.2 Pattern-Matching Algorithms

15.3 Dynamic Programming

15.4 Text Compression and the Greedy Method

15.5 Tries

Chapter 16 Memory Management and B-Trees

16.1 Memory Management

16.2 Memory Hierarchies and Caching

16.3 External Searching and B-Trees

16.4 External-Memory Sorting

Illustrative Examples and Programs

Exercises

Multiple Choice Questions

Chapter Notes

Answers to Multiple Choice Questions

Appendix A Character Strings in Python

Appendix B Useful Mathematical Facts

Appendix C Additional Searching and Sorting Algorithms

Bibliography

Index