Advanced Algorithms

News

Important dates

• 2024/10/23 Midterm exam

• 2024/12/18 Final exam

Info

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

  • Email: hlwang@ntnu.edu.tw

• Teaching assistants: 

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

• Course: Advanced Algorithms

• Semester: 113-1

• Credit: 3 

• Time: Wed. 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: 2024/09/11) Reduction, NP-hardness, NP optimization problems, and approximation algorithms 

• Slide_02 (last update: 2024/10/08) Combinatorial approximation algorithms 

• Slide_03 (last update: 2024/11/05) FPTAS 

• Slide_04 (last update: 2024/11/14) PTAS

• Slide_05 (last update: 2024/11/26) LP-based approximation: rounding

• Slide 06  (last update: 2024/11/26) LP-based approximation: the primal-dual schema 

• Slide 07  SDP-based approximation