목록PSU/CSE 565 - Algorithm (30)
MJay
이 시국에 계획을 짜보자 알고리즘 계획을 짜보자 퀴즈 - 3개 과제 - 3개 파일 - 13개 토 일 월 화 수 5일밖에 없다고? 4개씩 은 해야겠네 난 지금 연구가 더 중요한거 같으니 일단 그냥 하자 2시간 잡으면 되겠네 To-Do Lists 1. 연구 2. 퀄리파잉 - 알고 3. 퀄리파잉 - OS 4. 수업 - Algorithm 5. 수업 - Computer Architecture 6. Colloquim 남은 시간에 알고를 하고 OS를 한다.. 복습을 해야겠네. 3시간 하면 되려나 7시부터 10시 알고만 해도 될꺼같다. 이번주는 사실 - 3시간은 해야 다 끝날거같음
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 ..
Merge two binary hea takes O(n) time 이게 일반적인 사실이다. 이걸 O(logn)으로 하기 위해서 쓰는게 leftist tree 이다. rank 라는게 shortest path from v to NULL leftist propoerty -> T 에 있는 vertex 를 가지고 봤을떄 vertex 의 left child 의 rank 가 오른쪽보다 항상 같거나 많다. Fact - rank(root) = O(logn) 이다 당연하다 이건 그래서 이 둘을 Merge 하기 하려고 한다. 쨋든 O(logn) 으로 바뀐다. 그릭 봐서 swap 을 해준다. ㅇ Find Min - return root delete - min 은 root끼리 merge 한다. insert - Merge (PQ..
CSE 560 을 봐보자 2019-10-02.pdf PQ stores the vertices in V - Ak* (전체에서 A를 뺀 것) Ak* = {V1*, V2*, Vk*} ak가 아마 s 랑 v 랑 다 같이 Ak에 속한다고 일단 생각하자 V* 가 PQ 로 부터 지워지면 - dist(v*) = distance (s, v*) v1, v2, v3, v4, v5 지금 이게 뭐를 하고있지? Binary Heap 을 얘기하는 건가? 그냥 그래프를 그려볼까 Binary-Heap 은 find-min -> O(1) min heap delete min, decrease-key, insert -> log(n) # times -> delete min, find-min, insert - Vertex 랑 관련이 있고 dec..
다시 정리 Crossing Edge 는 항상 MST 에 속한다. 증명 - 다른 crossing edge를 할 경우 결국 crossing edge 기존꺼가 더 작다고 해서 접근한다. Prim은 Priority Queue 를 사용해서 min crossing edge를 찾는다. Kruskal은 Cycle https://progresivojs.tistory.com/7 https://progresivojs.tistory.com/3
Prim Algorithm crossing edge 의 최소를 찾기 V 는 Vertex 에서 S 가 뭘까? 그냥 Vertex Set을 뜻함 이거는 좀 찾아봐야겠다. Kruskal 은 알겠다. 뭐 대충은 알겠다 일단 한국말부터 알아야할듯..
notes-2019-10-07 undirected graph 에서 V1 = V and E
알고리즘은 책으로 시작하는게 좋아보인다. 일단 책으로 어디까지 했는지 다 정리를 해보는게 좋을꺼 같다. CSE 565 KT 위주로 보면 될꺼같다. 모르는거 위주로 봐야할꺼같다. 2.2 2.4 2.5 4.4 4.5 5.1 5.2 5.3 5.4 5.5 5.6 6.1 6.5 6.6 6.7 6.8 6.10 homework 랑 퀴즈도 해야한다. 책을 먼저 보고 해결을 해보자 2.2 Asymptotic Order of Growth 중요한거랑 모르는거랑만 정리를 해보자면 O, Theta, 하나가 뭐드라 근데 이건 이제 고수다. Pass 2.4 A Survey of Common Running Times Merging Two Sorted Lists O(n log n) Time 이 정도 2.5 A More Complex ..
Algorithm 문제 푸는 중 lines -> points Graham Scan’s Algorithm. Upper envelope lower hull Given Dataset, 이미 convex hull이 존재한다고 했으니, Counter-clock-wised 로 되는 point만 찾으면 된다. next point as the starting point Convex Polygon 에 속하는게 Convex Hull이다.