zyBook - Data Structures Essentials

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 Algorithms Analysis

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

3. Sorting Algorithms

3.1 Sorting: Introduction
3.2 Selection sort
3.3 Insertion sort
3.4 Shell sort
3.5 Quicksort
3.6 Merge sort
3.7 Radix sort
3.8 Overview of fast sorting algorithms

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 Doubly-linked lists
4.7 Doubly-linked lists: Insert
4.8 Doubly-linked lists: Remove
4.9 Linked list traversal
4.10 Sorting linked lists
4.11 Linked list dummy nodes
4.12 Stack abstract data type (ADT)
4.13 Stacks using linked lists
4.14 Queue abstract data type (ADT)
4.15 Linked lists: Recursion
4.16 Deque abstract data type (ADT)
4.17 Array-based lists

5. Hash Tables

5.1 Hash tables
5.2 Chaining
5.3 Linear probing
5.4 Quadratic hashing
5.5 Double hashing
5.6 Hash table resizing
5.7 Direct hashing
5.8 Hashing Algorithms: Cryptography, Password Hashing

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

7. Balanced Trees

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

8. Heaps and Treaps

8.1 Heaps
8.2 Heaps using arrays
8.3 Heap sort
8.4 Priority queue abstract data type (ADT)
8.5 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.9 Weighted graphs
9.9 Algorithm: Dijkstra's shortest path
9.10 Algorithm: Bellman-Ford's shortest path
9.11 Topological sort
9.12 Minimum spanning tree
9.13 All pairs shortest path

10. Algorithms

10.1 Heuristics
10.2 Greedy algorithms
10.3 Dynamic programming

11. B-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

12. Sets

12.1 Set abstract data type
12.2 Set operations
12.3 Static and dynamic set operations

13. Additional Material

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

What You'll Find In This zyBook:

More action with less text.

  • Emphasizes essential data structures and algorithms
  • Animations and tools are an excellent match for teaching data structures
  • Language-independent pseudocode for data structures to ensure mastery of the fundamental concepts
  • This zyBook also features highly visual content, bringing the world of data structures to life

The zyBooks Approach

Less text doesn't mean less learning.

Provides an introduction to the basics of algorithms and data structures, illustrating the "science" of computing. Mastery of these concepts is part of the foundation of the discipline of computing, leading to computing professionals as distinct from programmers. This zyBook uses pseudocode to ensure the reader masters the fundamental concepts that apply to all programming languages. This zyBook is well suited for a first course in data structures and algorithms.

"I have now been asked to teach Discrete Mathematics again … because of my past experience with zyBooks I agreed to teach this topic again only if I could use the zyBook again."

Authors

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

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