Advanced Algorithms

News

Important dates

• 2025/10/21 Midterm exam

• 2025/12/16 Final exam

Info

• Lectured by Hung-Lung Wang (王弘倫)

  • Email: hlwang AT ntnu DOT edu DOT tw

• Teaching assistants: 

  • 孫士明 (資訊工程學系 碩士班) 

• Course: Advanced Algorithms

• Semester: 114-1

• Credit: 3 

• Time: Tue. 9:10-12:10

• Classroom: 理圖001

• Prerequisite: Algorithms, Discrete math, Formal language/Automata theory 

Grading

• Midterm (oral) 40% 

• Final (oral) 40%

• Participation 20%

Textbooks

• V. Vazirani, Approximation algorithms, Springer, 2003.

• T. H. Cormen, C.L. Leiserson, R. L. Rivest, Introduction to Algorithms, 3rd Ed., MIT Press, 2009.

Syllabus

• Approximation algorithms

  • Combinatorial algorithms

  • Polynomial-Time Approximation Scheme (PTAS)

  • LP-based approximation

  • SDP-based approximation

• Selected topics

Slides

• Slide_01 (last update: 2025/09/01) Reduction, NP-hardness, NP optimization problems, and approximation algorithms 

• Combinatorial approximation algorithms 

• FPTAS 

• PTAS

• LP-based approximation: rounding

• LP-based approximation: the primal-dual schema 

• SDP-based approximation