Table of Contents

1. Introduction to Data Structures and Algorithms

1.1 Data structures
1.2 Introduction to algorithms
1.3 Relation between data structures and algorithms
1.4 Abstract data types
1.5 Applications of ADTs
1.6 Algorithm efficiency

2. Searching and Algorithm Analysis

2.1 Searching and algorithms
2.2 Binary search
2.3 Python: Linear and binary search
2.4 Constant time operations
2.5 Growth of functions and complexity
2.6 O notation
2.7 Algorithm analysis
2.8 Recursive definitions
2.9 Recursive algorithms
2.10 Analyzing the time complexity of recursive algorithms

3. Sorting Algorithms

3.1 Sorting: Introduction
3.2 Selection sort
3.3 Python: Selection sort
3.4 Insertion sort
3.5 Python: Insertion sort
3.6 Shell sort
3.7 Python: Shell sort
3.8 Quicksort
3.9 Python: Quicksort
3.10 Merge sort
3.11 Python: Merge sort
3.12 Radix sort
3.13 Python: Radix sort
3.14 Overview of fast sorting algorithms
3.15 Python: Sorting with different operators

4. Lists, Stacks, and Queues

4.1 List abstract data type (ADT)
4.2 Singly-linked lists
4.3 Singly-linked lists: Insert
4.4 Singly-linked lists: Remove
4.5 Linked list search
4.6 Python: Singly-linked lists
4.7 Doubly-linked lists
4.8 Doubly-linked lists: Insert
4.9 Doubly-linked lists: Remove
4.10 Python: Doubly-linked lists
4.11 Linked list traversal
4.12 Sorting linked lists
4.13 Python: Sorting linked lists
4.14 Linked list dummy nodes
4.15 Linked lists: Recursion
4.16 Stack abstract data type (ADT)
4.17 Stacks using linked lists
4.18 Queue abstract data type (ADT)
4.19 Queues using linked lists
4.20 Python: Stacks and queues
4.21 Deque abstract data type (ADT)
4.22 Array-based lists
4.23 Python: Array-based list

5. Hash Tables

5.1 Hash tables
5.2 Chaining
5.3 Linear probing
5.4 Quadratic probing
5.5 Double hashing
5.6 Hash table resizing
5.7 Common hash functions
5.8 Direct hashing
5.9 Hashing algorithms: Cryptography, password hashing
5.10 Python: Hash tables
5.11 Python: Quadratic probing

6. Trees

6.1 Binary trees
6.2 Applications of trees
6.3 Binary search trees
6.4 BST search algorithm
6.5 BST insert algorithm
6.6 BST remove algorithm
6.7 BST inorder traversal
6.8 BST height and insertion order
6.9 BST parent node pointers
6.10 BST: Recursion
6.11 Python: Binary search tree

7. Balanced Trees

7.1 AVL: A balanced tree
7.2 AVL rotations
7.3 AVL insertions
7.4 AVL removals
7.5 Python: AVL Trees
7.6 Red-black tree: A balanced tree
7.7 Red-black tree: Rotations
7.8 Red-black tree: Insertion
7.9 Red-black tree: Removal
7.10 Python: Red-black trees

8. Heads and Treaps

8.1 Heaps
8.2 Heaps using arrays
8.3 Python: Heaps
8.4 Heap sort
8.5 Python: Heap sort
8.6 Priority queue abstract data type (ADT)
8.7 Treaps

9. Graphs

9.1 Graphs: Introduction
9.2 Applications of graphs
9.3 Graph representations: Adjacency lists
9.4 Graph representations: Adjacency matrices
9.5 Graphs: Breadth-first search
9.6 Graphs: Depth-first search
9.7 Directed graphs
9.8 Weighted graphs
9.9 Python: Graphs
9.10 Python: Breadth-first search
9.11 Python: Depth-first search
9.12 Algorithm: Dijkstra’s shortest path
9.13 Python: Dijkstra’s shortest path
9.14 Algorithm: Bellman-Ford’s shortest path
9.15 Python: Bellman-Ford’s shortest path
9.16 Topological sort
9.17 Python: Topological sort
9.18 Minimum spanning tree
9.19 Python: Minimum spanning tree
9.20 All pairs shortest path
9.21 Python: All pairs shortest path

10. Algorithms

10.1 Heuristics
10.2 Python: Heuristics
10.3 Greedy algorithms
10.4 Python: Greedy algorithms
10.5 Dynamic programming
10.6 Python: Dynamic programming

11. Trees

11.1 B-trees
11.2 2-3-4 tree search algorithm
11.3 2-3-4 tree insert algorithm
11.4 2-3-4 tree rotations and fusion
11.5 2-3-4 tree removal
11.6 Python: 2-3-4 trees

12. Sets

12.1 Set abstract data type
12.2 Set operations
12.3 Static and dynamic set operations
12.4 Python: Set implementation

13. Additional Material

13.1 Bubble sort
13.2 Quickselect
13.3 Python: Quickselect
13.4 Bucket sort
13.5 List data structure
13.6 Circular lists

What You’ll Find In This zyBook:

More action with less text.

This zyBook uses pseudocode to teach essential data structures and algorithms to help the reader master the fundamental concepts. Python-specific sections are also included, providing Python implementations of many of the data structures and algorithms

Instructors: Interested in evaluating this zyBook for your class? Sign up for a Free Trial and check out the first chapter of any zyBook today!

The zyBooks Approach

Less text doesn’t mean less learning.

Studying data structures and algorithms often represents a person’s first study of the “science” of computing, beyond just programming. Mastery of these concepts is part of the foundation of the discipline of computing, leading to computing professionals as distinct from programmers.

Data structures is an extremely visual subject, forming an excellent match for the extensive use of animations that typifies a zyBook. Embedded learning questions help the reader understand and remember concepts.

The content is maximally modular to enable configuration by instructors. Instructors can rearrange sections, set sections as optional, add instructor’s notes to sections, and more. This zyBook can also be mixed-and-matched with others, such as with the Programming in Python zyBook; contact sales@zybooks.com for information.

“It is already clear that this represents the future of programming text books. Its basic expository content is the equal of any paper text, but it really shines in using the natural advantages of online vs. static teaching material ­ animation and interactivity ­ to excellent effect, giving the student an additional dimension of insight.”

Brian LinardLecturer, UC Riverside

Authors

Roman Lysecky
Professor of Electrical and Computer Engineering, Univ. of Arizona

Frank Vahid
Professor of Computer Science and Engineering, Univ. of California, Riverside

Combine Data Structures Essentials Python With These Other zyBooks

DSE Python is often combined with other zyBooks to give students experience with a diverse set of programming languages. Some popular titles to pair include: