# Advanced Data Structures An Introduction to Data Structures and Algorithms

Frontmatter Preview
Order The Book!

The book is available to be purchased in various formats:

Digital Formats:

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.

### Chapters

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

All the video lectures can be located here: http://www.pagewizardgames.com/datastructures

For more free or accessible educational content, subscribe to
PageWizard Games, Learning & Entertainment!

Contact

For general questions to the author: drpage@pagewizardgames.com

For questions involving permissions for use of book or for licensing, or to report errors/bugs/typos: gle@pagewizardgames.com

Errata/Questions

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 31, Figure 3.1: Top picture, the result for computing mid should be 4, not 2.
• *Page 38, around the bottom of the page (Simple Implementations of a Dictionary): "...just create a node with the record and insert the front of the list." -> "...just create a node and insert it at the front of the list."
• *Page 56, Figure 5.6: Index 7 is not labelled on the table, this has been added.
• *Page 56, last paragraph before Revisiting the Load Factor: "...the divisors of 8 are 1, 2, and 4" -> "...the divisors of 8 are 1, 2, 4, and 8."
• *Page 61, Figure 6.1: You can order the children differently so they read left to right (this is changed).
• *Page 69, last step in Figure 7.3: The array is not updated, it should read in the array (left to right): 3, 6, 5, 7, 10, 12, 8, 14, 22, 18, 17, 15, 13, 11
• *Page 71, Figure 7.4: Index 6 in array should read 11, not 3.
• *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 82: "An ordered dictionary implement..." -> "An ordered dictionary implemented..."
• *Page 94, about middle of page (AVL Trees, Re-Balancing AVL Trees): Figure 9.3, should be Figure 9.2.
• *Page 108, top of page: Rephrase the last bullet to instead: "Note that for any tree, if a new edge is added to it, the induced graph (the graph as a result of the insertion of the new edge) contains a cycle."
• *Page 109, adjacency matrix: When the adjacency matrix is defined, it states (u,v), whereas it should be (i,j).
• *Page 118, beginning of DFS tree: "...in the connected component of vertex v." -> "...in the connected component of vertex u."
• *Page 126, small rephrasing to improve readability: "Consider any weighted connected graph G=(V,E), where V_1 and V_2 are two non-empty sets of the vertices of V with no common vertices (also known as some partition of the vertices V, should the entire graph be considered)." -> "Consider any weighted connected graph G=(V,E), where V_1 and V_2 are two non-empty sets containing the vertices of V with no common vertices (that is, the two sets V_1 and V_2 are some partition of the vertices V). "
• *Page 128, typo fix and small rephrasing to improve readability: "... because it always pick an edge that goes across the cut of two ``clusters'' (each a tree), which then become merged; you can view the two ``clusters'' of vertices to be merged as V_1 and V_2 in the cut-property proof where e is the least weight edge the algorithm uses to merge two ``clusters''." -> "because it always picks an edge e={u,v} that goes across the cut of two ``clusters'' (each a tree), which then become merged. Furthermore, edge e is the next least weight edge over the entire graph in such a setting, where one of either u or v belongs to V_1 along with vertices in its ``cluster'', and the other endpoint and all other vertices not in that ``cluster'' belong to V_2, crossing a cut as in the cut property."
• *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.
• *Page 132: "...when considering the adjacency matrix representation..." -> "...when considering the adjacency list representation..."
• *Page 132: "Maintain an positional array..." -> "Maintain a positional array..."
• *Page 133, time complexity: extractMin is written, when it should be removeMin.
• *Page 136: "...compute shortest length path from any two vertices..." -> "...it is trivial to compute a shortest length path from vertex s to another vertex t..."
• *Page 141, Figure 14.5: The parent reference/pointer is omitted from this figure, each node has access to its parent.

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 gle@pagewizardgames.com, such will be updated on this site.

For any general questions, you may contact the author at drpage@pagewizardgames.com.

Bibliographic Information

ISBN: 9781777407513
ISBN-10: 1777407516
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.