Intro2Algorithm Notes

Part II Sorting
Ch9 Medians and order statistic
finding the minimum and maximum each = N comparison
finding them both = 3/2* N comparison
finding the second smallest = N + lgN -2 comparison :

construct a comparison tree when finding the smallest, then replace the smallest with negative infinite
and follow the tree again.

finding the kth element = O(n)

O(n) on average : adapted quicksort
O(n) on worst case: first divide the array into groups each of 5 elements. sort each group and select the median , sort all the medians and find the median-of-medians, partition the array around the median-of-medians as the pivot.

Part III Data Structures
Ch10 Elementary Data Structures
representing a tree with arbitrary number of children in a binary tree

struct Node{
Node* parent;
Node* left-child;
Node* right-sibling;
}

ch11 Hash Tables
hash function for ordinary string

“pt” = (’p’ * 128 + ‘t’ ) mod a-big-prime

universal hash methods
division method : k mod N, N should be a prime number not too close to an power of 2