Definition. A directed graph (digraph) G = (V, E) is an ordered pair consisting of • a set V of vertices (singular: vertex)

Dynamic programming Design technique, like divide-and-conquer. Example: Longest Common Subsequence (LCS)

How large should a hash table be? Problem: What if we don’t know the proper size in advance? Goal: Make the table as small as possible, but large enough so that it won’t overflow (or otherwise become inefficient)

Goal: Maintain a dynamic subset S of size n of the universe U = {0, 1, …, u – 1} of size u subject to these operations:

Computational geometry Algorithms for solving “geometric problems” in 2D and higher. Fundamental objects: point line segment line Basic structures: point set polygon

Balanced search tree: A search-tree data structure for which a height of O(lg n) is guaranteed when implementing a dynamic set of n items

The depth of a node = the number of comparisons made during TREE-INSERT. Assuming all input permutations are equally likely, we have

Algorithms Day 12 L8.2 A weakness of hashing Problem: For any hash function h, a set of keys exists that can cause the average access time of a hash table to skyrocket. IDEA: Choose the hash function at random, independently of the keys

Symbol-table problem Symbol table T holding n records: key key[x] [x]

Order statistics Select the ith smallest of n elements (the element with rank i)