Lecture Notes for CS 512, Algorithm Design

25 September 1999

1. searching

   1. problem - find an item in an array of items

   2. linear search - simple and efficient for small n

   3. improve the search by eliminating more than one item per comparison

   4. sorting the array leads to a binary search

      1. pure

      2. cyclic

      3. matches

         1. a match is when a[i] = i

      4. increasing intervals

      5. stuttering subsequences

      6. bisection, bolzano's method

   5. do better by elimiating more than half on each comparison

      1. interpolation sort - guess the likely location

      2. more complicated, a small improvement over a large improvement

2. sorting - ascending, descending order

   1. problem - how do you sort the array; in place, in situ; key

   2. order n sorts

      1. bucket sorts - a small number of buckets

      2. repeated bucket sorts on pieces of the key - radix sort

         1. right-to-left, radix exchange

         2. left-to-right, straight radix

   3. insertion and selection sort - order n^2 sorts

   4. order n log n sorts

      1. mergesort - divide and conquer; extra storage

      2. quicksort - be a bit smarter on the divide part; n^2 worst case behavior, n log n average case behavior; smallest division size; good execution characteristics

      3. heapsort - build and rebuild the heap, picking off the top element each time

         1. creating the heap in situ; top down and bottom up

      4. lower bound

3. order statistics - median

   1. maximum, minimum, max and min - exploit all information

   2. k-th smallest - back to quicksort.

4. majority

This page last modified on 25 September 1999.