斯坦福算法专项课程Course2 week3习题解析
这一部分将带来Course2 week3的习题解析。
选择题选择题 1假设您使用排好序的数组(例如,从最大到最小)实现优先级队列的功能。
Insert和Extract-Min的最差运行时间分别是多少?(假设您有足够大的数组来容纳您所面临的插入。)
$\Theta(1)$和$\Theta(\log n)$
$\Theta(n)$和$\Theta(1)$
$\Theta(n)$和$\Theta( n)$
$\Theta(1)$和$\Theta(n)$
Insert需要移动后续的元素,最坏时间复杂度为$\Theta(n)$,Extract-Min直接弹出最后一个元素即可,最坏时间复杂度为$\Theta(1)$
选择题 2假设您使用未排序的数组实现优先级队列的功能。
Insert和Extract-Min的最差运行时间分别是多少?(假设您有足够大的数组来容纳您所面临的插入。)
$\Theta(1)$和$\Theta(\log n)$
$\Theta(n)$和$\Theta(1)$
$\Theta(n)$和$\Theta( n)$
$\Theta(1)$和$\Theta(n)$
因为没有 ...
斯坦福算法专项课程Course2 week3内容回顾
这一周的内容主要介绍了一些常用的数据结构。
Course 2 Week 3HeapHeap是一种特殊的数据结构,其特点为父节点的值或者都不小于子节点,或者都不大于子节点,所以根节点或者为最小值(此时称为最小堆),或者根节点为最大值(此时称为最大堆),来看下堆的具体特点:
以最小堆为例,堆支持如下操作:
下面介绍堆的实现方法(以最小堆为例):
Implementation我们这里使用数组表示Heap,注意此时用完全二叉树表示堆,特点为第$i$个元素的父节点为第$[i/2]$个元素,子节点为$2i,2i+1$(注意下标从1开始),来看个图示:
有了这种表示之后,下面介绍Insert以及Extract-Min
Insert将元素插入队尾(记下标为$i$),如果该元素小于其父节点元素(第$[i/2]$个元素),那么插入成功;否则交换其父节点和该元素的位置,重复此操作直至满足条件或者无法交换为止。可以看到,因为堆是用完全二叉树表示,所以树的高度为$O(\log n)$,所以最多交换$O(\log n)$次。
下面从一个图示中看下具体过程:
Extract-Min删除位置为$1$的元素, ...
Unit 6 Clustering
这一周主要介绍聚类,分别介绍了Hierarchical以及K-means的使用。
课程地址:
https://www.edx.org/course/the-analytics-edge
setwd("E:\\The Analytics Edge\\Unit 6 Clustering")
这次的数据不是csv格式,要使用read.table函数来读取。
movies = read.table("movieLens.txt", header=FALSE, sep="|",quote="\"")
str(movies)
'data.frame': 1682 obs. of 24 variables:
$ V1 : int 1 2 3 4 5 6 7 8 9 10 ...
$ V2 : Factor w/ 1664 levels "'Til There Was You (1997)",..: 1524 6 ...
斯坦福算法专项课程Course2 week2习题解析
这一部分将带来Course2 week2的习题解析。
选择题选择题1考虑边长非负且不同,源点为$s$的有向图。固定目标顶点$t$,并假设该图包含至少一个$s-t$路径。
以下哪项陈述属实?
$s-t$的最短路径必须排除最长边$G$
$s-t$的最短路径必须有最短边$G$
$s-t$的最短路径可能有$n-1$条边,$n$是顶点总数
$s-t$的最短路径没有重复顶点
最短路径和单个边长无关,前两个选项错误。考虑一条直线上$n$个点,从起点到终点有$n-1$条边,第三项正确。假设最短路径有重复顶点,所以包含环,把这个环去掉依旧是$s-t$路径,由边长非负可得,长度更短,第四项正确。
选择题2考虑边长不同,源点为$s$的有向图,目标顶点$t$的有向图,在什么条件下$s-t$最短路径唯一。
当所有边长都是不同的正整数时,并且图$G$不包含有向循环
当所有边长都是2的不同幂
没有其他选项是正确的
当所有边长都是不同的正整数时
选项1,4可以考虑一个四边形,两条边长为1,4另外两条为2,3,那么最短路径不唯一。当边长为2的不同幂时,可以把最短路径理解为一个二进制数,由二进制数表示的 ...
台大实分析单元 8 度量空间 1
这一部分介绍了度量空间的基本概念。
我们之前考虑的都是测度空间$(\Omega,\Sigma, \mu)$,接下来我们要考虑定义在其上的度量空间$L^p(\Omega,\Sigma, \mu),1\le p \le \infty$,我们先介绍度量空间的预备知识。
度量的定义令$M$是一个非空集合,考虑$\rho :M\times M \to \mathbb R$,如果$\rho$满足以下三个性质,$\rho$被称为度量:
\begin{aligned}
(i) & \rho(x,y) = \rho(y,x) 对所有(x,y) \in M\times M \\
(ii) & \rho(x,y) \ge 0 , \rho(x,y) =0 \Leftrightarrow x = y \\
(iii)& \rho(x,y) \le \rho(x,z) +\rho(z,y) (三角不等式)
\end{aligned}来看几个具体例子
例1
M = \mathbb R^n = \{x =(x_1,...,x_n): x_j \in \mathbb R ,j =1,...,n\}\\
定义\ ...
台大实分析单元 7 测度与积分 3
这一讲介绍了Fatou引理以及勒贝格控制收敛定理。
首先给定一个测度空间$(\Omega,\Sigma, \mu)$,其次回顾上次介绍的单调收敛定理:
Theorem 2 单调收敛定理
\{f_n\}可测函数序列, f_n \ge 0 (a.e.), f_n\uparrow(a.e.)\\
那么\int_{\Omega} \lim_{n\to \infty} f_n d\mu = \lim_{n\to \infty} \int_{\Omega}f_n d\mu这里简单说明下这个定理,假设当$x\in N_n$时,$f_n<0$,其中$\mu(N_n)=0$,所以
\mu(\bigcup_{n=1}^{\infty} N_n) \le \sum_{n=1}^{\infty} \mu(N_n) = 0这说明$\{f_n\}$除去一个零测集上都大于等于$0$。此外,由于$f_n\uparrow(a.e.)$,说明存在一个$N$,使得当$x\in \Omega \setminus N$时,$f_n \uparrow $,那么
\mu((\bigcup_{n=1}^{\infty ...
Unit 5 Text Analytics
这一周主要介绍了要介绍了文本分析。
课程地址:
https://www.edx.org/course/the-analytics-edge
首先读取数据。
setwd("E:\\The Analytics Edge\\Unit 5 Text Analytics")
emails = read.csv("energy_bids.csv", stringsAsFactors=FALSE)
emails$email = iconv(emails$email, "WINDOWS-1252", "UTF-8")
str(emails)
'data.frame': 855 obs. of 2 variables:
$ email : chr "North America's integrated electricity market requires cooperation on environmental policies Comm ...
Coursera Cpp程序设计 week 7
这周主要介绍SLT的内容。
课程地址:
coursera:C++程序设计
https://www.coursera.org/learn/cpp-chengxu-sheji
中国大学MOOC:程序设计与算法(三)C++面向对象程序设计
程序设计与算法(三)C++面向对象程序设计
string类基本使用
string 类是模板类:typedef basic_string char string;
使用string类要包含头文件string
string对象的初始化:
string s1(“Hello”);
string month = “March”;
string s2(8,’x’);
错误的初始化方法:
string error1 = ‘c’; // 错
string error2(‘u’); // 错
string error3 = 22; // 错
string error4(8); // 错
可以将字符赋值给string对象
string s;
s = ‘n’;
来看一个具体例子:
#include <iostream>
#include < ...
斯坦福算法专项课程Course2 week2内容回顾
这一周的内容主要介绍了Dijkstra算法。
Course 2 Week 1Dijkstra’s AlgorithmDijkstra算法是解决单源最短路径问题,来看下算法的输入输出:
Input:有向图$G=(V, E). (m=|E|, n=|V| ) $,每条边有非负边长$l_e$,一个源点$s$
Output: 对于每个节点$v$,计算$L(v)$,其中$L(v)$为$s$到$v$的最短路径长度
这里最重要的假设为$l_e \ge 0$。
来看下算法描述:
解释下算法,这里将节点分为$X$和$V-X$,前者为已经计算完结果的节点,后者为还未计算的节点,$A[s]$表示到$s$的最短距离,$B[s]$记录了最短路径。
Why It Works这部分证明为什么Dijkstra算法计算出了正确的结果,即如下事实成立:
L(v) =A[v],\forall v\in V利用数学归纳法证明。
证明:
对于出发点$s$,由于边长非负,所以显然有$L(s) = A[s] = 0$,基本情形得证。
假设对于任意$v\in X$($X$为之前描述的已经计算的节点),$L(v) = ...
斯坦福算法专项课程Course2 week1习题解析
这一部分将带来Course2 week1的习题解析。
选择题选择题1给定有向图的邻接列表表示,其中每个顶点记录其出去的边的数组(不是入边的数组),在最坏的情况下,需要多长时间来计算给定顶点的入度?
像往常一样,我们使用$n$和$m$分别表示给定图的顶点和边的数量。还有,让$k$表示顶点的最大入度。(回想一下顶点的入度是输入它的边数。)
无法确定
$\theta(k)$
$\theta(m)$
$\theta(n)$
只要遍历一遍全部的边,就可以计算出每个顶点的入度,所以为$\theta(m)$
选择题2考虑以下问题:给定有$n$个顶点$m$条边的无向图$G$以及两个顶点$s$和$t$,是否存在至少一个$s-t$路径?
如果$G$用邻接列表表示,则可以在$\theta(m+n)$时间解决上述问题 ,使用BFS或DFS。
如果$G$用邻接矩阵表示。在最坏的情况下,需要什么运行时间才能解决上述计算问题?(假使,假设$G$没有平行的边缘。)
$\theta(n^2)$
$\theta(m+n\log n )$
$\theta(m+n)$
$\theta(m\times n)$
可以先 ...
Neural Networks for Machine Learning Lecture 16
课程地址:https://www.coursera.org/learn/neural-networks
老师主页:http://www.cs.toronto.edu/~hinton
备注:笔记内容和图片均参考老师课件。
这周是课程的最后一次内容,介绍了几个新的应用。
Learning a joint model of images and captions这部分介绍了如何学习图像和标签的联合模型,效果是给每个图像一个标签,训练一共有三步:
1.训练图像的多层模型
2.训练词向量的多层模型
3.利用新的顶层把两个模型联合起来
可以从下图中看到步骤:
Hierarchical coordinate frames这部分主要是解决视角的问题,从下图中来看个例子:
老师指出CNN不太好解决这种问题,给出的方法是使用一组神经元来代表结合特征的形状及其相对于视网膜的姿势。简单来说就是增加神经元来表示特征的相对位置,如下图:
Bayesian optimization of neural network hyperparameters这部分是讲调参的,老师的意思是,如果超参数太多,那么手工调参 ...
台大实分析单元 6 测度与积分 2
这一讲开始介绍了单调收敛定理以及几乎处处的概念。
Therorem 2 单调收敛定理
\{f_n\}是一个单调非递减非负可测函数序列,那么\\
\int_{\Omega} \lim_{n\to \infty} f_n d\mu = \lim_{n\to \infty} \int_{\Omega}f_n d\mu证明:
由于$f_n\uparrow$,所以
f_1 \le ...\le f_n\le ... \le \lim_{n\to \infty} f_n又由于$f_n$非负,因此
\int_{\Omega}f_1d\mu \le ...\le \int_{\Omega}f_nd\mu\le ... \le \int_{\Omega} \lim_{n\to \infty} f_nd\mu \\
\lim_{n\to \infty} \int_{\Omega}f_n d\mu \le \int_{\Omega} \lim_{n\to \infty} f_n d\mu所以我们只要证明另一个方向的不等式即可。
为了证明
\lim_{n\to \infty} \int_{\Om ...