Mini-homework-checkpoint.ipynb



 
 Problem 1. Fibonacci Sequence
在课程里，讨论过如果去找到第N个Fibonacci number。在这里，我们来试着求一下它的Closed-form解。 
Fibonacci数列为 1,1,2,3,5,8,13,21,.... 也就第一个数为1，第二个数为1，以此类推...
我们用f(n)来数列里的第n个数，比如n=3时 f(3)=2。
下面，来证明一下fibonacci数列的closed-form, 如下：
$f(n)=\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^n-\frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2})^n$
 // your proof is here ....
见图片problem1.jpg
 Problem2. Algorithmic Complexity
对于下面的复杂度，从小大排一下顺序：
$O(N),  O(N^2),  O(2^N),  O(N\log N),  O(N!),  O(1),  O(\log N),  O(3^N),  O(N^2\log N), O(N^{2.1})$
 // your answer....
$O(N!),O(3^N),  O(2^N), O(N^{2.1}),O(N^2\log N),  O(N^2), O(N\log N), O(N),O(\log N)$
 Problem 3  Dynamic Programming Problem
 Edit Distance (编辑距离）
编辑距离用来计算两个字符串之间的最短距离，这里涉及到三个不通过的操作，add, delete和replace. 每一个操作我们假定需要1各单位的cost. 
例子： "apple", "appl" 之间的编辑距离为1 （需要1个删除的操作）
"machine", "macaide" dist = 2
"mach", "aaach"  dist=2

    In [142]:
  
 # 基于动态规划的解法
import math
def edit_dist(str1, str2):
    # 两个string 输入
    # your code here
    len1 = len(str1)
    len2 = len(str2)
    dist = [ [0] * (len2+1) for i in range((len1+1))]
    for j in range(1,len2+1,1):
        dist[0][j] =1 
    for i in range(1,len1+1,1):
        dist[i][0] =1
    
    print(dist)
    for i in range(0,len1+1,1):
        for j in range(1,len2+1,1):
            if str1[i-1] == str2[j-1]:
                dist[i][j] = dist[i-1][j-1]
            else:
                dist[i][j] = min(dist[i-1][j-1]+1,dist[i-1][j]+1,dist[i][j-1]+1)
    print(dist)
    return dist[len1][len2]
    
if __name__ == "__main__":
    str1='machine'
    str2 = 'macaide'

    dist = edit_dist(str1,str2)
    print(dist)
  
    
    
    
    
 
    Out [142]:
  
 [[0, 1, 1, 1, 1, 1, 1, 1], [1, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0]]
[[0, 1, 1, 1, 1, 1, 1, 0], [1, 0, 1, 2, 2, 2, 2, 1], [1, 1, 0, 1, 2, 3, 3, 2], [1, 2, 1, 0, 1, 2, 3, 3], [1, 2, 2, 1, 1, 2, 3, 4], [1, 2, 3, 2, 2, 1, 2, 3], [1, 2, 3, 3, 3, 2, 2, 3], [1, 2, 3, 4, 4, 3, 3, 2]]
2
 Problem 4 非技术问题
本题目的目的是想再深入了解背景，之后课程的内容也会根据感兴趣的点来做适当会调整。 
Q1: 之前或者现在，做过哪些AI项目/NLP项目？可以适当说一下采用的解决方案，如果目前还没有想出合适的解决方案，也可以说明一下大致的想法。 请列举几个点。
Q2: 未来想往哪个行业发展？ 或者想做哪方面的项目？ 请列举几个点。
Q3: 参加训练营，最想获得的是什么？可以列举几个点。