CS 240: Data Structures and Data Management §

https://student.cs.uwaterloo.ca/~cs240/s23/

Markus: https://markus.student.cs.uwaterloo.ca/markus_cs240_s/en/assignments

Concepts §

Module 1: Introduction and Asymptotic Analysis

• Big O
• Asymptotic Analysis
• Merge Sort Module 2: Priority Queue
• Heap Module 3: Sorting, Average-case and Randomization
• Quickselect
• Quicksort
• Bucket Sort
• Radix Sort Module 4: Dictionaries
• AVL Tree
  • Binary Search Tree
  • Tree Rotation Module 5: Other Dictionary Implementations
• Skip List Module 6: Dictionaries for special keys
• Interpolation Search
• Trie
• Compressed Trie Module 7: Dictionaries via Hashing
• Dictionary
• Hashing
• Uniform Hashing Assumption Module 8: Range-Searching in Dictionaries for Points
• Range Tree Module 9: String Matching
• Karp-Rabin Algorithm
• Boyer-Moore Algorithm
• Knuth-Morris-Pratt Algorithm
• Suffix Tree
• Suffix Array

Final §

Things to review

• Skip List

• Compressed Tries?

• Review hash tables

• Understand how range trees are implemented

• Write out the alogirhtm for Karp-Rabin Algorithm, and Boyer-Moore Algorithm

Key idea:

• Use the indices as keys for skip list / BST

Query rectangle, be careful since it is first x,x then y,y

“The exam covers everything up to Module 9 slide 19, with a strong emphasis on post-midterm material (Module 5 - Module 9 slides 19). Be aware that we have not been following the course notes (textbook) exactly. Anything that was not covered in class will not be asked about on the exam. For any question where you do not know the exact formula or details of a pseudocode, you can state your assumptions with your solution.”

Questions

• What is the minimum number of nodes in an AVL tree of height?