Lecture Notes for CS 512, Algorithm Design

21 September 1999

These are provisional lecture notes, expect changes.

  1. data structures

    1. a set of operations - adt

      1. behavior - insert, fetch, delete, initialize

      2. cost

    2. sometimes storage or representation - cost

  2. element

    1. a generic object - something of type t

    2. operations - equality, total ordering

  3. array - vector, matrix

    1. mapping from a range of integers to elements of type t

    2. constant cost operators; fixed size

    3. directly supported by compilers

  4. record - struct

    1. mapping from tags to elements of type t1 + t2 + t3 + ...

    2. constant cost operators; fixed size

    3. directly supported by compilers

  5. linked lists

    1. dynamic data structure

    2. generally, type node = rec ( next : pointer to node ; data : t)

    3. non-constant access

  6. tree - connected dag

    1. root, parent, child, sibling, ancestor, descendent, leaf, internal, frontier, fringe, ...

    2. binary trees, ternary trees, quad trees, oct-trees, k-ary trees

    3. degenerate, unbalanced - worst cases

    4. lots of mathematics associated with trees - how many edges in a tree with n nodes?

  7. heap - binary tree with data

    1. heap property - parent's data is at least its childrens' data; priority queue

    2. insert - add at the bottom and bubble up

    3. remove - move bottom to top and bubble down

    4. trees are complete O(log|n|) at best

    5. array implementation - a[i], a[2i], a[2i + 1]

  8. binary search tree - dictionary

    1. parent data fits between left and right child's data

    2. search - walk down the tree

    3. insert - walk down to a leaf, then insert

    4. delete - walk to the predecessor or successor, swap, and delete

    5. worst case O(n), average case O(log n)

  9. avl tree

    1. do more work when inserting and deleting to keep the tree nice

    2. avl property - subtree heights differ by at most one

    3. rotations - single and double

  10. hashing

    1. arrays have good put and get, not good searching

    2. also, identifying an index value with an item

    3. hash function - turn an item into an index value

    4. collisions

    5. hash functions - items to integers; mods and primes

    6. dealing with collisions - open or separate chaining; linear probing.

  11. graphs

    1. representation - adjacency matrix, adjacency list; node-edge list.

This page last modified on 23 September 1999.