McGraw Hill Introduction To Algorithms (2nd Ed) >>


 HEAPSORT (112 - 127) 15 pages
  6    1    1,2,3,4,5,6,7
  6    2    1,2,3,4,5
  6    3    1,2,3
  6    4    1,2,3,4 >>

 SORTING IN LINEAR TIME (145 - 160) 15 pages
  8    1    1,2,3,4*
  8    3    1,2,3,4,5*
  8    4    1,2
  8    Pro  2,4,6 >>

 HASH TABLES (192 - 219) 27 pages
  11    1    1,2,3
  11    2    1,2,3,4*
  11    3    1,2,3,4
  11    4    1,2,3,4 >>

HASH TABLES
insert, search, delete operations
Dİrect Adrress Tables
Aim is run in O(1) time.
Collision resolution by chaining
In open addressing, all elements are stored in the hash table itself.
Choose a hash table size, to be prime and not to near a power of 2

h'(k) = ((ak + b)%p)%m
Linear Probing    : h(k, i) = (h'(k) + i) mod m
Quadratic Probing : h(k, i) = (h'(k) + s.i + t.i^2) mod m
Double Probing    : h(k, i) = (h1(k) + i.h2(k)) mod m

Perfect Hashing : We use chaining with another hashing

 BINARY SEARCH TREES (220 - 238) 18 pages
  12    1    1,2,3,4,5
  12    2    1,2,3,4,5,6,7,8,9
  12    3    1,2,3,4,6 >>

 RED-BLACK TREES (238 - 261) 23 pages
  13    1    1,2,6
  13    2    1,2,3
  13    3    1,2, 3, 6
  13    4    1, 2, 3, 4, 6, 7 >>

 B-TREES (371 - 388) 17 pages
  18    1    1, 2, 3, 4, 5
  18    2    1, 3, 5, 6 >>

 BINOMIAL HEAPS (388 - 405) 17 pages
  19    1    1, 2
  19    2    1, 2, 3, 5, 7 >>

 SORTING NETWORKS (614 - 632) 18 pages >>

 MATRIX OPERATIONS (632 - 673) 41 pages >>

 Show All