**¬ì¥Ø¦WºÙ¡Gºtºâªk³]p»P¤ÀªR**

**¥ý×¬ì¥Ø**¡GµL (It is assumed that students in this course have had some exposure
to algorithms and their analysis.)

**±Ð®v**¡G¬x°êÄ_ ±Ð±Â¡]²z¾Ç¤j¼Ó 912«Ç¡^(gbhorng@cs.nchu.edu.tw)

**§U±Ð**¡G

** **

**±Ð§÷**¡GIntroduction
to algorithms, 2nd ed or 3rd ed. by Corman, Leiserson, Rivest, and Stein (2001) MIT Press
& McGraw-Hill.

**½Òµ{¥Øªº**¡GThe 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.

**½Òµ{¤jºõ**¡G
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)

**µû¤À**¡GHomework 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%