1. Home
  2. COMP
  3. COMP 272: Data Structures and Algorithms (Revision 9)

COMP 272: Data Structures and Algorithms (Revision 9) Report a Broken Link

Computer Science 272: Data Structures and Algorithms builds on the concepts introduced in COMP 268, COMP 206, or COMP 218 and shows how to use data structures as tools to design computer programs that will cope with the complexity of actual applications.

Course Orientation

Supplemental Resources
Barnett, G., & Del Tongo, L. (2008). Data structures and algorithms: Annotated reference with examples. DotNetSlackers. 
Buell, D. A. (2013). Data structures using Java. Jones & Bartlett Learning.

Note: You must log in to Books24x7 through the AU Library before you can access the above resource.
Mehlhorn, K., & Sanders, P. (2008). Algorithms and data structures: The basic toolbox. Springer. 10.1007/978-3-540-77978-0
Dale, N. (2013). C++ plus data structures. Jones & Barlett Learning.

Note: You must log in to Books24x7 through the AU Library before you can access the above resource.
Venkateshwara Rao, K., Srujan Raju, K., & Ravinder, B. (2014). C programming and data structures. University Science Press.

Note: You must log in to Books24x7 through the AU Library before you can access the above resource.
Wang, H. (2023). Introduction to computer programming with Python. AU Press. https://www.aupress.ca/books/oer-202301-introduction-to-computer-programming-with-python/

Unit 1: Introduction

Required Resources
Lin, O. (n.d.). Introduction to abstract data types (ADTs). https://oscar.athabascau.ca/COMP272/ADT.html
Ku. J. (2021, Sept. 13). 1. Algorithms and computation [Video]. YouTube. https://www.youtube.com/watch?v=ZA-tUyM_y7s&list=PLUl4u3cNGP63EdVPNLG3ToM6LaEUuStEY&index=3
Demaine, E. (2021, Sept. 13). 2. Data structures and dynamic arrays [Video]. YouTube. https://www.youtube.com/watch?v=CHhwJjR0mZA
codebasics. (2020, Oct. 2). Insertion sort - data structures & algorithms tutorial Python #16 [Video]. YouTube. https://www.youtube.com/watch?v=K0zTIF3rm9s
Kinsta. (2023, Apr. 7). What is pseudocode? The programmer's time-saving tool [Video]. YouTube. https://www.youtube.com/watch?v=zMRlK7mzows
Lin, O. (n.d.). Insertion sort. GitHub. https://fuhualin.github.io/InsertionSort/
Supplemental Resources
Lehman, E., Thomson Leighton, F., Meyer, A. R. (2015). Mathematics for computer science. https://people.csail.mit.edu/meyer/mcs.pdf
Sedgewick, R., Wayne, K., & Dondero, R. (n.d.). Introduction to programming in Python. https://introcs.cs.princeton.edu/python/home/
Sedgewick, R., & Wayne, K. (n.d.). Programming in Java. Computer science. An interdisciplinary approach. https://introcs.cs.princeton.edu/java/home/

Unit 2: Algorithm Analysis

Required Resources
Ku, J. (2021, Sept. 13). 1. Algorithms and computation [Video]. YouTube. https://www.youtube.com/watch?v=ZA-tUyM_y7s&t=1527s

Note: The above link takes you to 25:27. Please watch until 37:00.
Ku, J. (2021, Sept. 13). 1. Algorithms and computation [Video]. YouTube. https://www.youtube.com/watch?v=ZA-tUyM_y7s&t=2220s

Note: The above link takes you to 37:00. Please watch to the end.
Back to Back SWE. (2019, Feb. 9). A detailed algorithmic analysis of insertion sort. Best case & worst case [Video]. YouTube. https://www.youtube.com/watch?v=ufIET8dMnus
Bell, A. (2024, Apr. 11). Lecture 24: Sorting algorithms [Video]. YouTube. https://www.youtube.com/watch?v=R8Rw9mIa7JQ&t=1620s

Note: The above link takes you to 27:00. Please watch to the end.
Lin, O. (n.d.). Merge sort. GitHub. https://fuhualin.github.io/MergeSort/
Galles, D. (2011). Recursive factorial. Algorithm visualizations. http://www.cs.usfca.edu/~galles/visualization/RecFact.html
Galles, D. (2011). Recursive reverse. Algorithm visualizations. https://www.cs.usfca.edu/~galles/visualization/RecReverse.html
Galles, D. (2011). Recursive n-queens. Algorithm visualizations. https://www.cs.usfca.edu/~galles/visualization/RecQueens.html
Back to Back SWE. (2019, Feb. 3). What is asymptotic analysis? And why does it matter? A deeper understanding of asymptotic notation [Video]. YouTube. https://www.youtube.com/watch?v=myZKhztFhzE
Back to Back SWE. (2019, Feb. 28). Asymptotic notations 101: Big O, Big omega, & theta (asymptotic analysis bootcamp) [Video]. YouTube. https://www.youtube.com/watch?v=0oDAlMwTrLo

