【演算法】L1-4

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)