What is this Book?
Learn Data Structures and Algorithms! This book is a collection of lectures notes on Data Structures and Algorithms. The content found in this book supplements the free video lecture series, of the same name, "Advanced Data Structures", by the author. This video lecture series is available at http://www.pagewizardgames.com/datastructures. This book:
- Contains Computer Science topics and materials comparable to those found among university courses at a similar level (second-year) at top Canadian universities.
- Provides an accessible written companion and supplemental notes for those that wish to learn the subject of Data Structures and Algorithms from the video lecture series, but have difficulties taking notes, or would prefer having a written alternative to follow along.
This book is ideal for those with already an introductory programming background, know a little bit about computing, and wish to learn more about Data Structures and Algorithms and begin a more formal study of Computer Science. The materials here are a great place to start for supplemental/additional learning materials on the subject for self-study, university students, or those that want to learn more about Computer Science.
Dr. Daniel Page places great emphasis on the introductory mathematical aspects of Computer Science, a natural transition from a basic programming background to thinking a bit more like a computer scientist about Computer Science.
This book is not a textbook. The author assumes the reader is familiar with algebra, functions, common finite and infinite series such as arithmetic series and geometric series, and basic control structures in programming or logic. All the algorithms in this book are described in English, or using Java-like pseudocode.
- Chapter 1 - Introduction: Data Structures, Problems, Input Size, Algorithms, The Search Problem.
- Chapter 2 - Intro to Analysis of Algorithms I: Complexity Analysis, Comparing Algorithms, Growth Rate of Functions (Asymptotics), Showing f is O(g), Showing f is not O(g).
- Chapter 3 - Intro to Analysis of Algorithms II: Some Properties of O, An Iterative Example, Back to our "Easy" Search Problem.
- Chapter 4 - Dictionaries: The Dictionary Problem, Simple Implementations of a Dictionary.
- Chapter 5 - Hashing: Hash Function, Hash Code, Separate Chaining, Open Addressing, Revisiting the Load Factor.
- Chapter 6 - Trees: Tree ADT, Linked Tree Representation, Tree Property, Computing Height of a Tree, Tree Traversals
- Chapter 7 - Priority Queues & Heaps: Priority Queues, Heaps, Array-Based Implementation, Building a Heap, Application: Sorting, Introduction to Amortized Analysis
- Chapter 8 - Binary Search Trees: Ordered Dictionary ADT, BST Implementations, Inorder Traversal, Smallest, Get, Put, Remove, Successor.
- Chapter 9 - AVL Trees: Height, AVL Trees, Re-Balancing AVL Trees, putAVL, removeAVL, AVL Tree Performance.
- Chapter 10 - Graphs: Degrees and the Handshaking Lemma, Complete Graphs, Paths and Cycles, Trees, Forests, Subgraphs, and Connectivity, Graph Representations.
- Chapter 11 - Graph Traversals: Depth-First Search (DFS), Path-Finding, Cycle Detection, Counting Vertices, DFS Tree, Breadth-First Search (BFS), Summary.
- Chapter 12 - Minimum Spanning Trees: Weighted Graphs, Minimum Spanning Trees & Algorithms, Prim's Algorithm, Heap-Based Implementation of Prim's Algorithm and More!
- Chapter 13 - Shortest Paths: Single-Source Shortest Path Problem, Dijkstra's Algorithm.
- Chapter 14 - Multiway Search Trees: Beyond Binary Search Trees, Get, Put, Successor and Remove, (2,4)-Trees, B-Trees.
All corrections/bugs/typos and remarks to supplement the book can be found here.
- *On cover page: The page number for "How to Use This Book" is on Page 2, it may state Page 3; in earlier versions of the book it was on Page 3.
- *On the copyright page in some early prints of the book (Page 1): It refers to Page 3 for reference to the name YouTube, this in fact occurs on Page 2 of the book.
- *Page 94, about middle of page (AVL Trees, Re-Balancing AVL Trees): Figure 9.3, should be Figure 9.2.
- *Page 73, heapify pseudocode, first line of pseudocode: On line one of the pseudocode for heapify, it was incorrectly typed that the position of the parent in the last position is the floor of (n-1)/2, it is actually the floor of (n-2)/2. This is because, of course the final position in the array is n-1, and of course computing the parent of a node is its position less one divided by two (rounded down, floor).
- *Page 130, first version of Prim's Algorithm pseudocode: On the outermost loop, it says "i -> i", it should read "i -> 1". In addition, the comment on the line where a vertex u_min is marked afterwards is incorrect. Removed "(this line is not necessary)". This comment is correct in the 2nd version of Prim's Algorithm, the typo in the first version of the pseudocode is an artifact of the 2nd version's pseudocode.
All Items marked with * have already been addressed in updated versions of the book; however, this listing serves as a comprehensive record should you encounter any corrections/bugs/typos.
Please send any errors/bugs/typos to email@example.com, such will be updated on this site.
For any general questions, you may contact the author at firstname.lastname@example.org.
ISBN (eBook): 978777407506
Pages: 160 pages
If cited or referenced, please cite as, per appropriate format:
Page, D.R. Advanced Data Structures: An Introduction to Data Structures and Algorithms. PageWizard Games, Learning & Entertainment, 2020.