알고리즘 시험 준비 - [1/3 Homework]

 

이건 뭐 그냥 하면 된다. 

 

 

 

(b) -> 2n 이랑 n으로 하면 달라지네 굳!!

 

Problem 3 

 

(1)

 

(2)

(3)

 

 

(4)

 

(5)

(6)

(7)

 

g(n) 이 더큼 

 

(8)

 

 

(9)

 

 

(10)

 

 

 

 

다른 방법도 있는데 이것도 맞았기 때문에 이걸로 쳐도 될 거 같다. 

 

[1 1 1 0] -> 이거의 recursive 이니까 이렇게 하자 

 

To prove that points in S union pk forms the convex hull of {p1, p2,...}, we need to, by definition, verify that 1) S union pk form a convex polygon, 2) the polygon formed by S you pk contains all other points, and 3) such polygon is the smallest. To verify 1), we need to show that every three consecutive points in S union pk are turning left, and the algorithm guarantees this. To verify 2), we notice that the algorithm guarantees that all the points that are popped out from the stack are within some triangle formed by points in S union pk. To verify 3) we note that vertices of the polygon S union pk are form {p1,p2,...pk} and therefore it must be the smallest.