Skip to main content

Data Structures and Algorithms Using Python

Data Structures and Algorithms Using Python

Rance D. Necaise

ISBN: 978-0-470-61829-5

Jan 2011

540 pages

Select type: Paperback

Out of stock


* VAT information


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.

Related Resources


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.


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.


Programming Projects.

Chapter 3: Sets and Maps.

3.1 Sets.

3.2 Maps.

3.3 Multi-Dimensional Arrays.

3.4 Application: Sales Reports.


Programming Projects.

Chapter 4: Algorithm Analysis.

4.1 Complexity Analysis.

4.2 Evaluating the Python List.

4.3 Amortized Cost.

4.4 Evaluating the Set ADT.

4.5 Application: The Sparse Matrix.


Programming Projects.

Chapter 5: Searching and Sorting.

5.1 Searching.

5.2 Sorting.

5.3 Working with Sorted Lists.

5.4 The Set ADT Revisited.


Programming Projects.

Chapter 6: Linked Structures.

6.1 Introduction.

6.2 The Singly Linked List.

6.3 The Bag ADT Revisited.

6.4 More Ways to Build a Linked List.

6.5 The Sparse Matrix Revisited.

6.6 Application: Polynomials.


Programming Projects.

Chapter 7: Stacks.

7.1 The Stack ADT.

7.2 Implementing the Stack.

7.3 Stack Applications.

7.4 Application: Solving a Maze.


Programming Projects.

Chapter 8: Queues.

8.1 The Queue ADT.

8.2 Implementing the Queue.

8.3 Priority Queues.

8.4 Application: Computer Simulations.


Programming Projects.

Chapter 9: Advanced Linked Lists.

9.1 The Doubly Linked List.

9.2 The Circular Linked List.

9.3 Multi-Linked Lists.

9.4 Complex Iterators.

9.5 Application: Text Editor.


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.


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.


Programming Projects.

Chapter 12: Advanced Sorting.

12.1 Merge Sort.

12.2 Quick Sort.

12.3 How Fast Can We Sort?

12.4 Radix Sort.

12.5 Sorting Linked Lists.


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.


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.


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.2 Overloading Operators.

D.3 Inheritance.

D.4 Polymorphism.

  • 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.