MJay

Homework 2 Find Upper Envelop of the line intersection. Half-Plane -> Convex Hull using duality between the set of points and a set of lines. N lines -> N points in the dual plane. Upper Envelop -> Easier hull of the convex Using Grahams’s scan algorithm (nlogn) y축 젤 작은거를 찾는다. 그리고 작은거 기준으로 counter-clockwise 로 되는 걸 찾는다. 이걸 각각의 점에서 한다. 총 8개의 점이 convex hull을 구성하는 걸 알고있기떄문에 각각의 Iteration 별로 한개의 점을 찾..

이건 뭐 그냥 하면 된다. (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)..

Matroid 이건 그냥 외워야 할 거 같다. Leftist Tree 는 Rank 즉 the number of nodes on shortest path Minimum Spanning Tree는 이것도 기억하면 될꺼같은데 어떤 weight 가 다른 어떤 edge의 weight 보다 크면 이건 MST에 속하지 않는다.

Quiz 2 재밌는 문제이네 DP 에서 보면 전단계였었나? 아예 전단계는 아니네 이상하다 맞을꺼같은데 아닌게 또 신기하네 ㅎㅎ a2 -> a5 -> a7 1 2 3 4 5 6 7 8 9 2 5 7 8 9 4 2, 10, 8, 6, 14, 9, 11, 15 1 2 3 4 5 6 7 8 9 9 7 1 3 8 2 10 아 True 같은데 왜 글지 반례가 있을꺼같은데 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 위키에서 가져옴 0, 2, 6, 9, 11, 15. 여기서 6까지만 봐보면 0, 8, 4, 12, 2, 10, 6, 똑같지만 14까지 봐보면 0, 8, 4, 12, 2, 10, 6, 14 까지 가버린다. 그래서 답이 아니다. 이거 생각해서 False 라고..

이건 쉽지 뭐

Def(matroid) - Let x be an infinite cost. S - subsets X A belong to S, we call A “independent” (X, S) forms a matroid if hereditary property: if A belongs to S, then for any subset of A, A belongs to S (유전이지 왜냐면 A1 은 A에서 나온 애니까) A 랑 B랑 둘 다 S에 속하고 A보다 B가 더 크면 A에 속하지 않고 B에 속하는 x 가 있을 것이다. 그리고 그건 A 랑 X 랑 Union 해도 S에 속한다. exchange라는 게 B에 속하는 걸 A에 줘도 된다는 뜻으로 보인다. Optimization Problem Input - matroid ..

notes-2019-10-07 undirected graph 에서 V1 = V and E

일단 하나씩 적어보자 PQ는 V- Ak* 속하지 않는 Vertices를 가지고 있다. dist(u) 는 s to v로 가는 length를 가지고 있다. 그리고.그리고 그건 A*k에 속하는 Vertecies를 통해서다. V * 가 PQ에서 사라지는 순간 -> dist(v*)와 s에서 v*로 가는 거리가 같아진다. 그 다이 스트라에서 weight를 뜻하는 거 같네 별 의미가 없는 거 같은데 그냥 문제를 얼른 풀어봐야겠다. Running Time은 Delete Min에서 VlogE Decrease Key에서 ElogV (V+E) logV 이제 Binary Heap을 사용하여 구현을 할 수도 있다. Heap은 min-heap 이랑 max-heap을 사용할 수 있다. 이게 쉬운 거니 넘어가자 이건 뭐 당연한 건데..