LE/EECS 4101 GS/EECS 5101
Advanced Data Structures
Course Information
- Term: Winter 2023
- Lectures:
17:30 - 19:00, Mondays, Wednesdays in person at Keele CC 108
- Instructor:
Shahin Kamali
kamalis@yorku.ca
- Teaching Assistants:
Alireza Pourali (alirezaprl11@gmail.com) - Office hours:
Tuesday 14:00 - 15:00 at LAS-3052B,
Tuesday 15:00 - 16:00 on Zoom (or by appointment)
https://yorku.zoom.us/j/3531400655
- Info & Syllabus:
Find all details here
- Piazza page:
https://piazza.com/yorku.ca/winter2023/advanceddatastructures
Students are encouraged to post their questions on Piazza (this can be done anonymously).
- Course Goals and Intended
Learning Outcomes:
By the end of this course, students are expected to be able to do the followings (refer to course information for details):
- Describe important classes of data structures (dictionaries, priority queues, disjoint set union) and explain how they work.
- Augment data structures to expand their functionality.
- Analyze the efficiency of data structures, including the use of amortized analysis and online competitive analysis.
- Demonstrate knowledge of important
themes in data structure design such as persistence,
self-adjustment, concurrency.
- Select or design appropriate data
structures to help solve problems for algorithmic
applications.
- Textbooks:
All materials from the class will be posted in the course web-page. The slides will be the main source for assignments and exams.
The following book is the main reference for the materials covered in the class.
- Introduction to Algorithms, by Cormen, Leiserson, Rivest, and Stein, MIT Press.
- Course overview:
We will cover concepts related to the design and analysis of data structures and classic structures for implementing various abstract data types. If time allows, we will review applications of data structures in designing efficient algorithms. Tentative topics are listed below.
|
|
List of topics & course material
1. Introduction
Intended learning outcomes:
- Explain the difference between average and amortized running times.
- Contrast offline and online algorithms and describe the meaning of competitive analysis
- Contrast self-adjusting and static data structures via examples that include linked lists and trees.
- Slides:
1a - Formalities
1b - Amortized Analysis
1c - Competitive Analysis
1d - Self-Adjusting Lists and Compression
- Zoom recordings
- Assignment 1
- Assignment 1 solutions
2. Dictionaries
Intended learning outcomes:
- Explain a Dictionary abstract data type and various data structures for implementing it.
- Describe pros and cons of various dictionary data structures and choose the right data structure based on queries that need to be supported.
- Illustrate how a data structure can be augmented to support more queries.
- Differentiate between static and dynamic data structures and analyze them with appropriate tools.
- Contrast and analyze various dictionary data structures such as balanced binary search trees (e.g., AVL trees), hash tables (e.g., Cuckoo hashing), self-adjusting data structures (e.g., AVL trees), and randomized data structures (e.g., skip lists)
- Slides:
2a - AVL Trees and Augmentation
2b - Red-Black trees
2c - 2-3 Trees and B-trees
2d - Splay trees & dynamic optimality conjecture
2e - Hashing
- Zoom recordings:
February 2nd (lecture)
January 30th
February 2nd (tutorial for assignment 1)
February 6th (AVL trees conclusion)
February 6th (Red-Black trees)
February 8th (B-trees and comments on assignment 2)
February 13th (Splay Trees)
February 15th (Hash Tables)
February 27th (Hash Tables)
- Assignment 2
- Assignment 2 solutions
- Assignment 3
- Quiz 1 Solutions
- Assignment 3 solutions
- Sample Midterm
- Midterm Solutions
3. Multidimensional Dictionaries
Intended learning outcomes:
- Explain a Multi-dimensional Dictionary abstract data type, its operations, and the application of these data types.
- Compare and contrast various data structures for implementing multi-dimensional dictionaries.
- Describe the pros and cons of various multi-dimensional dictionary data structures and choose the proper one based on queries needing support.
- Explain the range-search operations and their time complexity for various multidimensional data structures such as quad-trees, kd-trees, and range-trees.
- Slides:
3-multidimensional-dictionaries
- Zoom links:
March 1st (intro, quad-trees)
March 8th (kd-trees, range-trees)
March 13th (Binomial heaps, comments on A4)
- Assignment 4
- Assignment
4 solutions
- Quiz
2 solutions
4. Priority Queues
Intended learning outcomes:
- Explain Priority Queue abstract data type and various data structures for implementing it.
- Describe various data structures for priority queues.
- Select the right data structure for
implementing priority queues based on queries that
need to be supported .
- Explain
algorithms for answering priority queue queries for Binary
Heaps, Binomial Heaps, and Fibonacci heap, and analyze their
time complexities.
- Slides:
5. Disjoint Sets
Intended learning outcomes:
- Explain Disjoint Set abstract data type and its operations (queries).
- Describe various data structures for priority queues and compare and contrast their running times.
- Recognize application of Disjoint Set as ``black boxes" in algorithms like Kruskal's minimum spanning tree algorithm, and use disjoint sets as black boxes for other practical algorithms.
- Describe the standard union-find data
structure for disjoint sets using union-by-rank and
path-compression.
- Slides:
- Zoom links:
6. Randomized Data Structures
Intended learning outcomes:
- Describe advantages of randomization in designing data structures with improved \emph{expected} running time.
- Compare and contrast randomized and deterministic data structures for implementing an abstract data type.
- Describe randomized data structures for
Dictionaries and analyze their space and time complexity.
- Slides:
- Zoom links:
7. String Data Structures
Intended learning outcomes:
- Describe advantages of randomization in designing data structures with improved \emph{expected} running time.
- Compare and contrast randomized and deterministic data structures for implementing an abstract data type.
- Describe randomized data structures for
Dictionaries and analyze their space and time complexity.
- Slides:
- Zoom links:
Review and Last Words