Annoucements #

Midterm exam on 21, unless pushed back to 26th.

The format is open book, open notes, no webcam. During class time so it will be timed. One question at a time, randomly shuffled, and you can’t go back to work on previous questions.

Radix sort #

In this example: D = 3, K = 10. Sort from the least significant digit to the most significant digit.

If we use count sort to sort, our runtime is O(D * (N + K)).

Best case is O(n) Worst case O(n^2) Average O(n)

Best/worst case space complexity os O(1)

Symbol table #

When a duplicate is added the value is overwritten. Ordered symbol tables are sorted by key.

key, value “”, 0 “S”, 1 “E”, 3 “A”, 2 “R”, 1 “C”, 1 “H”, 1 “X”, 1 “M”, 1 “P”, 1

When it reaches the “E”, it adds 1 to the value. maxFreqKey would be “E”.