/ncu-algo-spring23

NCU CSIE Algorithms in 2023 Spring taught by 江振瑞教授.

Primary LanguageJupyter Notebook

NCU CE Algorithms in Spring 2023

這學期 27 學分有專題又有資工資管兩門演算法,不成功便成仁

變 29 學分了

Implementations of Algorithms

Analysis

Algorithm Code Time Complexity Space Complexity
Fibonacci C++ O(2 ^ n) O(n)
Bubble Sort C++ B: O(n ^ 2)
A: O(n ^ 2)
W: O(n ^ 2)
O(1), inplace
Improved Bubble Sort C++ B: O(n)
A: O(n ^ 2)
W: O(n ^ 2)
O(2)
Insertion Sort C++ B: O(n)
A: O(n ^ 2)
W: O(n ^ 2)
O(1), inplace

Divide and Conquer

Algorithm Code Time Complexity Space Complexity
Merge Sort C++ B: O(nlogn)
A: O(nlogn)
W: O(nlogn)
O(n), stable, not inplace
Quick Sort C++ B: O(nlogn)
A: O(nlogn)
W: O(n ^ 2)
B: O(logn)
W: O(n)
not stable, not inplace
Maximum Contiguous Subsequence Sum C++ O(nlogn) O(logn)
Closest Pair of 2D Points C++ O(nlogn)

Dynamic Programming

Algorithm Code Time Complexity Space Complexity
KnapSack C++ O(n * W), n 代表物品數量;W 代表背包最大承重 O(n * W)
Longest Common Subsequence C++ O(n * m), n 代表第一個序列長度;m 代表第二個序列長度 O(n * m)
Maximum Contiguous Subsequence Sum C++ O(n) 原版: O(n)
改良版: O(1)

Homeworks(hand-writing)

#HW Date Score
HW1 A & F 23/03/07 100
HW2 D & 論文心得 23/03/14 100
HW3 B & D 23/03/21 100
HW4 4-1B & 4-2G 23/03/28 100

Midterm Project CNN 工件辨識

收到的評語: Great ! 訓練神經網路就是不斷嘗試~文件做得很好,可以當成下屆範本了 XD

痛哭流涕

Online Judge Problems(Using C++)

佛系解題沒在管排名,不過還是做個紀錄

Team59

#Problem Date Status
1-1 Odd Sum 23/03/01 Yes
1-2 Happy Number 23/03/01 Yes
1-3 Odd Sum 23/03/01 Yes
第一周成績: Rank 18/137 : Time 624
2-1 Odd Sum without prime 23/03/07 Yes
2-2 GCD 23/03/07 Yes
2-3 Perfect number 23/03/07 Yes
第二周成績: Rank 13/137 : Time 206
3-1 Bubble sort 23/03/14 Yes
3-2 Fibonacci 23/03/14 Yes
3-3 All in All 23/03/14 Yes
第三周成績: Rank 3/137 : Time 68
4-1 Age Sort 23/03/22 Yes
4-2 Reverse and Add 23/03/22 Yes
4-3 Number Sort 23/03/22 Yes
第四周成績: Rank 2/137 : Time 101 Done
5-1 Add the Page 23/03/28 Yes
5-2 Divisors 23/03/28 Yes
5-3 Ugly Number 23/03/28 Yes
第五周成績: Rank 5/137 : Time (此周原題目有出錯)
6-1 Calculate Quantum State 23/05/02 Yes
6-2 Multiple Control Constructions 23/05/02 Yes
6-3 Deutsch-Jozsa Algorithm 23/05/02 Yes
第六次成績: Rank 2/137 : Time

Epilogue