[강의정리] 알고리즘 기말정리

---

Minimum Spanning Tree

• 정의
• 알고리즘(Prim’s and Kruskal’s) complexities, 이게 greedy appraoch인가??

Dijkstra’s Algorithm for Single-Source Shortest Paths

• 소스코드레벨 구현

Knapsack Problem (fractional & 0-1) 차이

• Greedy approach로 Optimal(최적)한 Solution을 찾을 수 있는가? 어떨때 가능한가?
• Greedy vs. Dynamic Programming
• Backtracking & Branch-and-Bound
  • DPS, BPS, Best-First searches…
  • pruning

TSP (Traveling Salesperson Problem)

• DP vs. Greedy? or Branch-and-Bound?
• 유전 알고리즘, 다른것들과 차이, 장단점, 최적의 Solution을 가질 수 있는가?

Search Algorithms

• Actual tree searches…

  • 방문하는 노드들 & 최적경로 ()
  • 방문 트리 구성

• 장단점

• 최적의 해를 찾는 보장은?

• Complexities & 구현방법(data structures?)