# Algorithms and Computation

## Computation

Computation 中有三个重要概念，问题（Problem)、算法（Algorithm) 和效率（Efficiency）。这三个概念将永远伴随你走过计算机生涯。

### 问题

一个合法的**问题**有以下几个特点：

* 问题定义了从输入到正确输出的二元关系
* 通常问题描述不会穷举所有输入到所有正确输出的关系，而是提供一个可验证的方式来确定输出是否正确。
* 通常问题的输入有两种，有界和无界。无界的输入可以有无限种输入。

### 算法

一个合法的**算法**有以下几个特点：

* 算法是一个将输入映射到确定输出的过程
* ”一个算法解决了一个问题“，意思是对于问题的任意输入，该算法都能将其映射到正确的输出
* 算法的大小必须是有限的
* 算法必须要能证明它的正确性：
  * 有界输入问题：可以穷举
  * 无界输入问题：必须通过归纳法证明

### 效率

Asymptotic Notation:

* Upper Bounds: $$O$$ 
* Lower Bounds: $$Ω$$ 
* Tight Bounds: $$θ$$ 

| input | constant | logarithmic | linear   | log-linear  | quadratic  | polynomial | exponential             |
| ----- | -------- | ----------- | -------- | ----------- | ---------- | ---------- | ----------------------- |
| n     | $$θ(1)$$ | $$θ(lgn)$$  | $$θ(n)$$ | $$θ(nlgn)$$ | $$θ(n^2)$$ | $$θ(n^c)$$ | $$2^{θ(n^c)}$$          |
| 1000  | 1        | $$≈ 10$$    | 1000     | $$≈ 10000$$ | 1000000    | ...        | $$2^{1000} ≈ 10^{301}$$ |

在谈论算法效率之前，必须明确我们的计算模型（Model of Computation）是什么：

#### Word-RAM

内存可以理解成可随机访问的数组，每个元素是一个字（32-bit 或者 64-bit），每次随机访问的时间复杂度为 $$O(1)$$ 

## 如何用算法解决一个问题

### Reduce

将其转化成你所熟知的数据结构及算法，如：

#### Search Data Structures

* Array
* Sorted Array
* Linked List
* Dynamic Array
* Binary Heap
* Binary Search Tree / AVL
* Direct-Access Array
* Hash Table

#### Sort Algorithms

* Insertion Sort
* Selection Sort
* Merge Sort
* Heap Sort
* AVL Sort
* Counting Sort
* Radix Sort

#### Shortest Path Algorithms

* Breadth First Search
* Depth First Search/Topo. Sort
* Dijkstra
* Bellman-Ford
* Floyd-Warshall
* Johnson

...

### Design

设计你的递归/迭代算法：

* 将函数调用抽象成计算图中的一个点，A -> B 表示 A 调用 B
* 将算法按照计算图进行归类，见下表
* 证明算法的正确性

| 算法类别                 | 计算图类别 | 访问节点数量 |
| -------------------- | ----- | ------ |
| Brute Force          | Star  | All    |
| Decrease & Conquer   | Chain | All    |
| Divide & Conquer     | Tree  | All    |
| Dynamic Programming  | DAG   | All    |
| Greedy / Incremental | DAG   | Some   |