COMP 272 v8 Notes and Reading List
Computer Science 272: Data Structures and Algorithms
V8
Contents
Reading List for Units 1–13 ....................................................................................................................................................... 4
Unit 1: Introduction ................................................................................................................................................................. 4
Unit 1 Introduction ....................................................................................................................................................................... 7
Learning Outcomes .................................................................................................................................................................. 7
Study Activities .......................................................................................................................................................................... 7
Assignment 1 .............................................................................................................................................................................. 8
Unit 2 Array-Based Lists ............................................................................................................................................................. 9
Learning Outcomes .................................................................................................................................................................. 9
Study Activities .......................................................................................................................................................................... 9
Assignment 1 .............................................................................................................................................................................. 9
Unit 3 Linked Lists ...................................................................................................................................................................... 10
Learning Outcomes ................................................................................................................................................................ 10
Study Activities ........................................................................................................................................................................ 10
Assignment 1 ............................................................................................................................................................................ 10
Unit 4 Skiplists .............................................................................................................................................................................. 11
Learning Outcomes ................................................................................................................................................................ 11
Study Activities ........................................................................................................................................................................ 11
Assignment 1 ............................................................................................................................................................................ 11
Unit 5 Hash Tables ...................................................................................................................................................................... 12
Learning Outcomes ................................................................................................................................................................ 12
Study Activities ........................................................................................................................................................................ 12
Division Hashing ..................................................................................................................................................................... 14
Multiplication Hashing ......................................................................................................................................................... 15
Folding Hashing....................................................................................................................................................................... 16
Radix Transformation........................................................................................................................................................... 16
Digit Rearrangement ............................................................................................................................................................. 16
Length-Dependent Hashing................................................................................................................................................ 16
, COMP 272 v8 Notes and Reading List
Mid-Square Hashing .............................................................................................................................................................. 16
Resolving Hash Collisions ................................................................................................................................................... 17
Linear Probing..................................................................................................................................................................... 17
Quadratic Probing.............................................................................................................................................................. 18
Double Hashing ....................................................................................................................................................................... 18
Separate Chaining................................................................................................................................................................... 19
Assignment 2 ............................................................................................................................................................................ 20
Unit 6 Recursion........................................................................................................................................................................... 21
Learning Outcomes ................................................................................................................................................................ 21
Study Activities ........................................................................................................................................................................ 21
Decimal to Binary Representation.............................................................................................................................. 21
Printing a String in Reverse Order.............................................................................................................................. 22
Checking for Palindromes .............................................................................................................................................. 22
The Greatest Common Divisor (GCD) ........................................................................................................................ 22
Time Complexity of Recursion ..................................................................................................................................... 23
Assignment 2 ............................................................................................................................................................................ 23
Unit 7 Binary Trees ..................................................................................................................................................................... 24
Learning Outcomes ................................................................................................................................................................ 24
Study Activities ........................................................................................................................................................................ 24
AVL Trees .............................................................................................................................................................................. 24
Assignment 2 ............................................................................................................................................................................ 25
Unit 8 Scapegoat Trees .............................................................................................................................................................. 26
Learning Outcomes ................................................................................................................................................................ 26
Study Activities ........................................................................................................................................................................ 26
Assignment 2 ............................................................................................................................................................................ 26
Unit 9 Red–Black Trees ............................................................................................................................................................. 27
Learning Outcomes ................................................................................................................................................................ 27
Study Activities ........................................................................................................................................................................ 27
Assignment 3 ............................................................................................................................................................................ 27
, COMP 272 v8 Notes and Reading List
Unit 10 Heaps ................................................................................................................................................................................ 28
Learning Outcomes ................................................................................................................................................................ 28
Study Activities ........................................................................................................................................................................ 28
Assignment 3 ............................................................................................................................................................................ 29
Unit 11 Sorting Algorithms...................................................................................................................................................... 30
Learning Outcomes ................................................................................................................................................................ 30
Study Activities ........................................................................................................................................................................ 30
Assignment 3 ............................................................................................................................................................................ 30
Unit 12 Graphs .............................................................................................................................................................................. 31
Learning Outcomes ................................................................................................................................................................ 31
Study Activities ........................................................................................................................................................................ 31
Assignment 3 ............................................................................................................................................................................ 31
Unit 13 Binary Trie ..................................................................................................................................................................... 32
Learning Outcomes ................................................................................................................................................................ 32
Study Activities ........................................................................................................................................................................ 32
Assignment 3 ............................................................................................................................................................................ 32
, COMP 272 v8 Notes and Reading List
Reading List for Units 1–13
Unit 1: Introduction
- Pat Morin’s textbook: https://www.aupress.ca/books/120226-open-data-structures/
- Top coder article: https://www.topcoder.com/thrive/articles/The%20Importance%20of%20Algorithms
- YouTube Video 1 (from 18:25): https://www.youtube.com/watch?v=dnklgh85RE0&t=3247s
- YouTube Video 2 (from 5:00 to 33:28): https://www.youtube.com/watch?v=5kQfRMC64Vk&t=887s
Unit 2: Array-Based Lists
- Lecture notes: https://opendatastructures.org/newhtml/ods/latex/arrays.html#tex2htm-19
- Tutorial PDF: https://scis.lms.athabascau.ca/file.php/4899/studyguide/Unit2_tutorial.pdf
- Visualizations:
- Stack (Array): https://www.cs.usfca.edu/~galles/visualization/StackArray.html
- Queue (Array): https://www.cs.usfca.edu/~galles/visualization/QueueArray.html
- Visualization hub: https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
Unit 3: Linked Lists
- Lecture notes: https://opendatastructures.org/newhtml/ods/latex/linkedlists.html#tex2htm-37
- Visualizations:
- Stack (Linked List): https://www.cs.usfca.edu/~galles/visualization/StackLL.html
- Queue (Linked List): https://www.cs.usfca.edu/~galles/visualization/QueueLL.html
- Java Visualizations: https://www.cs.usfca.edu/~galles/visualization/java/visualization.html
Unit 4: Skiplists
- Lecture notes: https://opendatastructures.org/newhtml/ods/latex/skiplists.html#tex2htm-53
Unit 5: Hash Tables
- Lecture notes: https://opendatastructures.org/newhtml/ods/latex/hashing.html#tex2htm-61
- YouTube Intro: https://www.youtube.com/v/MfhjkfocRR0
- Wikipedia (Separate Chaining): https://en.wikipedia.org/wiki/Hash_table#Separate_chaining
- Minimal Perfect Hashing: https://randorithms.com/2019/09/12/MPH-functions.html
Unit 6: Recursion
- Barnett & Tongo Reference: https://freecomputerbooks.com/data-structures-and-algorithms-annotated-
reference-with-examples.html#downloadLinks
- Euclid.java: https://introcs.cs.princeton.edu/java/23recursion/Euclid.java.html
- Time Complexity Videos:
- https://www.youtube.com/watch?v=cBGLEa6WcrQ
- https://www.youtube.com/watch?v=oZ0MP5euLQ0
- https://www.youtube.com/watch?v=t4mwbA46KF8
- https://www.youtube.com/watch?v=agy0GW9-uyM
Computer Science 272: Data Structures and Algorithms
V8
Contents
Reading List for Units 1–13 ....................................................................................................................................................... 4
Unit 1: Introduction ................................................................................................................................................................. 4
Unit 1 Introduction ....................................................................................................................................................................... 7
Learning Outcomes .................................................................................................................................................................. 7
Study Activities .......................................................................................................................................................................... 7
Assignment 1 .............................................................................................................................................................................. 8
Unit 2 Array-Based Lists ............................................................................................................................................................. 9
Learning Outcomes .................................................................................................................................................................. 9
Study Activities .......................................................................................................................................................................... 9
Assignment 1 .............................................................................................................................................................................. 9
Unit 3 Linked Lists ...................................................................................................................................................................... 10
Learning Outcomes ................................................................................................................................................................ 10
Study Activities ........................................................................................................................................................................ 10
Assignment 1 ............................................................................................................................................................................ 10
Unit 4 Skiplists .............................................................................................................................................................................. 11
Learning Outcomes ................................................................................................................................................................ 11
Study Activities ........................................................................................................................................................................ 11
Assignment 1 ............................................................................................................................................................................ 11
Unit 5 Hash Tables ...................................................................................................................................................................... 12
Learning Outcomes ................................................................................................................................................................ 12
Study Activities ........................................................................................................................................................................ 12
Division Hashing ..................................................................................................................................................................... 14
Multiplication Hashing ......................................................................................................................................................... 15
Folding Hashing....................................................................................................................................................................... 16
Radix Transformation........................................................................................................................................................... 16
Digit Rearrangement ............................................................................................................................................................. 16
Length-Dependent Hashing................................................................................................................................................ 16
, COMP 272 v8 Notes and Reading List
Mid-Square Hashing .............................................................................................................................................................. 16
Resolving Hash Collisions ................................................................................................................................................... 17
Linear Probing..................................................................................................................................................................... 17
Quadratic Probing.............................................................................................................................................................. 18
Double Hashing ....................................................................................................................................................................... 18
Separate Chaining................................................................................................................................................................... 19
Assignment 2 ............................................................................................................................................................................ 20
Unit 6 Recursion........................................................................................................................................................................... 21
Learning Outcomes ................................................................................................................................................................ 21
Study Activities ........................................................................................................................................................................ 21
Decimal to Binary Representation.............................................................................................................................. 21
Printing a String in Reverse Order.............................................................................................................................. 22
Checking for Palindromes .............................................................................................................................................. 22
The Greatest Common Divisor (GCD) ........................................................................................................................ 22
Time Complexity of Recursion ..................................................................................................................................... 23
Assignment 2 ............................................................................................................................................................................ 23
Unit 7 Binary Trees ..................................................................................................................................................................... 24
Learning Outcomes ................................................................................................................................................................ 24
Study Activities ........................................................................................................................................................................ 24
AVL Trees .............................................................................................................................................................................. 24
Assignment 2 ............................................................................................................................................................................ 25
Unit 8 Scapegoat Trees .............................................................................................................................................................. 26
Learning Outcomes ................................................................................................................................................................ 26
Study Activities ........................................................................................................................................................................ 26
Assignment 2 ............................................................................................................................................................................ 26
Unit 9 Red–Black Trees ............................................................................................................................................................. 27
Learning Outcomes ................................................................................................................................................................ 27
Study Activities ........................................................................................................................................................................ 27
Assignment 3 ............................................................................................................................................................................ 27
, COMP 272 v8 Notes and Reading List
Unit 10 Heaps ................................................................................................................................................................................ 28
Learning Outcomes ................................................................................................................................................................ 28
Study Activities ........................................................................................................................................................................ 28
Assignment 3 ............................................................................................................................................................................ 29
Unit 11 Sorting Algorithms...................................................................................................................................................... 30
Learning Outcomes ................................................................................................................................................................ 30
Study Activities ........................................................................................................................................................................ 30
Assignment 3 ............................................................................................................................................................................ 30
Unit 12 Graphs .............................................................................................................................................................................. 31
Learning Outcomes ................................................................................................................................................................ 31
Study Activities ........................................................................................................................................................................ 31
Assignment 3 ............................................................................................................................................................................ 31
Unit 13 Binary Trie ..................................................................................................................................................................... 32
Learning Outcomes ................................................................................................................................................................ 32
Study Activities ........................................................................................................................................................................ 32
Assignment 3 ............................................................................................................................................................................ 32
, COMP 272 v8 Notes and Reading List
Reading List for Units 1–13
Unit 1: Introduction
- Pat Morin’s textbook: https://www.aupress.ca/books/120226-open-data-structures/
- Top coder article: https://www.topcoder.com/thrive/articles/The%20Importance%20of%20Algorithms
- YouTube Video 1 (from 18:25): https://www.youtube.com/watch?v=dnklgh85RE0&t=3247s
- YouTube Video 2 (from 5:00 to 33:28): https://www.youtube.com/watch?v=5kQfRMC64Vk&t=887s
Unit 2: Array-Based Lists
- Lecture notes: https://opendatastructures.org/newhtml/ods/latex/arrays.html#tex2htm-19
- Tutorial PDF: https://scis.lms.athabascau.ca/file.php/4899/studyguide/Unit2_tutorial.pdf
- Visualizations:
- Stack (Array): https://www.cs.usfca.edu/~galles/visualization/StackArray.html
- Queue (Array): https://www.cs.usfca.edu/~galles/visualization/QueueArray.html
- Visualization hub: https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
Unit 3: Linked Lists
- Lecture notes: https://opendatastructures.org/newhtml/ods/latex/linkedlists.html#tex2htm-37
- Visualizations:
- Stack (Linked List): https://www.cs.usfca.edu/~galles/visualization/StackLL.html
- Queue (Linked List): https://www.cs.usfca.edu/~galles/visualization/QueueLL.html
- Java Visualizations: https://www.cs.usfca.edu/~galles/visualization/java/visualization.html
Unit 4: Skiplists
- Lecture notes: https://opendatastructures.org/newhtml/ods/latex/skiplists.html#tex2htm-53
Unit 5: Hash Tables
- Lecture notes: https://opendatastructures.org/newhtml/ods/latex/hashing.html#tex2htm-61
- YouTube Intro: https://www.youtube.com/v/MfhjkfocRR0
- Wikipedia (Separate Chaining): https://en.wikipedia.org/wiki/Hash_table#Separate_chaining
- Minimal Perfect Hashing: https://randorithms.com/2019/09/12/MPH-functions.html
Unit 6: Recursion
- Barnett & Tongo Reference: https://freecomputerbooks.com/data-structures-and-algorithms-annotated-
reference-with-examples.html#downloadLinks
- Euclid.java: https://introcs.cs.princeton.edu/java/23recursion/Euclid.java.html
- Time Complexity Videos:
- https://www.youtube.com/watch?v=cBGLEa6WcrQ
- https://www.youtube.com/watch?v=oZ0MP5euLQ0
- https://www.youtube.com/watch?v=t4mwbA46KF8
- https://www.youtube.com/watch?v=agy0GW9-uyM
