Algorithms and Data Structures (INF1, Autumn'05)
Lecture 10
Main topic: Hashing and Sorting.
Lecture Plan
- hashing (symbol table implementation)
- comparison of different implementations of symbol table ADT
- insertion sort
- selection sort
- merge sort
Reading
-
Sections 7.7, 7.9, 9.1, 9.2 and 9.3
of Algorithms and Data Structures: Design, Correctness and Analysis
by Jeffrey H. Kingston.
(You may safely skip the mathematics in the text
having to do with average-case complexity of
the operations, however, read the worst-case complexity analysis.)
- Have a look at
this
and
this (race of sorting algorithms)
graphical demonstration sorting algorithms.