Introduction to Algorithms, Third Edition이 다음 달 발간될 예정입니다

알고리즘 분야의 절대적인 바이블의 하나로 인정받는 Introduction to Algorithms, Third Edition이 다음 달 발간된다고 합니다.

이번 에디션에는 Van Emde Boas trees와 Multithreaded algorithms 이 두 챕터가 새롭게 포함되었습니다. 그리고 "Divide-and-Conquer" 챕터에도 몇 가지 내용이 추가되었습니다. 특히 Dynamic programming과 Greedy algorithm을 개선된 방법으로 다루었으며, Edge-based flow라는 새로운 개념이 추가된 것이 "인상적이다"라고 하네요.

연습문제도 새로운 내용이 추가되었습니다.

한 가지 덧붙이자면, 제가 특별히 new edition과 연관된 사람은 아닙니다만, 얼마전에 Hamiltonian-cycle problem(HAM-CYCLE)이 NP-complete problem이라는 것을 증명하는 과정에서 off-by-one 버그가 발견되어 보고를 했었습니다. 좀 자세하게 설명하면,

VERTEX-COVER문제가 HAM-CYCLE문제로 polynomially reducible(NP-hard)하다는 것을 증명하는데, edge가 추가되는 과정을 설명하다가 off-by-one 버그가 포함되었습니다.

Second edition에서는 아래와 같이 수정해주시면 됩니다.
----------------------------------------------------------------------
Page 1011, lines 18.
Change ``Include edges { ([Uj, Uj(i), 6], [Uj, Uj(i+1), 1]) : 1 ≤ i ≤ degree(uj)},''
to ``Include edges { ([Uj, Uj(i), 6], [Uj, Uj(i+1), 1]) : 1 ≤ i ≤ degree(uj)-1},''.
----------------------------------------------------------------------

Third edition은 아직 출간이 안 된 관계로 몇 쪽에 해당 내용이 들어가는 지 모르겠습니다만, 공동저자인 다트모스대학에 Tom Cormen교수님이 보내주신 레터에 따르면 (제가 지적한 내용이 버그로 확인될 경우)이미 첫쇄가 완료된 과정이라서 first print에는 이 버그가 어쩔 수 없이 포함된다고 합니다.(구입하실 분들 참고하세요!)

그리고 Tom Cormen교수님은 버그임을 확인 해주셨는데, 아직 공동 저자분들이 confirm 못해서 협의가 끝나는데로 답장을 준다고 하니까, 이번주 중에는 확정이 될 것 같습니다.

본의 아니게 출간도 안 된 책에 버그를 보고하게 되었네요.