Advanced Data Structures
An Introduction to Data Structures and Algorithms

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.