CS240: Data Structures and Data Management

• Taken in S2023: https://student.cs.uwaterloo.ca/~cs240/s23/
• Also look at W2024: https://student.cs.uwaterloo.ca/~cs240/w24/. Assignments change

Helpful youtube channel resource: https://www.youtube.com/channel/UCZCFT11CWBi3MHNlGf019nw

Concepts

Module 1

• Asymptotic Analysis - quiz 1 part 1
• Run-time Analysis - quiz 1 part 2
• Summation
• Merge Sort
• Recurrence Relations

Module 2

• Abstract Data Type
• Stack
• Queue
• Priority Queue
• Heap (Memory)
• Binary Heap
• Heapify
• Heap Sort
• Selection Algorithm

Module 3: Sorting, Average-case and Randomization

• Analyzing average-case run-time
  • Average-Case Run-Time
  • Sorting Permutation
  • Randomized Algorithms
  • Expected Run-time
• Randomized Algorithms
• Selection Algorithm
• Quickselect
• Quick Sort
• Lower bounds of sorting algorithms
• Decision Tree
• Comparison-Based Algorithm
• Sorting Algorithms
• Non-Comparison-Based Sorting
  • Bucket Sort
    • MSD-Radix Sort
    • LSD-Radix Sort

Module 4: Dictionaries

• ADT Dictionary
• Binary Search Tree
• AVL Tree
  • Insertion in AVL Trees
  • Restoring the AVL Property: Tree Rotation

Module 5: Other Dictionary Implementations

• Dictionary
• Skip List
• Static Ordering
• Dynamic Ordering

Module 6:

• Interpolation Search
• Trie
  • Compressed Trie
  • Multiway Trie

Module 7: Dictionaries via Hashing

• Hashing
  • Hashing with Chaining
  • Probe Sequence
  • Cuckoo Hashing

Module 8: Range-Searching in Dictionaries for Points

• Range Searching
• Quadtree
• kd-Tree
• Range Tree

Module 9: String Matching

• Brute force worst-case performance $\Theta ((n-m)\times m)$, this is $\Theta (mn)$, if $m\le n/2$.

• Karp-Rabin Algorithm

• Boyer-Moore Algorithm

• String Matching with Finite Automata

• Knuth-Morris-Pratt Algorithm

• Suffix Trees - didn’t do

• Suffix Arrays - didn’t do

Final

Things to review:

• Compressed Tries (they didn’t ask that)
• Hashing
• Heap properties
• Range trees will certainly be asked, know boundary nodes, and top most inside nodes, P1 and P2!!!

Need to ace the final: Goal: 85%

Thoughts about the final:

Overall, it was easier than the midterm in my opinion, probably because I’ve studied a lot for the final and that it had more problems on computation. So knowing how to do problems such as hashing, tries, range-searching and skip lists helped immensely.

Midterm

Important

Know worst, best, average cases of QuickSort, QuickSelect, HeapSort Know worst case of QuickSelect!!! Wtf are decision trees and how to use them

• Know how to solve problems for module 1 with the asymptotic analysis way (assignment 1)

Things to review:

• Know heapify better
  • a bit better, i know it’s bottom-up fix down, visit every parent node or something. has run-time of $n$ to build a heap out of an array.
• How does heapsort actually work?
• Use AVL to solve a certain problem
• Tree Rotation know which one to use, 4 cases
• Merge, mergesort, heapify, heapsort, quicksort and quick select know the best/worst cases and be able to use them. know what they do
• look through assignments for questions that have similar format to the midterm review session (look at code and give the runtime)
• given an array of size $n$, $0<ϵ<1$, the first $n-n^{ϵ}$ elements are sorted already, describe an $O(n)$ algorithm that sorts the whole array.
  • recognize that most of the array $(n^{ϵ})$ is sorted
  • you only need to sort the small remaining right end
  • knowing which algorithm to use:
    • not quicksort or quickselect because their worst case is $n^2$
    • heapify is $n$, heapsort is $n\log n$, probably overkill
    • merge sort is $n\log n$, merge is $n$
    • Recognize that $n=n^{ϵ},ϵ<1$ so we have some root of $n$ (which is less than $n$), sub in $n=n^{ϵ}$ and use algebra to show that doing merge sort on the small array and merge into the big array is in $O(n)$
• What is the minimum number of nodes in an AVL tree of height?