Abstract Data Types (ADTs) and Binary Search Tree (BST) Data Structures find Stacks and Queues insert Linked list implementation delete (3 cases) Array implementations (including buildTree circular arrays) Terminology (e.g. successor, Asymptotic Analysis predeccessor) Big-O of code snippets Balanced vs unbalanced trees Inductive Proofs AVL Trees Recurrence Relations (and when Balance conditions to apply them) AVL balance condition Formal definition of Big-O Rotations Big-O and -Omega, Theta, little-o insert (4 cases) and -omega Priority Queue ADT Amortized Analysis Heaps Dictionary ADT insert & delete Percolations Hash Tables Array Hash functions, hash values, and representation/implementation indexing buildTree (client version and insert, find, remove Floyd's Method /heapify) Collisions d-heaps Separate chaining Open addressing / probing For each data structure Linear probing Ways to implement Quadratic probing Pros, Cons, and other reasons to Double hashing choose one over the other Rehashing Generic trees Terminology Binary trees Terminology Representation Calculating the height Traversals
Abstract Data Types (ADTs) and Data Structures Stacks and Queues Linked list implementation Array implementations (including circular arrays) Asymptotic Analysis Big-O of code snippets Inductive Proofs Recurrence Relations (and when to apply them) Formal definition of Big-O Big-O and -Omega, Theta, little-o and -omega Amortized Analysis Dictionary ADT Hash Tables Hash functions, hash values, and indexing insert, find, remove Collisions Separate chaining Open addressing / probing Linear probing Quadratic probing Double hashing Rehashing Generic trees Terminology Binary trees Terminology Representation Calculating the height Traversals Binary Search Tree (BST) find insert delete (3 cases) buildTree Terminology (e.g. successor, predeccessor) Balanced vs unbalanced trees AVL Trees Balance conditions AVL balance condition Rotations insert (4 cases) Priority Queue ADT Heaps insert & delete Percolations Array representation/implementation buildTree (client version and Floyd's Method /heapify) d-heaps For each data structure Ways to implement Pros, Cons, and other reasons to choose one over the other
Section%209%20-%20Materials%20Covered.docx