(23.03.10) algorithms S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2008) 책 읽고 정리하기 http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf 정리한 내용 2.4 medians (+ quick sort) Medians quick sort quick sort python code def quick_sort(input, start, end): if start >= end: return input pivot = start left = start+1 right = end while left right: input[right], input[pivot] = inpu..

(23.03.07) algorithms S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2008) 책 읽고 정리하기 http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf 정리한 내용 2.1 multiplication 2.2 recurrence relations 2.3 merge sort Divide-and-Conquer algorithms divide: 문제를 sub-problem 으로 쪼갠다. conquer: cub-problem을 recuresively 하게 해결한다. combine: sub-problems의 solutions를 combine 한다. (+ 예전에 수업들으면서 정..

(2021.10.07) 알고리즘 수업들으면서 정리하기 5탄 3주차 내용 끝!! Divide-and-Conquer algorithms Divide-and-conquer를 이용하여 merge sort의 T(n) 계산 proof by telescoping 은 수업시간에 했음 ↓↓↓↓↓↓↓↓ proof by induction on n 은 과제로 했음 ↓↓↓↓↓↓↓↓ (답이 맞는지는 아직 모름..) Master Method for solving recurrences 과제로 했던 master method 문제들 ↓↓↓↓↓↓↓↓