Design and Analysis of Data Structures

Notes

• Course by Purva Gawde
• TA: Allie
• purva.gawde@utoronto.ca
• Assignments (4 total): 35%
• Midterm Test: 25%
• Final: 40%
• Allow up to two business days for response after email

Term Test

• Asymptotic Analysis
• AVL Tree
• Augmenting trees
• WBT
• Graph
• Heap
• SCC
• Master Theorem

Week 1

• Data Structures and Algorithms
• Data Structures and Algorithms
• Algorithm Analysis
• Big O Notation
• Big Theta Notation
• Algorithm
• Human Genome project
• Electronic Commerce
• ADT
• Insertion Sort
• Runtime Complexity
• Runtime Bounding
• Big Omega Notation

Week 2

• Limit Theorem for Runtime Bounding
• BST
• AVL Tree
• Red-Black Tree
• B-Trees
• Splay Tree

Week 3

• Augmented Data Structure
• AVL Tree
• Rank AVL Tree

Week 4

• AVL Tree Union

Week 5

• Weight Balanced Binary Search Tree
• Graph Theory
• Graph
• Tree
• Forest
• Breadth First Search
• Depth First Search
• Directed Graph
• Min-Heap
• Heap

Week 6

• Strongly Connected Component
• Transposed Graph