Solving recurrences The analysis of merge sort from Lecture I required us to solve a recurrence Recurrences are like solving integrals erential equations, etc o Learn a few tricks Lecture 3: Applications of recurrences

The divide-and-conquer design paradigm 1. Divide the problem(instance) into subproblems 2. Conquer the subproblems by solving them recursively 3. Combine subproblem solutions

Quicksort Proposed by C. A.R. Hoare in 1962 Divide-and-conquer algorithm Sorts“ in place”( like insertion sort, but not like merge sort Very practical(with tuning)

Symbol-table problem Symbol table T holding n records

Binary-search-tree sort 7∈ b Create an empty Bst for i=i to n do trEe-INSert(,AiD) Perform an inorder tree walk of t Example:

Balanced search trees Balanced search tree a search-tree data structure for which a height of o(g n)is guaranteed when implementing a dynamic set of n items

Fixed -universe successor problem Goal: maintain a dynamic subset s of size n of the universe 0=10, 1,.,u-1 of size u subject to these operations INSERT(X∈U\\S): Add x to s DELETE(X E S): Remove x from S

Dynamic programming Design technique, like divide-and-conquer Example: Longest Common Subsequence (LCs) Given two sequences x[l.. m] and yll.n], find a longest subsequence common to them both a' not the

Paths in graphs Consider a digraph g=(v, E)with edge-weight function w:E→>R. The weight of path p=v1→ →>…→> vi is defined to be (D)=∑(n,1)

Shortest paths Single-source shortest paths nonnegative edge weights Dijkstra's algorithm: O(E+ vlg n General