L1

Convex Hull

• 解法:Divide-and-conquer

One-Center Problem

• 解法:Prune-and-search

0/1 Knapsack Problem

• 給定:n個項目，每個項目含值與重量，及總重限制

• 目標:找價值最大，且不超過總重

• NP-complete
  

  (1-1)What strategy can solve the Convex Hull Problem and the One-Center Problem, respectively?
  
  (3-5)What is the optimal solution for the following knapsack problem?
  

L2

演算法比較

O(1) < O(log n) < O(n) < O(n log n) < O(n^2 ) < O(n^3 ) < O(2^n ) < O(n!) < O(n^n )

(1-2-1)Please compare the following complexity values: O(n), O(n!), O(2 ? ), O(log n), O(? ? )

Insertion Sort

定義

複雜度

• best case:O(n)

• worst case:O(n^2)

• average case:O(n^2)

    (1-3-2) Straight Insertion Sort Algorithm to sort 8, 5, 4, 9, 1, 3 
  

Binary Search

定義

複雜度

• best case:O(1)

• worst case:O(log n)

• average case:O(log n)

    (1-4-1) What is the number of comparisons we need at most to find a number in 2048 numbers by Binary search?
  

Selection Sort

定義

複雜度

• best case:O(n)
• worst case:O(n^2)
• average case:O(n log n)

Quick Sort

定義

複雜度

• best case:O(n log n)

• worst case:O(n^2)

• average case:O(nlog n)

    (1-4-2)What is the number of comparisons we need at least to sort 2048 numbers?
  
    (1-2-2)What are complexity values of the Binary Search and the Straight Selection Sort in worst case, and which one is better?
  
    (1-5)Give the following pairs of functions, what is the smallest value of n such that the first function is larger than the second one?
    (1) 2 ? , 6? 2 (2) ? 2 ,32?log2
  

2-D Ranking Finding

定義

• 各自點的支配數
• 支配:滿足x1 > x2 and y1 > y2
  

複雜度

O(n2)

Divide-and-Conquer

• 切中線為A B

• 找出A B各自Rank

• 根據A B點排序，更新B的值
  

• O(n log2n)

Lower Bound

定義

• 解法可以解決問題的最少複雜度
• not unique
• optimal:lower bound (n log n) 且algorithm with time complexity O(n log n)

Lower Bound of Sorting

• log(n!) = Ω(n log n)

• lower bound for sorting: Ω(n log n)

    (2-1)What is the number of comparisons we need at least to sort 6 numbers?
  

Heap sort

定義

• parent >= son
  

Heap sort Phase

Phase 1: Construction

Phase 2: Output

複雜度

• Worst case:O(n log n)

• Average case:O(n log n)

• Average case lower bound:O(n log n)

• Heap sort is optimal in the average case.

    (2-2)Please construct and output a max heap for the input data A(1) = 40, A(2) = 48, A(3) = 26, A(4) = 29, and A(5) = 4. Draw every tree for your heap construction and sorting output procedures.
  
    (2-3-1)What are complexity values of the Straight selection sort, the Quick sort and, the Heap sort in worst case?
  
  
    (2-3-2)Which algorithms is optimal in worst case? Why?
  

merging two sorted sequence

定義

• merging two sorted sequences A and B with lengths m and n
• 

複雜度

• Binary decision tree
  • Optimal algorithm: 2m - 1 comparisons
• Oracle
  • at least 2m-1 comparisons
  • optimal for m = n.

Problem Transformation

定義

• Problem A reduces to problem B (A ∞ B)

• if A can be solved by using any algorithm which solves B

• If A∞B, B is more difficult
  

• T(tr1 ) + T(tr2 ) < T(B) T(A) <= T(tr1 ) + T(tr2 ) + T(B) <= O(T(B))