Unit 3: Sorting Algorithms

Required Resources
Bell, A. (2024, Apr. 11). Lecture 24: Sorting algorithms [Video]. YouTube. https://www.youtube.com/watch?v=R8Rw9mIa7JQ 

Note: Please watch the above video to 27:00.
Lin, O. (n.d.). Bubble sort. GitHub. https://fuhualin.github.io/bubble_sorting/bubbleSort.html
Lin, O. (n.d.). Insertion sort. GitHub. https://fuhualin.github.io/InsertionSort/
Lin, O. (n.d.). Selection sort. GitHub. https://fuhualin.github.io/SelectionSort/
Devadas, S. (2013, Jan. 14). Lecture 4: Heaps and heap sort [Video]. YouTube. https://www.youtube.com/watch?v=B7hVxCmfPtM
Back to Back SWE. (2019, Mar. 26). The quicksort sorting algorithm: Pick a pivot, partition, & recurse [Video]. YouTube. https://www.youtube.com/watch?v=uXBnyYuwPe8 
Lin, O. (n.d.). Quick sort (pivot first element). GitHub. https://fuhualin.github.io/QuickSort/
Demaine, E. (2013, Jan. 14). Lecture 7: Counting sort, radix sort, lower bounds for sorting [Video]. YouTube. https://www.youtube.com/watch?v=Nz1KZXbghj8
Galles, D. (2011). Comparison sorting algorithms. Algorithm visualizations. https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html
Galles, D. (2011). Bucket sort. Algorithm visualizations. https://www.cs.usfca.edu/~galles/visualization/BucketSort.html
Galles, D. (2011). Counting sort. Algorithm visualizations. https://www.cs.usfca.edu/~galles/visualization/CountingSort.html
Galles, D. (2011). Radix sort. Algorithm visualizations. https://www.cs.usfca.edu/~galles/visualization/RadixSort.html
Galles, D. (2011). Heap sort. Algorithm visualizations. https://www.cs.usfca.edu/~galles/visualization/HeapSort.html
Supplemental Resources
Miller, B., & Ranum, D. (2014). The bubble sort. In Problem solving with algorithms and data structures using Python (3rd ed.). https://runestone.academy/ns/books/published/pythonds3/SortSearch/TheBubbleSort.html
Miller, B., & Ranum, D. (2014). The insertion sort. In Problem solving with algorithms and data structures using Python (3rd ed.). https://runestone.academy/ns/books/published/pythonds3/SortSearch/TheInsertionSort.html
Miller, B., & Ranum, D. (2014). The selection sort. In Problem solving with algorithms and data structures using Python (3rd ed.). https://runestone.academy/ns/books/published/pythonds3/SortSearch/TheSelectionSort.html
Jenkins, G. (2017, Sept. 29). Search/sort 6 | bubble sort [Video]. YouTube. https://www.youtube.com/watch?v=0nE_Zy5lBpk
Jenkins, G. (2017, Oct. 6). Search/sort 8 | insertion sort [Video]. YouTube. https://www.youtube.com/watch?v=wTPlGyRRx2M
Jenkins, G. (2017, Sept. 29). Search/sort 7 | selection sort [Video]. YouTube. https://www.youtube.com/watch?v=pTZA3CsluFk

Binary Heap Operations. TK!

Binary Heap Implementation. TK!
Jenkins, G. (2015, May 22). Trees 7 | priority queue - binary heap 1 [Video]. YouTube. https://www.youtube.com/watch?v=GXq4sV-eo3g
Jenkins, G. (2015, May 22). Trees 8 | priority queue - binary heap 2 [Video]. YouTube. https://www.youtube.com/watch?v=2q1Iaa-P2-o
Jenkins, G. (2015, May 22). Trees 9 | priority queue - binary heap 3 [Video]. YouTube. https://www.youtube.com/watch?v=1vxwC-bIn18
Jenkins, G. (2015, May 22). Trees 10 | priority queue - binary heap 4 [Video]. YouTube. https://www.youtube.com/watch?v=AwfC6Jo_07o

