Analysis of Algorithms Week 4
这次回顾第四周的内容。
课程主页:https://www.coursera.org/learn/analysis-of-algorithms
Exercise4.9If $\alpha<\beta,$ show that $\alpha^{N}$ is exponentially small relative to $\beta^{N}$. For $\beta=1.2$ and $\alpha=1.1,$ find the absolute and relative errors when $\alpha^{N}+\beta^{N}$ is approximated by $\beta^{N},$ for $N=10$ and $N=100 .$
解:因为当$N$充分大时,对于任意$M$,下式成立
\left(\frac{\alpha}{ \beta} \right)^N
Analysis of Algorithms Week 3
这次回顾第三周的内容。
课程主页:https://www.coursera.org/learn/analysis-of-algorithms
Exercise3.20Solve the recurrence $a_{n}=3 a_{n-1}-3 a_{n-2}+a_{n-3} \text { for } n>2$ with $a_0=a_1=0$ and $a_2=1$.
首先对原式进行改写:
a_{n}=3 a_{n-1}-3 a_{n-2}+a_{n-3} +\delta_{n2}那么
\begin{aligned}
a_nz^n &= 3 a_{n-1}z^n -3 a_{n-2}z^n +a_{n-3} z^n +\delta_{n2}z^n \\
A(z)&= 3zA(z)-3z^2 A(z) +z^3A(z) +z^2\\
A(z) &=\frac{z^2}{ 1-3z+3z^2 -z^3} =\frac{z^2}{(1-z)^3}\\
a_n &=\binom n2 =\frac{n(n-1)}{2}
\end{aligned}3.28Find an ex ...
Analysis of Algorithms Week 2
这次回顾第二周的内容。
课程主页:https://www.coursera.org/learn/analysis-of-algorithms
Exercise2.17Solve the recurrence $A_{N}=A_{N-1}-\frac{2 A_{N-1}}{N}+2\left(1-\frac{2 A_{N-1}}{N}\right) \quad \text { for } N>0 \text { with } A_{0}=0$.
This recurrence describes the following random process: A set of $N$ elements collect into “2-nodes” and “3-nodes.” At each step each 2-node is likely to turn into a 3-node with probability $2/N$ and each 3-node is likely to turn into two 2-nodes with probability $3/N$ Wh ...
斯坦福算法专项课程Course2 week3算法实现
这次回顾Course2 week3的算法。
课程地址:https://www.coursera.org/specializations/algorithms
Heapclass Heap():
def __init__(self, Type):
'''
type定义堆类型,x=1表示最小堆, x=0表示最大堆
'''
#堆的索引从1开始,堆守存放一个无用的元素
self.heap = [-1]
self.len = 0
#type定义堆类型,x=1表示最小堆, x=0表示最大堆
self.type = Type
def insert(self, x):
'''
插入
'''
#进入数组
self.heap.append(x)
#更新长度
self.len += 1
#索引
i = self. ...
EE364A Homework 3
课程主页:https://see.stanford.edu/Course/EE364A
这次回顾凸优化Homework 3。
3.42考虑下水平集
S_0=\{ x |W(x) \le T_0 \}即
\forall x \in S_0, \left|x_{1} f_{1}(t)+\cdots+x_{n} f_{n}(t)-f_{0}(t)\right| \le \epsilon现在$\forall x, y\in S_0, 0\le \alpha \le 1$,考虑
z =\alpha x +(1-\alpha) y那么
\begin{aligned}
\left|z_{1} f_{1}(t)+\cdots+z_{n} f_{n}(t)-f_{0}(t)\right|
&= \left|\left(\alpha x +(1-\alpha) y\right)_{1} f_{1}(t)+\cdots+
\left(\alpha x +(1-\alpha) y\right)_{n} f_{n}(t)-f_{0}(t)\right|\\
&\le \alpha \left|x_{1 ...
斯坦福算法专项课程Course2 week2算法实现
这次回顾Course2 week2的算法。
课程地址:https://www.coursera.org/specializations/algorithms
Dijkstra#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <sstream>
using namespace std;
const int N = 1e6;
const int INFTY = 1e9;
//定义图
vector <int> G[N];
//定义边长
vector <int> G1[N];
//节点数量
int n = 1;
//判断是否访问过
int flag[N];
//距离数组
int dist[N];
int Find_min(){
int index = -1;
int min_dist = INFTY;
for (int i = 1; i <= ...
斯坦福算法专项课程Course2 week1算法实现
这次回顾Course2 week1的算法。
课程地址:https://www.coursera.org/specializations/algorithms
BFS#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
const int N = 1e6;
//定义图
vector <int> G[N];
//节点数量
int n = 1;
//判断是否访问过
int flag[N];
//存储结果
vector <int> res;
void BFS(vector <int> Graph[], int i){
//初始化栈
queue <int> Q;
Q.push(i);
flag[i] = 1;
while (!Q.empty()){
int u = Q.front();
res.push_back(u); ...
斯坦福算法专项课程Course1理论习题算法实现
这一部分将带来Course1理论习题的实现。
思考题1现在有$n$个元素且大小不相同的无序数组,$n$为$2$的幂,给出一个最多用$n+\log_2n-2$次比较的算法来找出第二大的元素。
算法伪代码:传送门
import numpy as np
def Find_second_largest(array):
n = len(array)
#构造Hash,值为和键比较过且小于键的元素
mp = dict()
for i in range(n):
mp[i] = []
#索引集合
index = range(n)
#比较次数
Cnt = 0
while (len(index) != 1):
new_index, cnt = Compare(array, index, mp)
index = new_index[:]
Cnt += cnt
#和最大值比较过的元素
index1 = mp[index[0]]
...
斯坦福算法专项课程Course1 week4算法实现
这次回顾第四周的算法。
课程地址:https://www.coursera.org/specializations/algorithms
Randomized Selectionimport numpy as np
def Exchange(A, i, j):
#交换元素的值
p = A[i]
A[i] = A[j]
A[j] = p
def Partion(A, l, r):
#随机选择
index = np.random.randint(l, r + 1)
Exchange(A, index, l)
#选择主元
p = A[l]
i = l + 1
for j in range(l + 1, r + 1):
if (A[j] < p):
Exchange(A, i, j)
i += 1
Exchange(A, l, i - 1)
return i - 1
def Randomized_ ...
斯坦福算法专项课程Course1 week3算法实现
这次回顾第三周的算法。
课程地址:https://www.coursera.org/specializations/algorithms
Quick Sortimport numpy as np
def Exchange(A, i, j):
#交换元素的值
p = A[i]
A[i] = A[j]
A[j] = p
def Partion(A, l, r):
p = A[l]
i = l + 1
for j in range(l + 1, r + 1):
if (A[j] < p):
Exchange(A, i, j)
i += 1
Exchange(A, l, i - 1)
return i - 1
def Quick_Sort(A, l, r):
n = r - l + 1
if (n <= 1):
return
#返回pivot的位置
i = Parti ...
EE364A Lecture 7 and Lecture 8
课程主页:https://see.stanford.edu/Course/EE364A
这次回顾凸优化第七,第八讲,这部分介绍了凸优化问题以及对偶性。
Lecture 7 Convex optimization problems广义不等式约束考虑广义不等式约束下的凸问题:
\begin{array}{cl}{\operatorname{minimize} } & {f_{0}(x)} \\ {\text { subject to } } & {f_{i}(x) \preceq_{K_{i} } 0, \quad i=1, \ldots, m} \\ {} & {A x=b}\end{array}
f_{0} : \mathbf{R}^{n} \rightarrow \mathbf{R}为凸函数;$f_{i} : \mathbf{R}^{n} \rightarrow \mathbf{R}^{k_{i} }$关于正规锥$K_i$凸
锥形式问题:目标函数和约束为仿射函数的特殊情形
\begin{array}{cl}{\operatorname{minimize} } & {c^{T} ...
EE364A Lecture 5 and Lecture 6
课程主页:https://see.stanford.edu/Course/EE364A
这次回顾凸优化第五,第六讲,这部分介绍了凸优化问题。
Lecture 5 and Lecture 6 Convex optimization problems优化问题的标准形式
\begin{array}{cl}{ {\operatorname{minimize} } } & {f_{0}(x)} \\ {\text { subject to } } & {f_{i}(x) \leq 0, \quad i=1, \ldots, m} \\ {} & {h_{i}(x)=0, \quad i=1, \ldots, p}\end{array}
$x \in \mathbf{R}^{n}$为优化变量
$f_{0} : \mathbf{R}^{n} \rightarrow \mathbf{R}$为目标或损失函数
$f_{i} : \mathbf{R}^{n} \rightarrow \mathbf{R}, i=1, \dots, m$,为不等式约束
$h_{i} : \mathbf{R}^{n} \rig ...