0% found this document useful (0 votes)
18 views10 pages

Dr. Daniel Page's Data Structures Guide

The document is a publication titled 'Advanced Data Structures: An Introduction to Data Structures and Algorithms' by Daniel R. Page, aimed at second-year Computer Science students. It serves as a supplementary resource to Dr. Page's online lecture series, providing notes on fundamental concepts in data structures and algorithms, and is not intended as a comprehensive textbook. The book was published in November 2020 and is available in both eBook and print formats.

Uploaded by

yesudossj
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
18 views10 pages

Dr. Daniel Page's Data Structures Guide

The document is a publication titled 'Advanced Data Structures: An Introduction to Data Structures and Algorithms' by Daniel R. Page, aimed at second-year Computer Science students. It serves as a supplementary resource to Dr. Page's online lecture series, providing notes on fundamental concepts in data structures and algorithms, and is not intended as a comprehensive textbook. The book was published in November 2020 and is available in both eBook and print formats.

Uploaded by

yesudossj
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

See discussions, stats, and author profiles for this publication at: [Link]

net/publication/346473585

Advanced Data Structures: An Introduction to Data Structures and Algorithms

Book · November 2020

CITATIONS READS
0 17,645

1 author:

Daniel R. Page
PageWizard Games Learning & Entertainment
20 PUBLICATIONS 62 CITATIONS

SEE PROFILE

All content following this page was uploaded by Daniel R. Page on 23 January 2021.

The user has requested enhancement of the downloaded file.


Advanced Data Structures

An Introduction to Data Structures and Algorithms

Daniel R. Page

PageWizard Games, Learning & Entertainment


Sunnyside, Manitoba, Canada
1

Copyright Information

This book is notes adapted from the lecturer’s notes of Dr. Daniel Page on the
subject, over various offerings of courses of this nature over various years. In prepara-
tion of these materials, no rights were intended on being infringed and was created for
educational purposes. This is not a textbook, nor intended to be used as a textbook,
it lacks a reference/bibliography section and hence is not meant as a comprehensive
scholarly source on this subject; these are supplemental to Dr. Daniel Page’s lec-
tures discussed on the next page. The name YouTube, as referred to on Page 2, is
not owned by the author, and is owned by Google Inc. Any images not created by
Dr. Daniel Page are in the public domain and were retrieved via [Link]
thus are not credited directly here. This document was created as a written supple-
ment/companion to the lecture notes provided in lecture for a data structures and
algorithms course by Dr. Daniel Page, and a companion to the video-lecture series
discussed on the next page.
No part of this publication is to be sold, reproduced, scanned, freely distributed,
or re-sold, without explicit permission or prior agreement of/with Dr. Daniel Page
(PageWizard Games, Learning & Entertainment); with the exception of actions un-
der the fair dealings provision of the Canadian Copyright Act and any other applica-
ble exceptions, doing any of the mentioned actions without permission violates the
intellectual property rights of the author (Dr. Daniel Page) and the Canadian Copy-
right Act. The original written materials found in this publication are the property
of the author (Dr. Daniel Page), unless stated otherwise.
All business enquiries should be directed by e-mail to Dr. Daniel Page at
gle@[Link].
If cited or referenced, please cite this document (given the appropriate format) as:
Page, D.R. Advanced Data Structures: An Introduction to Data Structures and Al-
gorithms. PageWizard Games, Learning & Entertainment, 2020.
Published electronically/online and in print as of November 2020. Version history
will be disclosed below, where an errata will be available on the website for the book:
[Link]
Daniel R. Page, PageWizard Games, Learning & Entertainment
Sunnyside, Manitoba, Canada.
Book, 160 pages, ISBN 978-1-7774075-1-3 ISBN 978-1-7774075-0-6 (eBook)
First Edition (eBook, paperback), November 2020.
Copyright © 2020 by Daniel R. Page, PageWizard Games, Learning & Entertainment.
All rights reserved.
2

How To Use This Book

The target audience of this book is a beginning second-year Computer Science


