Syllabus: Advanced Algorithms I

Instructor: Guan-Shieng Huang (黃光璿)

• Office: Room 314, Science and Technology Building 3

• Office Hours: 2:00~4:00 pm, Friday

• Web Site: http://staffweb.ncnu.edu.tw/shieng/

• Email: shieng@ncnu.edu.tw

Time and Location:

• Room 118, Science and Technology Building 3

• 3:10~6:00 pm, Tuesday

Teaching Assistant: 吳季諺 、吳嘉森

• Office: Room 210, Science and Technology Building 3

• Email: s97321509@ncnu.edu.tw, netsphere@xuite.net

Text Book: 

• Introduction to the Design and Analysis of Algorithms, by R.C.T. Lee, S.-S. Tseng, R.-C. Chang, and Y. T Tsai, McGraw-Hill Education, 2005, ISBN-13: 978-0071243469.

References:

• Approximation Algorithms, by Vijay V. Vazirani, Springer, 2004, ISBN-13: 978-3540653677.

• Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, by G. Ausiello (Author), P. Crescenzi (Author), V. Kann (Author), Marchetti-sp (Author), Giorgio Gambosi (Author), Alberto M. Spaccamela, Springer, 2003, ISBN-13: 978-3540654315.

• Computers and Intractability: A Guide to the Theory of NP-Completeness, by M. R. Garey (Author), D. S. Johnson, W. H. Freeman, 1979, ISBN-13: 978-0716710455.

Prerequisites:

• Data Structures and Algorithms

• Discrete Mathematics

Description:

• The Greedy Method

• The Divide-and Conquer Strategy

• The Searching Strategies

• Prune-and-Search

• Dynamic Programming

• The Theory of NP-Completeness          

Grading Policy:

        Every student taken this course should follow three rules: hand in your homework on time, do it by yourself, and code programs by your own effort. Cheating is absolutely disallowed and no late homework will be accepted. The distribution of grading is as follows:

                70% Examinations (30% mid-term, 40% final)

                30% Homework and Programming assignments

As for the programming languages, C, C++ and Java are preferred.