---
tags: 讀書會
title: 演算法讀書會共筆
---
# 演算法讀書會共筆
start date: 2019/8/28
frequence: every Wed.

MIT 6.006 Introduction to Algorithms [PlayList](https://www.youtube.com/playlist?list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb)
筆記連結: [Mit 6006 home page](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-notes/)

This course provides an introduction to mathematical modeling of computational problems. It covers the common algorithms, algorithmic paradigms, and data structures used to solve these problems. The course emphasizes the relationship between algorithms and programming, and introduces basic performance measures and analysis techniques for these problems.

1. Efficient procedures for solving problems on large inputs
1. Scalability
1. Classic data structures and elementary algorithms (CLRS text)
1. Real implementations in Python
1. Fun problem sets!
2.
## 8 Module in this Lecture

| Module | Topic | Lecture |
| :---: | :------------------------------------- | :-----: |
| 1 | Algorithmic Thinking: Peak Finding | 01 - 02 |
| 2 | Sorting & Trees: Event Simulation | 03 - 07 |
| 3 | Hashing: Genome Comparison | 08 - 10 |
| 4 | Numerics: RSA Encryption | 11 - 12 |
| 5 | Graphs: Rubik’s Cube | 13 - 14 |
| 6 | Shortest Paths: Caltech → MIT | 15 - 18 |
| 7 | Dynamic Programming: Image Compression | 19 - 22 |
| 8 | Advanced Topics | 23 - 24 |

## 1. Algorithmic Thinking, Peak Finding

Problem Set 1: [**MIT6_006F11_ps1.pdf**](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/assignments/MIT6_006F11_ps1.pdf)
### 1D array

1D array pick finding
Recursive Algorithm:

If a[n/2] < a[n/2 − 1] then
only look at left half 1 . . . n/2 − − − 1 to look for peak
 
Else if a[n/2] < a[n/2 + 1] then 
only look at right half n/2 + 1 . . . n to look for peak

•Else n/2 position is a peak:

### 2D array
Greedy Ascent Algorithm

• Pick middle column j = m/2
• Find global maximum on column j at (i, j)
• Compare (i, j − 1),(i, j),(i, j + 1)
• Pick left columns of (i, j − 1) > (i, j)
• Similarly for right
• (i, j) is a 2D-peak if neither condition holds ← WHY?
• Solve the new problem with half the number of columns.
• When you have a single column, find global maximum and you‘re done.

## 2. Models of Computation, Document Distance
### Model of computation specifies
1. Random Access Macchine
2. Pointer Machine

Array.append(x)
L = L1 + L2 => a1 + a2 + 1
L1.append(L2)

x^x = 0
x^0 = x

x = x^y
y = y^x = y^x^y = y^y^x = 0^x = x
x = x^y = x^y^x = x^x^y = 0^y = y

## 3. Insertion Sort, Merge Sort
key: Resurrences, devide & conquer, recursion tree, Domainate number
1. insertion sort
2. binary insertion sort
3. merge sort (two finger)
* [merge sort in swift](https://www.raywenderlich.com/741-swift-algorithm-club-swift-merge-sort)

s + (s-e)/2

tree
substitution
master

T(n) = 2T(n/2) + n

## 4. Heaps and Heap Sort
key:[ ADT](https://zh.wikipedia.org/wiki/%E6%8A%BD%E8%B1%A1%E8%B3%87%E6%96%99%E5%9E%8B%E5%88%A5)
Heap: An array vuselized as nearly complete binary tree

max heap: every node value >= childs node value [swift](https://www.raywenderlich.com/586-swift-algorithm-club-heap-and-priority-queue-data-structure)
## 5. Binary Search Trees, BST Sort
## 6. AVL Trees, AVL Sort
key: LVR, Height of node, rotation
> after rotation, the inorder will be the same.

AVL in swift: [(link)](https://github.com/raywenderlich/swift-algorithm-club/tree/master/AVL%20Tree)
[【干货】几个口诀帮你记忆红黑树的操作实现 - 掘金:](https://juejin.im/post/5c86897ae51d45378301e359)

## 7. Counting Sort, Radix Sort, Lower Bounds for Sorting

Decision tree:
leaf -> n! : all possiable choose
## 8. Hashing with Chaining

## 9. Table Doubling, Karp-Rabin

[Karp-Rabin簡介](http://www.tastones.com/zh-tw/stackoverflow/algorithm/substring-search/introduction_to_rabin-karp_algorithm/)

rolling hash ADT: [link](https://blog.csdn.net/jitianyu123/article/details/64618993)

C resizable [link](https://stackoverflow.com/questions/3536153/c-dynamically-growing-array)
## 10. Open Addressing, Cryptographic Hashing
http://alrightchiu.github.io/SecondRound/hash-tableopen-addressing.html
## 11. Integer Arithmetic, Karatsuba Multiplication
Master Theorem
https://zh.wikipedia.org/wiki/%E4%B8%BB%E5%AE%9A%E7%90%86
https://fu-sheng-wang.blogspot.com/2016/11/algorithms14-master-theorem.html

Swift 版本的 Karatsuba Multiplication
https://github.com/raywenderlich/swift-algorithm-club/tree/master/Karatsuba%20Multiplication
## 12. Square Roots, Newton's Method

## 13. Breadth-First Search (BFS)
## 14. Depth-First Search (DFS), Topological Sort
[實作Graph與DFS、BFS圖形走訪演算法](https://kopu.chat/2017/09/22/實作graph與dfs、bfs走訪/)
[神童Erik Demaine](https://zh.wikipedia.org/wiki/Erik_Demaine)
Demaine於2001年加入麻省理工學院（MIT），據報導是麻省理工學院歷史上最年輕的教授，並於2011年晉升為全職教授。
Erik和Martin Demaine的數學摺紙藝術品是2008年現代藝術博物館的設計和彈性心靈展覽的一部分，並被列入MoMA永久收藏品。同年，他是「摺疊之間」的特色藝術家之一，這是一部關於摺紙從業者的國際紀錄片，後來在PBS電視台播出。他是Gathering 4 Gardner的董事會主席。
1. tree
2. for X
3. back
4. cross X
## 15. Single-Source Shortest Paths Problem
https://zh.wikipedia.org/wiki/%E6%88%B4%E5%85%8B%E6%96%AF%E7%89%B9%E6%8B%89%E7%AE%97%E6%B3%95
https://en.wikipedia.org/wiki/Johnson%27s_algorithm
## 16. Dijkstra
- [fibonacci heap](https://www.geeksforgeeks.org/fibonacci-heap-deletion-extract-min-and-decrease-key/)
- [johnson](https://www.geeksforgeeks.org/johnsons-algorithm/)
## 17. Bellman-Ford
## 18. Speeding up Dijkstra
## 19. 动态规划 1: 在斐波那契数列，最短路径中的应用
## 20. Dynamic Programming II: Text Justification, Blackjack

https://leetcode.com/problems/text-justification/

## 21. DP III: Parenthesization, Edit Distance, Knapsack

http://www.csie.ntnu.edu.tw/~u91029/DirectedAcyclicGraph.html


## 22. DP IV: Guitar Fingering, Tetris, Super Mario Bros.
## 23. Computational Complexity
## 24. Topics in Algorithms Research

other resource:
1. https://ms.sapientia.ro/~kasa/Algorithms_3rd.pdf
2. mycodeschool’s playlist: https://bit.ly/1NPQ2wQ
3. MIT course on YouTube: https://bit.ly/1BEh9DL
4. Stanford courses on Coursera: https://bit.ly/2g8OALL
5. The Algorithm Design Manual by Skiena (book): https://amzn.to/2KIEYGB
6. The Google course on Udacity: https://bit.ly/2t7lRLe
7. Algorithms (book): https://amzn.to/2KG5b8n