資工所準備心得

To: 初學者&跨考者

準備四大資工所，最不能缺少的能力就是數學跟軟體吧~硬體的話，因為台大考得太難，其實準備起來本來就沒有太多基本分，所以還是顧好基本分再去求更多額外分數會比較實際~

TSP(Traveling Salesman Problem)

Backtracking or Dynamic programming

Dijkstra algo.

greedy

時間複雜度O(V*V*V)

Path

Floyd -Warshall

Dynamic programming

All pairs shortest path

Hamiltonian cycles

back track method

##backtrack tech
1,2,3,4,5,6,1
1,2,6,5,4,3,1
1,6,2,5,4,3,1
2,3,4,5,6,1,2(跟第一列相同)

Master theorum

記錄一下

有一時間複雜度如下

我們可以用三個 case去判斷這個方程式的時間複雜度

Case1:

Case2:

Case3:

大師法則在解各研究所基本題可以快速判定，十分有用

Huffman Algo

greedy

有一message → BCCABBDDAECCBBAEDDCC

Knapsack Problem

greedy

。fraction

Constraint

Objective

0/1 Knapsack Problem

Dynamic Programming

Tabulation