Advanced Data Structures
An Introduction to Data Structures and Algorithms

by Daniel R. Page


Frontmatter Preview
Order The Book!

The book is available to be purchased in various formats:

Paperback on Amazon: http://mybook.to/advanceddatastructures

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

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.