• Administrativa
• Introduction and Overview of Topics

Selection

Let S  be a totally ordered set of n pairwise distinct elements. The rank of an element s in S is k if and only if S contains exactly k-1 elements that are smaller than s.

Given: a set S with n elements and a number k
Want: the element s in S of rank k

We assume that there is a funkction splitter(S) that finds an element in S whose ranke lies between n/4 and 3n/4. If splitter(S) does not cause any additional running time, we can solve the selection problem in O(n) time.     
The pseudocode can be found in the notes in the attachment.

This method is called prune and search: in each iteration, a constant fraction of the input (e.g., at least a quarter) is pruned  and the seach is continued in the remainder.
 

Implementations of splitter 

1.  Select a random element q of S; check if the rank of q lies between n/4 and 3n/4; repeat until it does. In expectation, this requires two attempts, so the excpeted running time of this implementation of splitter is O(n). The total expected running time of the selection algorithm is O(n).
2.    The BFPRT-algorithm (Blum-Floyd-Pratt-Rivest-Tarjan):

• Subdivide S into groups of 5 elements each. Find the median in each group (in O(1) time per group). Recursively find the median of these medians. Use the result as the splitter. 
• A detailed analysis shows that this median of medians is a good splitter.
• An induction shows that the overhead for the recursive call does not the overall linear running time (this is because 3/4 + 1/5 < 1, so the problem size still reduces geometrically at each level of the recursion). Attention: the calculations are a bit messy, because we need to deal with floors and ceilings.

Instructor sick - no class.

Foundations and Modelling

• Computational model: random access machine (RAM); a mathematical abstraction of the von-Neumann-Computer
• Running time and space: total cost of the instructions executed and total space used by the RAM for a specific input
• Unit Cost Model (UCM): Each instruction and each memory cell has cost 1.
• Logarithmic Cost Model (LCM): The cost of every instruction and of every memory cell corresponds to the number of bits needed to represent the numbers that are involved
• for combinatorial algorithms, we usually use the UCM, for number theoretich algorithms, we usually use the LCM
• worst-case running time: for each input size, we determine the maximum running time that is needed to process and input of that size
• O-Notation, pseudo-code

Divide-and-Conquer Algorithms

• Karatsuba-Multiplication
  • Given two n-bit natural numbers an and b, comput the product ab.
  • the grade-school algorithm uses a quadratic numbers of additions and multiplications of digits.
  • Karatsuba: use the divide-and-conquer approach. Subdivide the n-bit numbers into four n/2-bit numbers; perform the multiplications recursively; assemble the result from the results of the recursion.
  • naively, we need 4 recursive multiplications. This does not improve the asymptotic running time.
  • using a clever recurrence relations, one can reduce the number of recursive multiplications to 3. This improves the resulting running time.
• Solving recurrence relations
  • Method 1: Guess a solution and verify it by induction.
  • Method 2: Apply the recurrence relations until you can observe a pattern. Use known sum formulas to evaluate the resulting expression.
  • Method 3 (Tree method): Visualize the recurrence as a tree:
    • one node for each recursive call, annotated with the problem size.
    • compute the total running time for each level of the tree.
    • sum over all levels.
  • Method 4: Master Theorem:
    • general method for solving recurrences. Cannot always be applied, but often.
    • See also the notes and here.

Finding a closest point pair

See the attached notes

Dynamic Programming: Knapsack and TSP

For details, see the attached notes.

A website dedicated to the TSP.

The optimal UK pub crawl.

Dynamic Programming: TSP and HMMs

• A dynamic programming algorithm for TSP that achieves exponential running time, using exponential space.
• HMMs: Motivation and Definition

Dynamic Programming: HMMs

Viterbi's algorithm. See attached notes for details

Greedy Algorithms

• Interval selection
  • Given: n intervals
  • Want: maximum size subset of pairwise interior disjoint intervals             
  • Algorithm: go through intervals in increasing order of endpoints; add interval to the solution if it does not conflict with the intervals selected so far
  • Running time: O(n log n)
  • Correctness is proved with an exchange argument: we can transform an optimum solution to the greedy solution without reducing the interval
  • elegant way to phrase the argument: take an optimum solution that is "most similar" to the greedy solution (agrees on a maximum prefix). Either, the two solutions are identical; or we can increase the similarity (length of the prefix) with an exchange step, giving a contradiction to the choice of the optimum solution
     

Greedy Algorithms

