알고리즘(Foundations of Algorithms, Using C++ Pseudocode 3판)7,8,9장 솔루션

소개글

"알고리즘(Foundations of Algorithms, Using C++ Pseudocode 3판)7,8,9장 솔루션"에 대한 내용입니다.

7-30, 8-24, example 9.9, example 9.17 풀이이며 우수숙제풀이로 선정되었던 자료입니다.
숭실대학교 김** 교수 알고리즘 과제입니다.

목차

1. 7-30 Show that there is a case for Heapsort in which we get the worst-case time complexity of W (n) ≈ 2n lg n ∊ Θ (n lg n).
2. 8-24 Use induction to show that the worst-case time complexity of Alogrithm 8.6 (Selection Using the Median) is bounded approximately as follows:
W (n) <= 22n
3. example 9.9 cnf satisfiability reduces to clique decision problem
4. example 9.17 TSEDP

본문내용

TSOP가 NP-easy임을 증명하려면 NP문제를 해결 가능한 방법으로 TSOP가 해결 가능해야 한다. 이때 TSEDP가 활용된다. TSEDP는 존재하는지 여부를 찾는 결정문제이고, TSOP는 최적의 경로가 존재하는지를 생각하는 최적문제이다. 이때 TSEDP는 제일 짧은 거리(n개의 노드 거리가 모두 1이라고 할 때, n)~가장 긴 거리(n*제일 긴 노드 간 제일 긴 거리)로 경로를 상수범위로 잡을 수 있다. 그리고 polyalg를 이용해서 시작 노드 v1을 포함하는 거리 d를 만족하는 경로가 있는지 찾아본다. 이때 d를 바꿔가며 dmin을 찾아낼 수 있다.

참고 자료

없음