Textbook

# Data Structures and Algorithms Using Python

This book is designed for a CS2 course that uses Python. A key objective is to provide a back to basics approach to learning data structures and algorithms without overwhelming the reader with all of the OOP terminology and concepts. To provide flexibility in topic coverage for a wide variety of courses, the author focuses on data structures and algorithms, while designing the examples to allow the introduction of object-oriented programming if so desired. The book also introduces the concept of algorithm analysis and explores the efficiency of algorithms and data structures throughout the text.
Create a customized edition with Wiley Custom Select
Preface.

Chapter 1: Abstract Data Types.

1.1 Introduction.

1.2 The Date Abstract Data Type.

1.3 Bags.

1.4 Iterators.

1.5 Application: Student Records.

Exercises.

Programming Projects.

Chapter 2: Arrays.

2.1 The Array Structure.

2.2 The Python List.

2.3 Two-Dimensional Arrays.

2.4 The Matrix Abstract Data Type.

2.5 Application: The Game of Life.

Exercises.

Programming Projects.

Chapter 3: Sets and Maps.

3.1 Sets.

3.2 Maps.

3.3 Multi-Dimensional Arrays.

3.4 Application: Sales Reports.

Exercises.

Programming Projects.

Chapter 4: Algorithm Analysis.

4.1 Complexity Analysis.

4.2 Evaluating the Python List.

4.3 Amortized Cost.

4.5 Application: The Sparse Matrix.

Exercises.

Programming Projects.

Chapter 5: Searching and Sorting.

5.1 Searching.

5.2 Sorting.

5.3 Working with Sorted Lists.

Exercises.

Programming Projects.

6.1 Introduction.

6.4 More Ways to Build a Linked List.

6.5 The Sparse Matrix Revisited.

6.6 Application: Polynomials.

Exercises.

Programming Projects.

Chapter 7: Stacks.

7.2 Implementing the Stack.

7.3 Stack Applications.

7.4 Application: Solving a Maze.

Exercises.

Programming Projects.

Chapter 8: Queues.

8.2 Implementing the Queue.

8.3 Priority Queues.

8.4 Application: Computer Simulations.

Exercises.

Programming Projects.

9.4 Complex Iterators.

9.5 Application: Text Editor.

Exercises.

Programming Projects.

Chapter 10: Recursion.

10.1 Recursive Functions.

10.2 Properties of Recursion.

10.3 How Recursion Works.

10.4 Recursive Applications.

10.5 Application: The Eight-Queens Problem.

Exercises.

Programming Projects.

Chapter 11: Hash Tables.

11.1 Introduction.

11.2 Hashing.

11.3 Separate Chaining.

11.4 Hash Functions.

11.5 The HashMap Abstract Data Type.

11.6 Application: Histograms.

Exercises.

Programming Projects.

12.1 Merge Sort.

12.2 Quick Sort.

12.3 How Fast Can We Sort?

Exercises.

Programming Projects.

Chapter 13: Binary Trees.

13.1 The Tree Structure.

13.2 The Binary Tree.

13.3 Expression Trees.

13.4 Heaps.

13.5 Heapsort.

13.6 Application: Morse Code.

Exercises.

Programming Projects.

Chapter 14: Search Trees.

14.1 The Binary Search Tree.

14.2 Search Tree Iterators.

14.3 AVL Trees.

14.4 The 2-3 Tree.

Exercises.

Programming Projects.

Appendix A Python Review.

A.1 The Python Interpreter.

A.2 The Basics of Python.

A.3 User Interaction.

A.4 Control Structures.

A.5 Collections.

A.6 Text Files.

A.7 User-Defined Functions.

Appendix B User-Defined Modules.

B.1 Structured Programs.

B.2 Namespaces.

Appendix C Exceptions.

C.1 Catching Exceptions.

C.2 Raising Exceptions.

C.3 Standard Exceptions.

C.4 Assertions.

Appendix D Classes.

D.1 The Class Definition.

D.3 Inheritance.

D.4 Polymorphism.

Hallmark Features
• Provides complete coverage of abstraction and the basic data structures and algorithms using a back to basics approach.
• Python (version 3) used to design and implement classes for abstract data types and programs and algorithms.
• Flexible organization allows coverage of class inheritance as needed or desired.
• Introduces students to the basic array structure and the fundamentals of implementing and using multi-dimensional arrays.
• The underlying mechanism of many of Python's built-in data structures and constructs are explored in order to expose the magic and to evaluate their efficiency.
• Real-world applications of various chapter topics are presented throughout the text to help engage students.
• A number of ADTs and applications are presented as threads throughout the text (i.e. the Set, Bag, Matrix, Sparse Matrix, and Map ADTs.) This allows for multiple implementations as new data structures are introduced, which provides the opportunity to reinforce the abstraction concept and for studying algorithm efficiency.

## Available Versions

Data Structures and Algorithms Using Python
by Rance D. Necaise
ISBN 978-0-470-61829-5