Two approaches1) develope a more efficient algorithm.2) try to prove that more efficient algorithm is NOТ possible ==> Quit/Stop. 1) try to find a more efficient algorithm using NEW design : O(n^3) -> O(n^2) -> O(nlogn)2) try to find a greater(better) lower bound using computational analysis. Example1. Sorting: nlogn (comparison)-> omega(nlogn): lower bound already found, algoritms already ..

TSP: Traveling Salesman Problem - the most widely-used combinatorial optimization problem in computer science - minimization optimization - 택배 배달시스템에서 1,000개 boxes를 배달할 때, 노드들을 한 번씩만 거치고 출발 노드로 돌아와서 가장 먼저 퇴근하도록 하는 경로 Question: h-value estimation in TSP Maximization Optimization (0/1 KS) - h 값을 over-estimate- Overstimate하면 실수로 pruning하지 않음 0 - h = h* + alpha alpha 값이 작을 수록 higher pruni..

Brute-Force design: How to implement BF? Ex. 동전 2개의 모든 조합 나열→ For-loop 구현→ Graph 탐사: DFS, BFSEx. 미로 공원(Maze problem)Ex. 4-Queen problem: place 4 Queens onto 4×4 chess board → N-Queens problem(generalization) N-Queens Problem - Time complexity ex. 8-Queen problem → 64⁸ (permuation의 수) State-space tree(Search-space tree)→ 4-Queen state-space tree 모든 탐색 가능한 조합을 검사하고 나열할 필요가 있을까 → 상당 부분은 검사..

Q: Why is Greedy algorithm important?1. natural, simple, fast/easy implementation: (heuristic = 경험적) idea2. Test-bed: baseline performance 제공, - When we face new/open problems, 연구자들이 가장 먼저 접근하는 설계 전략. - 정밀도/정확도 (accuracy) 향상, 속도 증가, model size 감소의 기준이 됨3. May be "optimal.": optimal substructure local optimal → global optimal: proof required. example 1. 도둑 가방 (sack) → 보석방: 보석 (무게/부피, 가치)→ 보석 ..

Greedy AlgorithmsReal-life problems: mostly optimization problems.If we assume, "local optimal -> global optimal" "Greedy". Grabs data items in sequence, each time with BEST choice, without thinking Future.-> BEST choice: local optimal choice (o), global optima(x)-> In terms of viewpoint(intuition, heuristics(경험)) Example: MST(Minimum Spanning Tree) Designwhile NOT solved yet { Step 1. Se..

1. Dijkstra Algorithm (non-negative edge SSSP) - Negative edge weight -> can make negative weight cycle - Design: Greedy Algorithm - Time Complexity: O(v^2), |V|=n, --> O(n^2) (힙 사용 시, O(E log V)) - From a starting vertex S -> find SSSP RELAX(u, v, w) if d[v] > d[u] + w(u,v) then d[v] = d[u] + w(u, v) pi[v] 2. Bellman-Ford Algorithm (negative edges) - If negative weight e..

[Algorithm Design Approaches]1. Brute-Force, Full/Exhaustive Enumeration2. Divide and Conquer3. Dynamic programming Binomial Coefficient (이항계수)(n, k) = (n-1, k-1) + (n-1, k) (if 0 = 1 (if n == k, k == 0) B[n, k] = B[n-1, k-1] + B[n-1, k] if 0 B[n, k] = 1 if n == k, k == 0 solve B[5,3]B[5,3] = B[4,2] + B[4,3]B[4,2]..

DesignStep 1: Divide into (>=2)의 smaller problems (instances)Step 2: Solve each instances How to solve the step 2? (1) Recursively : divide and conquer : concise, natural, clear, 기계적 해법 (2) Iteratively, Sequentially (if the subprogram is small) : faster, save memory space,(system stack) --> recursion depth, stack depth : log(n) + 1Step ..