Unit 4: Elementary Data Structures

Required Resources
Demaine, E. (2021, Sept. 13). 2. Data structures and dynamic arrays [Video]. YouTube. https://www.youtube.com/watch?v=CHhwJjR0mZA

Note: Please watch the above video to 21:30.
Galles, D. (2011). Stack (array implementation). Algorithm visualizations. https://www.cs.usfca.edu/~galles/visualization/StackArray.html
Galles, D. (2011). Queue (array implementaion). Algorithm visualizations. https://www.cs.usfca.edu/~galles/visualization/QueueArray.html
Demaine, E. (2021, Sept. 13). 2. Data structures and dynamic arrays [Video]. YouTube. https://www.youtube.com/watch?v=CHhwJjR0mZA&t=1290s

Note: The above link will take you to 21:30. Please watch to 46:25, excluding the section of amortization.
Galles, D. (2011). Stack (linked list implementation). Algorithm visualizations. https://www.cs.usfca.edu/~galles/visualization/StackLL.html
Galles, D. (2011). Queue (linked list implementation). Algorithm visualizations. https://www.cs.usfca.edu/~galles/visualization/QueueLL.html
Reynhout, T. (2020, Apr. 21). Rooted trees - example of terminology [Video]. YouTube. https://www.youtube.com/watch?v=_LGLZzvV3N8

Unit 5: Hash Tables

Required Resources
Demaine, E. (2013, Jan. 14). Lecture 8: Hashing with chaining [Video]. YouTube. https://www.youtube.com/watch?v=0M_kIqhwbFo

Note: Please watch the above video to 42:09.
Demaine, E. (2013, Jan. 14). Lecture 8: Hashing with chaining [Video]. YouTube. https://youtu.be/0M_kIqhwbFo?feature=shared&t=2530

Note: The above link takes you to 42:10. Please watch to the end.
Lin, O. (n.d.). Hash functions with chained list collision resolution. https://oscar.athabascau.ca/COMP272/HashTable.html
Devadas, S. (2013, Jan. 14). Lecture 10: Open addressing, cryptographic hashing [Video]. YouTube. https://www.youtube.com/watch?v=rvdJDijO2Ro
Supplemental Resources
Jenkins, G. (2015, May 8). Search/sort 3 | hash tables 1 [Video]. YouTube. https://www.youtube.com/watch?v=HPN-jNnQ3zs
Jenkins, G. (2015, May 8). Search/sort 4 | hash tables 2 [Video]. YouTube. https://www.youtube.com/watch?v=e0jHauHRmKc
Jenkins, G. (2015, May 8). Search/sort 5 | hash tables 3 [Video]. YouTube. https://www.youtube.com/watch?v=IoaCqPi7uYs

Unit 6: Binary Search Trees

Required Resources
Demaine, E. (2021, Sept. 21). 6. Binary trees, part 1 [Video]. YouTube. https://www.youtube.com/watch?v=76dhtgZt38A
Galles, D. (2011). Binary search tree. Data structure visualizations. https://www.cs.usfca.edu/~galles/visualization/BST.html
Algorithms Lab. (2021, Apr. 5). Red-black trees [Video]. YouTube. https://www.youtube.com/watch?v=aPqz3jyl8ak
Demaine, E. (2021, Sept. 13). 7. Binary trees, part 2: AVL [Video]. YouTube. https://www.youtube.com/watch?v=U1JYwHcFfso
Galles, D. (2011). Red/black tree. Data structure visualizations. https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
Galles, D. (2011). AVL tree. Data structure visualizations. https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
Supplemental Resources
Jenkins, G. (2018, Jan. 31). Trees 11 | binary search trees 1 [Video]. YouTube. https://www.youtube.com/watch?v=bkF7JWiJ7Ns
Jenkins, G. (2018, Jan. 31). Trees 12 | binary search trees 2 [Video]. YouTube. https://www.youtube.com/watch?v=-tCaFKn7Kig
Jenkins, G. (2018, Jan. 31). Trees 13 | binary search trees 3 [Video]. YouTube. https://www.youtube.com/watch?v=zSxpj4o9VkM
Jenkins, G. (2018, Jan. 31). Trees 14 | binary search trees 4 [Video]. YouTube. https://www.youtube.com/watch?v=mJTCLJOMw80
Jenkins, G. (2018, Jan. 31). Trees 15 | binary search trees 5 [Video]. YouTube. https://www.youtube.com/watch?v=PBirOnqte8c
Jenkins, G. (2018, Jan. 31). Trees 16 | binary search trees 6 [Video]. YouTube. https://www.youtube.com/watch?v=XTvEHBl-9-I
Jenkins, G. (2018, Jan. 31). Trees 17 | binary search trees 7 [Video]. YouTube. https://www.youtube.com/watch?v=iPrJ3bMzlzQ
Jenkins, G. (2018, Jan. 31). Trees 18 | AVL trees 1 [Video]. YouTube. https://www.youtube.com/watch?v=dwcAm80mZoc
Jenkins, G. (2018, Jan. 31). Trees 19 | AVL trees 2 [Video]. YouTube. https://www.youtube.com/watch?v=VJ6SwyG0qfM
Jenkins, G. (2018, Jan. 31). Trees 20 | AVL trees 3 [Video]. YouTube. https://www.youtube.com/watch?v=gAVu38oNdMU