• Interval partition
  • Given: n Intervals
  • Want: A partition of the intervals into a minimum number of sets that contain only intervals that are pairwise disjoint.
  • Algorithm: go through intervals from left to right, sorted by start points. Add interval I to the first set that does not contain any interval that overlaps with I from the left. If necessary, create a new set that contains only I.
  • Running time: O(n log n).
  • correctness proof:
    • Depth d of the set of intervals: maximum number of intervals that have a common point.
    • Observation: every feasibly solution contains at least d sets.
    • Fact: The greedy algorithm needs at most d sets.
• offline caching: furthest in the future algorithm
  • see the attached notes

Greedy algorithms

• Offline Caching
  • see the attached notes

Data Structures

• disjoint set union
  • given: fixed set S of n element
  • task: maintain a partition of S into pairwise disjoint sets
  • operations:
    • Find(s): find the set in the current partition that contains s
    • Union(S_i, S_j): unite the sets S_i and S_j of the current partition
  • applications:
    • connected components of a graph
    • Kruskal's algorithm
    • percolation
    • image segmentation
    • FORTRAN
  • simple data structure: disjoint set forest
    • every element is represented by a node
    • every set is represented by a fixed representative element
    • every element has a parent pointer. The parent pointers of the representative elements are NULL. For the other elements we ensure that the parent points will eventually lead to the representative element for the set that contains the element.
    • Find: follow parent pointers until the representative elements
    • Union: given two representative elements, change the parent pointer of one representative element to the other representative element
    • running time can be very bad, if trees get tall
    • Union-by-Rank: during union, put tree of lower height under tree of higher height. Use ranks in the nodes to keep track of the heights of the trees.

Data Structures

• disjoint set union
  • union by rank: ensures O(log n) worst-case time for each find operation. Union takes O(1) time.
  • path-compression heuristic: after walking up the tree during a find-operation, change the parent nodes of all the trees visited during the walk to the root of the tree
  • Seidel-Sharir analysis of disjoint set union with union-by-rank and path-compression
    • see attached notes

Data Structures

• disjoint set union
  • Seidel-Sharir analysis of disjoint set union with union-by-rank and path-compression
    • see attached notes

Data Structures

• disjoint set union
  • Seidel-Sharir analysis of disjoint set union with union-by-rank and path-compression
    • see attached notes

Data Structures

• disjoint set union
  • Wrap-Up: Seidel-Sharir analysis of disjoint set union with union-by-rank and path-compression
    • see attached notes
• amortized analysis
  • analyze the worst-case running time of a sequence of operations on a data structure. Earlier operations can pay for the running time of later operations
• hashing
  • universal hashing
    • consider classic hashing with chaining
    • instead of choosing a completely random hash function, pick hash function from a universal family
    • universal family: for any pair k,l of distinct keys, the probability that a random hash function from the family hashes k and l to the same slot in the hash table is at most 1/size of the hash table.
    • if the hash function is chosen uniformly at random from a universal family, the expected number of collisions for a fixed key is n/m, where n is the number of keys in the hash table and m is the size of the hast table.

• Universal Hashing
  • Existence of an interesting universal family of hash functions
• Perfect hashing

• Perfect Hashing

• Perfect Hashing
• Las Vegas vs Monte Carlo Algorithms
• Bloom Filters

• Page Rank

Data Structures - Priority Queues

• advanced heaps can achieve O(1) amortized decrease-key, O(1) amortized insert, and O(log n) amortized extract-min
• motivation: Dijkstra's algorithm in O(|V| log |V| + |E|) time instead of O(|V| log |V| + |E| log |V|).
• first such data structure: Fibonacci Heaps by Fredman and Tarjan
• since then: many other proposals
• we look at Timothy Chan's quake heaps. See the attached notes for details

• Quake Heaps - continued

Data Structures - Priority Queues

Amortized analysis of quake heaps (see attached notes).

Graph Algorithms - Flows and Cuts in Networks

Problem motivation

Graph Algorithms - Flows and Cuts in Networks

Basic definitions and properties

Ford-Fulkerson algorithm

Min-Cut-Max-Flow Theorem

Ford-Fulkerson algorithm 

Min-cut max-flow theorem 

The Edmonds-Karp Algorithm for Maximum Flow in Networks

Linear Programming: Basic Definitions and the Simplex Algorithm

Linear Programming

• The simplex algorithm
• finding an initial vertex
• worst-case optimal algorithms: ellipsoid, interior-point methods 

Hard Problems: P, NP, polynomial-time reductions, NP-completeness