## 算法设计与分析笔记0x07 —— 动态规划(1)

Divide and Conquer 小问题中独立解决

• Dynamic Programming 小问题是有重叠的
• 分隔时，父问题共享子问题

## Integer Multiplication

Brute force solution: $\Theta(n^2)$ bit operations.
To multiply two n-digit integers: (warm up)

• Multiply four n/2-digit integers.
• Add two n/2-digit integers, and shift to obtain result.

$x = 1000 1101$, $x_1 = 1000$, $x_0 = 1101$

## 算法设计与分析笔记0x05 —— 分治法(1)

Divide and Conquer

• Break up problem into several parts
• Solve each part recursively
• Combine solution to sub-problems into over solution

$$T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + n$$
We solve it and get T(n)=O(nlogn), which could be proved by several methods mentioned in Basic Algorithm Note.

## 算法基础笔记0x06 —— 二叉搜索

Dictionary also called dynamic set, which support the following operations.

• find(k) returns 1 if k is in D, 0 otherwise.
• insert(k) puts k in D.
• delete(k) removes k from D.
• pred(k) / succ(k) return the predecessor / successor to k in D, resp.
• min / max return the minimum / maximum value in D, resp.

## Search Algorithm

• 给定一个排好序的数组，搜索输入x
• Idea Maintain an interval between [l, r] where x may be. Shrink the interval as quickly as possible.
• Initially the interval is all of A, i.e. l = 1, r = |A|.
• Use a probe point m = (l + r) / 2.
• If x < A[m], x can’t lie in [m, r], so keep searching in [l, m-1].
• If x > A[m], keep searching in [m+1, r].
• If l = r but x ≠ A[m], then x is not in A.

## Optimal Off-line Caching

• Goal: 最小化覆盖数
• Farthest-in-future: 删除原cache中变量在读取序列中的最后一个

## 算法基础笔记0x03 —— 线性排序

Comparison sorts

Beyond comparison sorts

## Insertion Sort

• Sort the first k numbers.
• Insert k+1’st number v in the proper place.
• Compare v with first k numbers from back to front.
• Stop if find number < v.