【演算法】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 uniqueoptimal: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 treeOptimal algorithm: 2m - 1 comparisonsOracleat least 2m-1 comparisonsoptimal 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

演算法

数量较小时使用暴力法，否则将问题切成两等分分别利用演算法解决结合两方问题的答案并找出最大值

图示

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个点时，该点直接是maximal，否则切中位线分为SL与SR找出SL与SR各自的maximal纪录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.根据y值排序所有的点如果集合中只有一个点，回传无限根据x值找出中线，分为SL与SR找出SL与SR最距离最近的点，并取最小距离的为d

设定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 pointsOutput:A convex hull for S若点小余5个，使用穷举法根据x值找出中线，分为SL与SR分别为SL与SR找出全多边形利用合併法合併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.若点只有一个，回传根据x值找出中线，分为SL与SR找出SL与SR的Voronoi diagram从左右 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)