科目名稱:演算法設計與分析

 

先修科目:無 (It is assumed that students in this course have had some exposure to algorithms and their analysis.) 

 

教師:洪國寶 教授(理學大樓 912室)(gbhorng@cs.nchu.edu.tw)

 

 

助教

 

教材Introduction to algorithms, 2nd ed or 3rd ed. by Corman, Leiserson, Rivest, and Stein (2001) MIT Press & McGraw-Hill.

 

課程目的:The goal of this class is to present fundamental problem-solving techniques, for designing efficient computer algorithms, proving their correctness, and analyzing their performance. We will deal with many different areas of applications. However, we will always try to concentrate on things that are important to know and interesting to study, including: - Data structures: More advanced data structures such as binomial heaps and Fibonacci heaps. - Algorithm design: Including techniques such as divide and conquer, dynamic programming, and greedy algorithms. - Algorithm analysis: How to analyze the time and space behavior. - Graph algorithms: Such as topological sort, minimum spanning tree, and shortest paths. - NP-completeness: Understanding why some problems are particularly hard, and how they are related by reductions.

         

 

課程大綱   1. Introduction (1-4) 

                        2. Data structures (10-14) 

                        3. Dynamic programming (15) 

                        4. Greedy methods (16) 

                        5. Amortized analysis (17) 

                        6. Advanced data structures (6, 19-21) 

                        7. Graph algorithms (22-25) 

                        8. NP-completeness (34-35) 

                        9. Other topics (5, 27,31)

 

評分Homework       25% (You may collaborate when solving the homework, however when writing up the solutions you must do so on your own. Handwritten only.)

            Midterm exam     30% (Open book and notes)

            Final exam           30% (Open book and notes)

            Class participation  15%