university student watching or listening to Dr. Daniel Page’s lectures. It is expected
that the reader is familiar with algebra, functions, common finite and infinite series
such as arithmetic series and geometric series, and basic control structures in pro-
gramming or logic. In addition, the author assumes students are knowledgeable of
some sorting algorithms and other fundamental programming concepts found often
in first-year Computer Science university courses; however, many assumptions are
avoided as the book lays out many common fundamental concepts in data structures
and algorithms. Algorithms are typically presented in pseudocode or in English in
this book, to emphasize the mathematical nature of algorithms and to ease students
away from viewing algorithms as a concept tethered to programming. Java-like pseu-
docode is often used for algorithms, and some Java code is provided in this book.
These notes are to supplement the lectures provided as part of Dr. Daniel Page’s
online lecture series called Advanced Data Structures. This is a compilation of lecture
notes, and not a textbook. At the time of publication these videos are available on
YouTube, and can be found at
[Link]
the playlist for this video lecture series is located at:
[Link]
This lecture series is freely available to all. The primary purpose of this book of
notes is to ensure students that have difficulties writing notes on their own or require
reference for the lectures have accessible notes. This publication is a mostly self-
contained reference for the lecture series, with minimal exceptions. Historically these
notes were compiled in lieu of preparing a course (, hence the main title of this book),
of the same name to be taught by the author, at St. Francis Xavier University.
To best learn the material, it is highly recommended taking written notes while
watching the lectures. A supplemental text that was in mind when these notes were
prepared (as part of course delivery) is:
Goodrich, Tamassia, Goldwasser. Data Structures & Algorithms in Java, 6e, Wiley.
Whenever referred to in these notes, the above book will be referred to as
“text [GTG]” or by the authors via “Goodrich et al.”. It is recommended should
you seek further readings.
Furthermore, each chapter does not reflect a week of material in a course. Mate-
rials covered in the lecture series are not segmented by week, and instead are covered
until completion of each topic. Happy learning, have a beautiful day!
3

About The Author

Dr. Daniel Page is a theoretical computer scientist and science educator, born
in Winnipeg, Manitoba, Canada. At the time of writing this, Dr. Page was most
recently in 2020 an Assistant Professor in the Department of Computer Science at
St. Francis Xavier University. With over a decade-plus experience working with
students and people of all ages in various educational settings, he has also worked as
an instructor and/or researcher for universities such as The University of Manitoba
and Western University, and worked for educational institutions such as the Royal
Aviation Museum of Western Canada and Mad Science of Manitoba. He received
his PhD in Computer Science at Western University in 2019, under the supervision
of Dr. Roberto Solis-Oba.
4

To my students.
Contents

1 Introduction 8
Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Input Size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
The Search Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2 Intro to Analysis of Algorithms I 17


Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Comparing Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Growth Rate of Functions (Asymptotics) . . . . . . . . . . . . . . . . . . . 23
Showing f is O(g) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
Showing f is not O(g) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3 Intro to Analysis of Algorithms II 28


Some Properties of O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
An Iterative Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Back to our “Easy” Search Problem . . . . . . . . . . . . . . . . . . . . . . 30

4 Dictionaries 35
The Dictionary Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
Simple Implementations of a Dictionary . . . . . . . . . . . . . . . . . . . 38

5 Hashing 44
Hash Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Hash Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Separate Chaining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
Open Addressing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
Revisiting the Load Factor . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

5
6 CONTENTS

6 Trees 58
Tree ADT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
Linked Tree Representation . . . . . . . . . . . . . . . . . . . . . . . . . . 61
Tree Property . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
Computing Height of a Tree . . . . . . . . . . . . . . . . . . . . . . . . . . 62
Tree Traversals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

7 Priority Queues & Heaps 65


Priority Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
Array-Based Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . 68
Building a Heap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
Application: Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
Introduction to Amortized Analysis . . . . . . . . . . . . . . . . . . . . . . 77

8 Binary Search Trees 81


Ordered Dictionary ADT . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
BST Implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
Inorder Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
Smallest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
Get . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
Put . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
Remove . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
Successor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

9 AVL Trees 91
Height . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
AVL Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
Re-Balancing AVL Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
putAVL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
removeAVL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
AVL Tree Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

10 Graphs 100
Degrees and the Handshaking Lemma . . . . . . . . . . . . . . . . . . . . . 104
Complete Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
Paths and Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
Trees, Forests, Subgraphs, and Connectivity . . . . . . . . . . . . . . . . . 107
Graph Representations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
CONTENTS 7

11 Graph Traversals 113


Depth-First Search (DFS) . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
Path-Finding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
Cycle Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
Counting Vertices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
DFS Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
Breadth-First Search (BFS) . . . . . . . . . . . . . . . . . . . . . . . . . . 119
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

12 Minimum Spanning Trees 123


Weighted Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
Minimum Spanning Trees & Algorithms . . . . . . . . . . . . . . . . . . . 125
Prim’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
Heap-Based Implementation of Prim’s Algorithm and More! . . . . . . . . 132

13 Shortest Paths 135


Single-Source Shortest Path Problem . . . . . . . . . . . . . . . . . . . . . 135
Dijkstra’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136

14 Multiway Search Trees 139


Beyond Binary Search Trees . . . . . . . . . . . . . . . . . . . . . . . . . . 139
Get . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
Put . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
Successor and Remove . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
(2,4)-Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
B-Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154