Unit 7: Amortized Analysis

Required Resources
Algorithms Lab. (2021, Mar. 15). Amortized analysis: Aggregate analysis and accounting method [Video]. YouTube. https://www.youtube.com/watch?v=VgLh4_4Bkhc
Algorithms Lab. (2023, June 18). Potential method for amortized analysis [Video]. YouTube. https://www.youtube.com/watch?v=8__p9OQn5UY

Unit 8: Binary Trees

Required Resources
Sambol, M. (2022, July 22). B-trees in 4 minutes — Intro [Video]. YouTube. https://www.youtube.com/watch?v=FgWbADOG44s
Sambol, M. (2022, July 24). B-trees in 6 minutes — Properties [Video]. YouTube. https://www.youtube.com/watch?v=fAfuZiFDpRo
Spanning Tree. (2024, Apr. 29). Understanding B-trees: The data structure behind modern databases [Video]. YouTube. https://www.youtube.com/watch?v=K1a2Bk8NrYQ
Sambol, M. (2022, Aug. 14). B-trees in 4 minutes — Search [Video]. YouTube. https://www.youtube.com/watch?v=jLEhJqNVauc
Sambol, M. (2022, Aug. 25). B-trees in 6 minutes — Insertions [Video]. YouTube. https://www.youtube.com/watch?v=tT2DT9Z4H-0
Sambol, M. (2022, Sept. 8). B-trees in 6 minutes — Deletions [Video]. YouTube. https://www.youtube.com/watch?v=pN4C8cLVc7I
Galles, D. (2011). B-Trees. Data structure visualizations. https://www.cs.usfca.edu/~galles/visualization/BTree.html
Galles, D. (2011). B+ trees. Data structure visualizations. https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

Unit 9: Graphs

Demaine, E. (2013, Jan. 14). Lecture 13: Breadth-first search (BFS) [Video]. YouTube. https://www.youtube.com/watch?v=s-CYnVz-uh4

Note: Please watch the above video to 20:22.
Sheehy, D. (2020, Aug. 31). GTAC 2.6: Implementing a graph data structure in Python [Video]. YouTube. https://www.youtube.com/watch?v=uFaZY1dVnGs
Demaine, E. (2013, Jan. 14). Lecture 13: Breadth-first search (BFS) [Video]. YouTube. https://www.youtube.com/watch?v=s-CYnVz-uh4&t=1223s

Note: The above links takes you to 20:23. Please watch to 30:34.
Demaine, E. (2013, Jan. 14). Lecture 13: Breadth-first search (BFS) [Video]. YouTube. https://www.youtube.com/watch?v=s-CYnVz-uh4&t=1835s

Note: The above link takes you to 30:35. Please watch to 44:54.
Sheehy, D. (2020, Aug. 28). GTAC 4.1: Graph search (in Python) [Video]. YouTube. https://youtu.be/wP8tzczIKiY?feature=shared&t=1200

Note: The above link takes you to 20:00. Please watch to the end.
Galles, D. (2011). Floyd-Warshall all-pairs shortest path. Data structure visualizations. https://www.cs.usfca.edu/~galles/visualization/Floyd.html
Demaine, E. (2013, Jan. 14). Lecture 14: Depth-first search (DFS), topological sort [Video]. YouTube. https://www.youtube.com/watch?v=AfSk24UTFS8

Note: Please watch the above video to 42:01.
Sheehy, D. (2020, Aug. 28). GTAC 4.1: Graph search (in Python) [Video]. YouTube. https://youtu.be/wP8tzczIKiY

Note: Please watch the above video to 20:00.
Galles, D. (2011). Kruskal minimum cost spanning tree. Data structure visualizations. https://www.cs.usfca.edu/~galles/visualization/Kruskal.html