Teaching Assistants (TAs): 姚克翰 潘邦睿 許哲昇 林育勳 鍾偉勝 郭昶逵
Time: 週二 15:00~17:50
Place: A207
TA Class: 週三 18:00~20:00
Scoring：
- 期中考(分析與設計概念)(20%)
- 期末考(分析與設計概念)(25%)
- 程式設計作業、報告、課程參與度及程式設計競賽成績(55%)
- My Book's Manuscript (book1-6.zip)
- Introduction to the Design and Analysis of Algorithms -- A Strategic Approach (2/e), R.C.T. Lee et. al., McGraw Hill, 2005.
- Introduction to Algorithms (3/e), Thomas Cormen, Charles Leiserson, Ronald Rivest and Clifford Stein, MIT Press, 2009.
- Algorithm Design: Foundations, Analysis, and Internet Examples,
Michael
T. Goodrich, Roberto Tamassia, Wiley, 2002. (有中譯本)
- Computer Algorithms, Ellis Horowitz et. al., Silicon Press, 2008.
- 中 文Java程式設計 (第三版) SIM-908A , 江振瑞 著, 儒林出版社, 2006.
- 物 件導向資料結構 — 使用Java語言, 江振瑞 著, 松崗圖書公司, 2005.
- Algorithms, S. Dasgupta, C. Papadimitriou and U. Vazirani, McGraw
Hill,
2008.
- Programming Challenges, Steven S. Skiena and Miguel Revilla, Elsevier, 2003.
- The Algorithm Design Manual, Steven S. Skiena, Elsevier.
- 1. 認識演算法 -- 從食譜到高階程式語言: (Alg-Intro.pptx) .1 演算法名稱的由來
.2 什麼是演算法?
.3 演算法的例子
.4 如何表示演算法?
.5 如何實作演算法? (EuclidGCD.c)(EuclidGCD.cpp)(EucidCGDClass1.java)(EucidCGDClass.java)(EuclidGCD.py)
.6 演算法的正確性
Problem Set 1:
(A) 使用流程圖(flow chart)表示歐幾里德GCD演算法 (Use the flow chart to describe the Euclid GCD algorithm.)
(B) 使用虛擬瑪(pseudo code)寫一個演算法，以輸入一個整數n並輸出小於n的最大質數(prime) (Write an algorithm using the pseudo code to input an integer n and output the largest prime less than n.
(C) 使用虛擬 瑪(pseudo code)寫一個演算法，以輸入一個整數n並輸出所有n除了本身以外的正因數(factor)總和 (Write an algorithm using the pseudo code to input an integer n and output the total summation of all n's factors except n.)
(D) 使用虛擬 瑪(pseudo code)寫一個演算法，以輸入一個整數n並判斷n是否為完 美數(perfect number) (Write an algorithm using the pseudo code to input an integer n and output (decide) if n is a perfect number.
(E) 使用虛擬瑪(pseudo code)寫 一個演算法，以輸入一個整數n並輸出小於n的所有完美數(perfect number) (Write an algorithm to input an integer n and output all perfect numbers less than n.
(F) 使用虛擬瑪(pseudo code)寫一個演算法，以輸入一個具有n個元素的集合S並輸出S的幂集(pwoer set) (Write an algorithm to input a set S of n elements and output the power set of S.)
Programming Problem Set 1
(P1A) 寫一個程式，能夠輸入一個n位元(n=128)整數t，能夠快速回答t之後連續的10000個整數(包含t)是否為質數?
(P1B) 寫一程式將一個大於二的整數進行質因數分解。例如，input為120，output為 120 = 2^3 * 3^1 * 5^1 ；input為19，output為19=19^1。
(P1C) 寫一程式，可以計算歐拉函數Phi(n)，其中Phi(n)定義為小於或等於n的正整數中與n互質的整數個數。例如，input為8，output為 4(因為1,3,5,7都和8互質)；input為19，output為18(因為19是質數，所以所有小於19的正整數都和19互質)。
- 2. 演算法複雜度分析範例(以排序演算法為例)(Alg-Analysis.pptx)
.1 演算法的效能
.2 演算法的時間複雜度
.3 大O漸進記號
.4 降低演算法時間複雜度量級
.5 漸進記號(asymptotical notation): Big O, Big Omega, Theta
.6 多項式時間、指數時間及 偽多項式時間演算法
.7 氣泡排序(bubble sort)演算法 - 3.
分治(divide-and-conquer)演算法: (Alg-Divide&Conquer.pptx)
若是問題 規模(problem size)夠小， 就直接解決之；反之，若問題規模較大，就將其分割(divide)成兩個或多個子問題(分割階段)，然後將每個子問題遞迴地(recursively)征 服(conquer)解決之(征服階段)。之後再將每個子 問題的解答合併(merge)，使其成為原問題的解答(合併階段)。3.3 分治缺陷棋盤填滿(tiling a defective chessboard)演算法
3.1 合併排序(merge sort)演算法 (屬分治演算法)
3.2 快速排序(quick sort)演算法 (屬分治演算法)
3.4 分治二維求 秩(2D rank finding)演算法
3.5 分治二維最大點(2D maxima finding)演算法
3.6 分治最近二 維點對(closest pair of 2D points)演算法
Problem Set 3:
(A) 寫一個分治演算法來解決一 個給定的數值集合的求秩(rank finding)問題，並進行複雜度分析。
(B) 寫一個分治演算法來找出一群在X軸上的點中的最近點對(closest pair of points on X-axis)，並進行複雜度分析。
(C) 寫出一個分治演算法來解決最長單調遞增 連續元素 子序列(the longest monotonically increasing consecutive element subsequence) 問題，並分析演算法的時間複雜度，並進行複雜度分析。
(D) 給定一 個包含n個正或負整數的一維陣列A，以分治演算法在O(n log n)時間複雜度求出連續相鄰元素的最大總和。你必須進行複雜度分析以驗證你的結果。
(E) 在選取刪尋演算法中，若每個分割子集改為3個元素，則其最壞狀況時間複雜度是否依然為O(n)，為什麼?
(F) 在選取刪尋演算法中，將每個分割子集改為6個元素後重新分析其時間複雜度。
.8 插入排序(insertion sort)演算法
Problem Set 2:
(A) 在氣泡排序(bubble sort)演算法中，若在某回合中完全沒有任何資料對調，則可推論資料已經排序完成而立即結束演算法執行，這稱為改良氣泡排序(improved bubble sort)演算法。請以虛擬碼描述「改良氣泡排序演算法」。(請注意:在有些文獻中，所謂「氣泡排序演算法」其實指的是「改良氣泡排序演算法」)
(B) 分析改良氣泡排序演算法最佳、最差與平均時間複雜 度
(C) 使用虛擬碼描述堆積排序(heap sort)演算法
(D) 分析堆積排序演算法時間空間複雜度
(E) 使用虛擬碼描述基數(radix sort)演算法
(F) 分析基數排序演算法時間空間複雜度
Programming Problem Set 2
(PA) 寫一個程式實作基數排序演算法
- 4. 刪尋(prune-and-search)演算法: (Alg-Prune&Search.pptx)
刪尋(prune-and-search)演算法包含多次迭代 (iteration)，在每一次的迭代中，均刪除(prune)輸入資料的一部分(假設為f部份, 0<f<1)，而後再遞迴地(recursively)以相同的演算法在剩餘的資料中搜尋(search)出解答。在經過一定次數的迭代後， 輸入資料的規模將會變得相當小，而能在常數時間內直接找出解答。
假設一個刪除-搜尋演算法的時間複雜度為T(n)，並且每次迭代所需的時間 為O(nk)(k為大於0的常數)，則T(n)=T((1-f)n)+O(nk)。由於 1-f<1，我們可得T(n)=O(nk)。
4.1 二元搜尋(binary search)演算法
4.2 選取(selection)與中位數(median)演算法
4.3 限制的一圓心(constrained 1-center)演算法
4.4 簡化的二變數線性規劃(simplified 2-variable linear programming)演算法
- 5. 貪婪演算法(greedy algorithm): (Alg-Greedy.pptx)
貪婪演算法(greedy algorithm)一步步地建構出一個問題的完整解答。其每一步都藉由貪婪解題策略(greed strategy)增加一部份的解答到完整解答中。所謂貪婪解題策略為: 每一次都選擇當下最好的部份解答加入完整解答中。
5.1 背包演算法(knapsack algorithm) (帶出0/1背包問題後可以在之後講授NP-hard問題)
5.2 Huffman編碼演算法
5.3 Kruskal最小含括樹(minimum spanning tree, MST)演算法
5.4 Prim最小含括樹(minimum spanning tree, MST)演算法
5.5 Dijkstra最短路徑演算法
Problem Set 4:
(A) 以刪尋演算法解決以下限制的一圓心問題: (0,0),(1,1),(2,2),(3,3),(4,2),(5,1),(6,0),(2,0)，圓心在y=0上。(可以精確繪圖說明即可)
(B) 以刪尋演算法解決以下限制的一圓心問題: (0,0),(1,1),(2,2),(3,3),(4,2),(5,1),(6,0),(4,0)，圓心在y=3上。(可以精確繪圖說明即可)
(C) 以刪尋演算法解決以下簡化的雙變量線性規劃問題: 最小化y，限制條件為y>=x+4, y>=3x+6, y>=2x+8, y>=4x+10, y>=-x+6, y>=-2x+2, y>=-3x+9, y>=-4x+12。(可以精確繪圖說明即可)
(D) 一個背包容量為10，現在有5個物品， 重量分別為4、3、6、2、5，價格分別為10、9、 12、4、8，求背包能夠裝入零碎(fractional)物品的最大價值為何?
(E) 分別利用Kruskal's演算法與Prim's演算法求出以下圖(graph)的最小生成樹 (minimum spanning tree, MST)
(F) 利用Huffman 編 碼演算法替以下字元編碼A(42%)、B(7%)、C (18%)、D (33%)。(備註:括號中為字元出現頻率)
(G) 利用Dijkstra演算法求以下圖(graph)頂點4到各頂點的最短路徑(shortest path)距離(成本)
- 6. 動態規劃(dynamic programming)演算法:
(Alg-DP.pptx)
動態規劃(dynamic programming)演算法籍由將原問題分解成一系列子問題 (subproblems)，並依序解決子問題來解決原問題。為避免一再地解重複的子問 題，一旦解出子問題的解答(solution)，即會將其存在表格(或陣列)中。當需要用到某一子問題的解答時，與其重新計算其解答，演算法會取而代之地 從表格中直接取出其解答以節省計算時間，是一個「以空間換取時間」的演算法。一個動態規劃演算法會先從最簡單的子問題先解起，並以一定的程序持續運行直至 求出原問題解答為止。
最佳解原則(Principle of optimality):
假設為了解決一個問題，我們必須作出一系列的決策
D1, D2, …,
Dn。若這一系列的決策是最佳解，則針對於前n-k個(或最後n-k個)決策所產生的狀態(子問題)而言，最後的k個(或前k個)決策(1<=
k<=n)必定也是最佳的。
6.1 Bellman-Ford最短路徑演算法
6.2 Floyd-Warshall最短路徑演算法
6.3 多階圖最小成本路徑(multi-stage graph minimum-cost path)演算法
6.4 最長共同子序列(longest common subsequence, LCS or LCSS)演算法
Problem Set 5:
A. 利用Floyd-Warshall演算法求以下圖(graph)全對最短路徑(all-pair shortest path)距離(成本)(此圖的啟始距離矩陣如下，以經過的中間節點為s, a, b, c, d的順序寫出距離矩陣的改變過程。)
(d->b的加權在圖形與表格中誤植為不一致的值，同學可以將之改為5或6讓圖形與表格一致後解題都算答對。)
B. 求出以下給定圖(graph)的Floyd-Warshall演算法的啟始前節點矩陣(陣列)，並求出最後的前節點矩陣(陣列)。
-
C.
以下是Floyd-Warshall演算法針對具有五個節點(記為1、2、3、4、5)的圖產生的前節點矩陣(陣列)，說明如何藉以找出節點1到節點3的
最短路徑，及節點5到節點2的最短路徑。
D. 針對以下的給定圖，列出Bellman-Ford最短路徑演算
法執行過程，
說明Bellman
-Ford最短路徑演算法如何檢查出一給定圖具有負循環(negative-weight
cycle)。
E. 證明Bellman-Ford最短路徑演算法可以檢查出一給定圖具有負循環(negative-weight cycle)，也就是累積邊加權為負的循環。
F. 寫一個演算法來解決最長單調遞增子序列問題(the longest monotonically increasing subsequence problem)，並分析演算法的時間複雜度。
E. 證明Bellman-Ford最短路徑演算法可以檢查出一給定圖具有負循環(negative-weight cycle)，也就是累積邊加權為負的循環。
F. 寫一個演算法來解決最長單調遞增子序列問題(the longest monotonically increasing subsequence problem)，並分析演算法的時間複雜度。
- 7. Software Defined Networking
(SDN) and Dijkstra's Algorithm (SDN&Dijkstra2015.pptx)
and programming stuffs (ACM-ICPC&EPC.ppt)
Title:
This talk introduces the
SDN (Software Defined Networking)
concept
and its development and applications. The talk also includes the topic
of
extending Dijkstra’s shortest path algorithm to achieve the optimal
routing
for SDN by considering not only edge weights but also node weights. How
to
implement the extended Dijkstra’s algorithm with Pyretic, a
Python-based
language for developing SDN applications, is also elaborated. Finally,
simulation
results of the algorithm using the Mininet and the Iperf tools on the
Abilene
topology are described.
- 期中考:
(時間:
4/19 下
午4:00-5:50)
(地點: 工程五館 2F 教室)
(範圍: 已授課的部份)(參考:book1-6.zip)
- 7. (4/26) (5/3) 再探動態規劃(dynamic
programming)演算法: (Alg-DP.pptx)
最大連續子序列和(Maximum Contiguous Subsequence Sum)演算法 (MCSS.pptx)
(5/3) (SomeDPA.zip)
- 8. (5/10) 樹搜尋(tree
search)與回溯(backtracking)演算法: (Alg-TS&BT.pptx)(更正:
投影片第36和37頁
樹第三層右邊的三個節點由左而右依序為"2' "4' "5")
(8-, 15-, 24-puzzle games)
*許多問題的尋找解答過程可以使用樹 (tree)來表達，這類問題也都可以建構 出解答空間樹(solution space tree)。因此要找到這些問題的解答，不管是可行解(feasible solution)或是最佳解(optimal solution)，就轉變成一個樹搜尋(tree search)問題。
*有許多方法可以拜訪(visit)與拓展(expand)一個解答 空間樹，包括深度優先搜尋(depth-first search, DFS)、廣度優先搜尋(breadth- first search, BFS)、登山搜尋(hill climbing search, HCS)以及最佳優先搜尋(best-first search)等演算法。
.1 廣度優先搜尋(breadth-first search, BFS)演算法
.2 深度優先搜尋(depth-first search, DFS)演算法
.3 登山搜尋法(hill climbing search, HCS)演算法
.4 最佳優先搜尋法(best-first search)演算法
.5 回溯(backtracking)演算法
Problem Set:
A. 給定一集合S={7, 4, 1, 2, 11}以及一加總值10，利用深度優先搜尋法來解子集合加總問題，你必須畫出解出問題的解答空間樹(solution space tree)。
B. 以深度優先搜尋演算法找出以下圖(graph)的漢米爾頓迴路 (Hamiltonian circuit)，你必須畫出解出問題的解答空間樹(solution space tree)。
C. 以廣度優先搜尋演算法找出上圖的漢米爾頓迴路，你必須畫出解出問題的解答空間樹(solution space tree)。
D. 以空單 格的移動方向為上下左右的次序，以廣度優先搜尋演算法下解決以下的八拼圖(8- puzzle)問題。
起始狀態:
目標狀態:2
3184765
E. 以空單 格的移動方向為上下左右的次序，以深度優先搜尋演算法解決D題中的八拼圖(8- puzzle)問題。1238
47
65
F. 以空單格的移動方向為上下左右的次序，以登山搜尋演算法解決D題中的八拼圖(8-puzzle)問題。而評估函數為方塊錯置的數目，若有相同的 情形，則以空單格移動方向上下左右為其優先順序。
G. 以空單格的移動方向為上下左右的次序，以最佳優先搜尋演算法解決D題中的八拼圖(8-puzzle)問題。而評估函數為方塊錯置的數目，若有相同的情形，則以空單格移動方向上下左右為其優先順序。 - 9. (5/17) 分支定界(Branch and Bound)演算法 (Branch&Bound.zip)
*分支定界(branch and bound)是一個拜 訪與拓展解 答空間樹的特殊方法，用於找出問題的最佳解。其做法相當於找出一種方法來切割出解答空間的分支(branch)，然後以上界(upper bound)與下界(lower bound)的概念來加快最佳解的搜尋。
*對於尋找最小成本(minimum cost)解答的最佳化問題而言，分支定界演算法會針對每一分支的解答預測其成本下界(lower bound)，並利用找出可行解來得到問題的成本上界(upper bound)。如果有一個解答的成本下界超過問題成本上界，則這個解不可能是最佳的，因此演算法會中止(terminate)與這個解相關聯的整個分支的 搜尋。
*而對於尋找最大利益(maximum benefit)解答的最佳化問題而言，分支定界演算法會針對每一分支的解答預測其利益上界(upper bound)，並利用找出可行解來得到問題的利益下界(lower bound)。如果有一個解答的利益上界低於問題利益下界，則這個解不可能是最佳的，因此演算法會中止(terminate)與這個解相關聯的整個分支的 搜尋。
.1 基本概念
.2 分支定界演算法(配合登山搜尋法)解決多階圖最短路徑問題
.3 分支定界演算法(配合最佳優先搜尋法)解決旅行推銷員問題
.4 分支定界演算法(配合最佳優先搜尋法)解決0/1背包問題
.5 一個特殊的分支定界演算法: A*演算法
Problem Set:
A. 以分支定界演算法解決以下多階圖最短路徑問題。
B. 使用分支定界演算法解決以下旅行銷售員問題。（註: 必須畫出搜尋樹）
ø 代表無窮大i j
1
2
3
4
5
1
ø
5
61
34
12
2
57
ø
43
20
7
3
39
42
ø
8
21
4
6
50
42
ø
8
5
41
26
10
35
ø
C. 給定一0/1背包問題，其背包可載重C=10,且有三物品的重量分別為10, 3, 5，而其利潤分別為40, 20, 30，使用分支定界演算法來解此0/1背包問題 （註: 必須畫出搜尋樹）
D. 使用A*演算法來解以下之多階圖最短路徑問題。（註: 必須畫出搜尋樹）
E. 將A題的S與T對調，箭頭反向解題。
F. 將B題所有成本乘以2減3解題。
G. 將C題的物品重量改為20, 5, 6解題。
H. 將D題的V0與V8對調，箭頭反向解由V8到V0的最段路徑問題。
- 10. (6/21) 問 題下界與問題分類: P、NP、NP困難與NP完全問題 *一個問題 的下界為任何能解決此問題的演算法至少所需的時間複雜度。(The lower bound of a problem is the least time complexity required for any algorithm which can be used to solve this problem.) (ProblemLB.zip)
*NP完全問題理論: 若任何一個NP完全問題可在多項式時間被解決，則每一個NP問題皆可在多項式時間獲得解決(也就是P=NP)。 If any one NP-complete problem can be solved in polynomial time, then every problem in NP can also be solved in polynomial time (i.e., P=NP). (Recipe, Cook and Carp)(NPC.zip)
*(NPC理論測驗及解答)
A. 證明支配集問題(dominating set problem)為NP問題。
B. 證明點覆蓋問題(vertex cover problem)為NP問題。
C. 證明集團問題(clique problem)為NP問題。
D. 證明著色問題(chromatic coloring problem)為NP問題。
E. 證明0/1 背包問題(0/1 knapsack problem)為NP問題。
F. 證明3-滿足問題(3-SAT problem)為NP問題。
G. 證明獨立頂點集合問題(independent set problem)為NP問題。
I. 證明Steiner tree決策問題為NP問題。
J. 證明裝箱問題(bin packing problem)為NP問題。
B. 證明點覆蓋問題(vertex cover problem)為NP問題。
C. 證明集團問題(clique problem)為NP問題。
D. 證明著色問題(chromatic coloring problem)為NP問題。
E. 證明0/1 背包問題(0/1 knapsack problem)為NP問題。
F. 證明3-滿足問題(3-SAT problem)為NP問題。
G. 證明獨立頂點集合問題(independent set problem)為NP問題。
I. 證明Steiner tree決策問題為NP問題。
J. 證明裝箱問題(bin packing problem)為NP問題。
- 11. (5/24)近似演算法 (Approximation algorithms) (ApproximationAlgorithm.zip) 歐拉旅途演算法 (Eulerian Tour Algorithm) (EulerianTour.zip)
- 12. (5/31) 最小成本最大流量演算法(Minimum-Cost Maximum-Flow Alg., Min-Cost Max-Flow Alg.,
MCMF Alg.)(MCMF-New.zip)(p32頁最大流應為9)、匈牙利演算法(Hungarian
Algorithm)(HungarianAlg.zip)、應用實例
1: (LOM.ppt)
應用實例2: Paper: Yung-Liang Lai and Jehn-Ruey Jiang, "Sink-Connected Barrier Coverage Optimization for Wireless Sensor Networks," in Proc. of 2011 International Conference on Wireless and Mobile Communications (ICWMC 2011), 2011. (Slides)
Problem Set 7:
A. 使用匈牙利演算法(Hungarian algorithm)來解以下的指派問題(assignment problem)（註: 必須寫出演算法執行過程中的每個中間結果）
B. 自行設計一個指 派問題(assignment problem)的4x4成本矩陣，並以匈牙利演算法(Hungarian algorithm)找出最大權重完美二分匹配(Maximum-Weight Perfect Bipartite Matching)。
Task A
Task B
Task C
Tim
$1
$2
$3
Bob
$2
$3
$2
Alex
$2
$2
$3
C. 說明如何使用匈牙利演算法(Hungarian algorithm)解決最小歐氏平面權重配對(Minimum Euclidean Weighted Matching)問題。所謂最小歐氏平面權重配對問題描述如下: 給定n個點(n為偶數)，如何將此n個點匹配形成n/2個點對，讓每個點對形成一條線段，而此n/2條線段具有最小的長度總和。
D. 隨意畫出四個歐氏平面點(2D point)，設其距離皆為整數(以公分計算)，以匈牙利演算法(Hungarian algorithm)找出其最小歐氏平面權重配對(Minimum Euclidean Weighted Matching)。
E. 以Edmonds-Karp演算法解決以下最大流量問題(圖的有向邊(directed edge)上所標示的為容量(capacity))
F. 自行 設計一個流網 (flow network)(除s、t外具有4個節點，並具有10個edge)，以Edmonds-Karp演算法解決 其最大流量問題。
Problem Set 8:
A. 完成投影片p30之Bellman-Ford演算法檢測負循環範例
B. 說明如何將匈牙利演算法能夠解答的最小成本指 派問題(assignment problem)變轉為(reduce to)最大流問題
C. 將以 下最小成本指 派問題(assignment problem)轉換為流網(flow network)，以便使用最大流(max-flow)演算法解決之
D. 自行設計一個流網(flow network)(除s、t外具有4個節點，並具有10個edge)，解出其最小成本最大流。
Task 1
Task 2
Task 3
Carl
$24
$28
$24
Bob
$26
$32
$28
Alex
$24
$28
$30
Programming Problem Set 3
(P3A) 寫一個程式實作匈牙利演算法
(P3B) 寫 一個程式實作Dijkstra演算法
(P3C) 寫一個程式實作Edmonds- Karp演算法
(P3D) 寫一個程式實作Bellman-Ford演算法
(P3E) 寫一個程式實作Min-Cost Max-Flow演算法 (兩倍加分)
- 13. (6/7) RSA演算法 (RSA.pptx): Problem Set 13:
Problem Set 12:
A. 證明最適裝箱(best-fit bin packing)演算法的近似比例界(approximation ratio bound)為2。
B. 使用2-近似演算法(2-approximation algorithm)來解決以下圖的頂點覆蓋問題(vertex cover problem)。（註: 須描述在執行演算法過程的每個中間結果。）
C. 使用歐拉旅途演算法來找出以下圖的歐拉旅途。（註: 須描述在執行演算法過程的每個中間結果。）
D. 將以自然語言撰寫的「無向圖歐拉旅途/路徑演算法」改為以虛擬碼撰寫
E. 以自然語言撰寫「有向圖歐拉旅途/路徑演算法」
F. 以虛擬碼撰寫「有向圖歐拉旅途/路徑演算法」
G. 分析兩個演算法的時間複雜度
Programming Problem Set 4
(P4A) 寫一個程式實作歐拉旅途演算法
(P4B) 寫 一個程式實作0/1背包問題動態規劃演算法
A. 隨意選兩個質數(選擇p=5, q=7)，以產生RSA公鑰與密鑰。 (e 必須與phi(n)互質且大於1小於phi(n))
B. 隨意選兩個質數(選擇p=3, q=11)，以產生RSA公鑰與密鑰。 (e必須與phi(n)互質且大於1小於phi(n))
C. 隨意選兩個質數(選擇p=3, q=7)，以產生RSA公鑰與密鑰。 (e必須與phi(n)互質且大於1小於phi(n))
D. 隨意選兩個質數(選擇p=5, q=11)，以產生RSA公鑰與密鑰。 (e必須與phi(n)互質且大於1小於phi(n))
E. 若(23, 143)為RSA公鑰，(47, 143)為RSA私鑰，若明文M=12，求以公鑰加密的密文C=?驗證你求出的密文以私鑰解密後得到明文12。
F. 若(23, 143)為RSA公鑰，(47, 143)為RSA私鑰，若明文M=34，求以公鑰加密的密文C=?驗證你求出的密文以私鑰解密後得到明文34。
G. 若(23, 143)為RSA公鑰，(47, 143)為RSA私鑰，若密文C=56，求以私鑰解密後得到明文M=?驗證你求出的明文以公鑰加密後得到密文56。
H. 若(23, 143)為RSA公鑰，(47, 143)為RSA私鑰，若密文C=99，求以私鑰解密後得到明文M=?驗證你求出的明文以公鑰加密後得到密文99。
I. 依據歐拉定理，求7^9999的個位數?
J. 給定一0/1背包問題，其中背包容量W=10，三物品重量分別為10, 3, 5，而物品利潤分別為40, 20, 30，使用動態規劃法來解此0/1背包問題。(你必須列出表格的變化細節)
K. 已知0/1背包問題是一個NPC問題，說明為何0/1背包問題也是一個弱NPC問題(weakly NPC problem)。
L. 以下為子集合加總(subset sum problem)問題的描述：給定一非零整數集合S以及一特定整數M，是否存在一個S的非空子集合其元素加總值等於M？例如，給定集合S={−7, −3, −2, 5, 8}及一特定整數0；或給定集合S={1,3, 4, 6, 8}及一特定 整數8。說明子集合加總問題可以變轉為0/1背包問 題。