• Sorting ∞ Convex hull(lower bound:Ω(n log n)

• Sorting ∞ Euclidean MST(lower bound:Ω(n log n)

    (2-4)If problem A can reduce to problem B, which problem is more difficult? Why?
  
    (2-5)What is the lower bound of the Euclidean Minimal Spanning Tree problem? Why
  

L3

Minimum Spanning Trees (MST)

• a spanning tree with the smallest total weight.
  

Kruskal’s Algorithm for Finding MST

定義

• SET and UNION algorithm:檢查迴圈
  

複雜度

• O(|E|log|E|) = O(n^2 log n), where n = |V|.

Prim’s Algorithm for Finding an MST

定義

複雜度

• O(n^2), n = |V|

The Single-Source Shortest Path Problem

Dijkstra’s Algorithm to Generate Single Source Shortest Paths

定義

複雜度

• O(n2)

• optimal

    (3-4)What is the time complexity of Dijkstra’s algorithm? Why?
  

2-way merging

定義

• Example: 6 sorted lists with lengths 2, 3, 5, 7, 11 and 13
  

複雜度

• O(n log n)

Huffman codes

(3-3)For the seven messages (M1, M2, …, M7) with access frequencies (q1, q2, …, q7) =(3, 6, 7, 9, 12, 13, 16), please obtain a set of optimal Huffman codes and draw itsdecode tree

The minimal cycle basis problem

定義

• 3 cycles:
  • A1 = {ab, bc, ca}
  • A2 = {ac, cd, da}
  • A3 = {ab, bc, cd, da}
• Cycle basis: {A1 , A2 } or {A1 , A3 } or {A2 , A3 }
• minimal cycle basis is {A1 , A2 }

演算法

• 定義最小cycle數為k
  • |E| - |V| + 1
• 以權重排序所有cycles
• 分別連接cycle，檢查是否以連接，若有則取消cycle(高斯消去法Gaussian elimination)
• cycle數等於k時結束

複雜度

The 2-terminal One to Any Special Channel Routing Problem

定義

演算法

• P1 is connected Q1.
• pi連接到qJ，檢查pi+1是否能連到gj+1,如果密度+1，則嘗試連接gj+1到qj+2
• 重複第二步直到pi連完

L4 The Divide-and-Conquer Strategy

Finding the maximum

演算法

• 1. 數量較小時使用暴力法，否則將問題切成兩等分
• 2. 分別利用演算法解決
• 3. 結合兩方問題的答案並找出最大值

圖示

Time complexity

2-D Maxima Finding Problem

定義

• maxima:滿足不被其他點支配

    支配:x1 > x2 and y1 > y2
  

演算法

• Input:A setS of n planar points.
• Output:The maximal points of S
• 1. 當只有1個點時，該點直接是maximal，否則切中位線分為SL與SR
• 2. 找出SL與SR各自的maximal
• 3. 紀錄SR中最大的y值，若SL的maxima 小於y值則移除
     

Time complexity

• Step 1: O(n)
• Step 2: 2T(n/2)
• Step 3: O(n)
• Assumen=2k T(n)=O(nlogn)

The Closest Pair Problem

定義

Given a set S of n points, find a pair of points which are closest together.

演算法

• Input:A set S of nplanar points.
• Output:The distance between two closest points.
• 1. 根據y值排序所有的點
• 2. 如果集合中只有一個點，回傳無限
• 3. 根據x值找出中線，分為SL與SR
• 4. 找出SL與SR最距離最近的點，並取最小距離的為d

• 5. 設定x中線之x+d與x-d的範圍，記錄所有點的y值，若有點距離小於d則取代

        (4-3)Give a set S = {(7, 1), (5, 8), (2, 6), (1, 2), (6, 5), (5, 3), (8, 7), (10, 5)} of planar points, please use the Divide-and-Conquer method to find a pair of points which are closest together and calculate its distance. Please explain each step of your solution
     

Time complexity

The Convex Hull Problem

定義

The convex hullof a set of planar points is the smallest convex polygon containing all of the points.Concave polygon: Convex polygon:

演算法

• Input :A set S of planar points
• Output:A convex hull for S
• 1. 若點小餘5個，使用窮舉法
• 2. 根據x值找出中線，分為SL與SR
• 3. 分別為SL與SR找出全多邊形
• 4. 利用合併法合併SL與SR

Time complexity

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

The Voronoi Diagram Problem

定義

找出每個點之間的中線

演算法

• Input:A set S of n planar points.
• Output:The Voronoi diagram of S.
• 1. 若點只有一個，回傳
• 2. 根據x值找出中線，分為SL與SR
• 3. 找出SL與SR的Voronoi diagram
• 4. 從左右 Convex Hull 的外公切線的中垂線開始行進，一旦撞到左右 Voronoi Diagram ，就改變行進方向。途中清除多餘的 Voronoi Diagram

特色

• 邊的數量<=3n-6(n:點)

• 頂點數量<=2n-4

    (4-2)Please take a graphic example to show how to merge two Voronoi Diagrams, and explain the graph
  
    (4-4)Give a set S = {(7, 1), (5, 8), (2, 6), (1, 2), (6, 5), (5, 3)} of planar points, please draw the Voronoi Diagram and indicate its Voronoi points, Voronoi edges, and Voronoi polygons
  

從Voronoi Diagram建立Construct a Convex

演算法

Time complexity

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

    (4-5)How to find the convex hull in a set S of planar points and a Voronoi diagram, respectively

FFT

藉由DFT反轉，可得複雜度 O(n log n)