View publication stats

Common questions

Powered by AI

The book is described as a set of lecture notes rather than a comprehensive textbook, and its primary purpose is to supplement Dr. Page's lectures. In this context, including an extensive bibliography might not align with its intended function as a resource geared towards aiding students' understanding of lecture material. The absence of a bibliography suggests the book is focused on providing immediate educational support rather than serving as a detailed academic reference. Dr. Page also encourages students to consult other texts, such as "Data Structures & Algorithms in Java" by Goodrich et al., for more in-depth reading, further indicating the book's supplementary role .

The key focus of Dr. Daniel Page's lecture series is to provide a comprehensive understanding of advanced data structures and algorithms, introducing mathematical concepts and analyses through a theoretical lens. This aligns with the book by reinforcing these concepts through written materials that accompany the lectures. The book acts as a reference to support those who may find note-taking challenging, providing continuity and additional context outside the lecture environment. By aligning the content with his lectures, Page ensures that both resources work together to enhance the learning experience .

Pseudocode plays a crucial role in Dr. Daniel Page's book by providing a way to express algorithms without the syntactical constraints of actual programming languages. This allows the focus to be on the logical and mathematical aspects of algorithms, thereby aiding in the conceptual understanding of how algorithms work. By using Java-like pseudocode and some Java snippets, the book bridges the gap between theory and practical implementation, enabling students to better grasp algorithmic concepts without getting bogged down in programming language syntax .

Dr. Daniel Page's book addresses common challenges by presenting algorithms and data structures in pseudocode or English, focusing on their mathematical nature rather than programming syntax. This approach helps demystify algorithms, allowing students to comprehend the underlying logic and execution without the barrier of code syntax, which can be particularly challenging for those less familiar with specific programming languages. Additionally, the book supplements lectures, providing structure and reference material that reinforces student learning, especially for complex or abstract concepts .

Combining lecture notes from "Advanced Data Structures: An Introduction to Data Structures and Algorithms" with video lectures leverages multiple modes of learning to enhance student understanding. Video lectures provide dynamic, visual explanations that can be paused and revisited, accommodating different learning paces and reinforcing complex concepts through auditory and visual channels. Meanwhile, lecture notes offer a written reference that students can annotate, summarize, and reflect upon, facilitating deeper engagement with the material. This dual approach caters to diverse learning preferences, reinforcing knowledge retention and supporting students with different needs and learning styles .

Dr. Daniel Page's extensive experience in theoretical computer science and education informs his teaching materials by emphasizing a deep conceptual understanding of computer science principles. His background includes working in various academic settings and obtaining a PhD under the guidance of Dr. Roberto Solis-Oba, which likely contributes to his methodological emphasis on theoretical aspects over programming details. His teaching materials reflect an educator's perspective that values accessible and comprehensive references for students who may find difficulty in those areas, informed by his practical experience with diverse educational methodologies .

The book is designed as supplemental notes to Dr. Daniel Page's lectures, specifically targeting second-year Computer Science students who attend his lectures. It offers a written reference for students who may struggle with note-taking or require additional clarification on topics covered in his lectures. Although it's not a standalone textbook, the book provides a mostly self-contained reference aligned with the lecture series. Additionally, it includes algorithms presented in pseudocode or English to maintain focus on the mathematical understanding rather than programming .

A potential limitation is that the book explicitly serves as a supplement to Dr. Daniel Page's lectures, not a comprehensive textbook. It lacks a reference/bibliography section, which may limit its utility for in-depth scholarly research. The structure and content are designed specifically to support students who are simultaneously attending his lectures, possibly leaving gaps for those using it independently. Additionally, as a condensed compilation of notes, it might not delve into topics with the depth or modeling exercises one might find in a typical textbook, potentially requiring the use of additional resources to gain a comprehensive understanding .

The book presumes that readers are beginning second-year Computer Science university students who have some familiarity with algebra, functions, and basic programming or logical control structures. It also assumes knowledge of some sorting algorithms and foundational programming concepts commonly explored in first-year Computer Science courses. This background ensures that students are ready to engage with the advanced topics in data structures and algorithms presented in the book .

Dr. Daniel Page uses a teaching approach that emphasizes mathematical understanding of algorithms and data structures rather than viewing them as programming tasks. This approach is reflected in the use of pseudocode and English descriptions for algorithms, aiming to detach students from the idea that algorithms are strictly tied to programming languages. This method helps students develop a conceptual understanding of algorithms' mathematical underpinnings. The book also advises students to actively take notes and recommends supplementary readings for deeper insights. The goal is to ensure students can grasp complex ideas by providing various forms of engagement with the material .

You might also like