======Algorithms, Spring 2009======
This course is an introduction to the design and analysis of computer algorithms. Its goal
is to acquaint the students with basic computer algorithms and their design principles and to
cultivate the students' ability in designing and analyzing algorithms independently. A particular
emphasis will be given to **principles of mathematical induction** and their use in designing
algorithms.

=====Announcements=====
  * 7/2: grade report available
  * 6/4: slides for NP-Completeness available; Note on Chapter 11 of [Manber] available
  * 6/4: slides for Dynamic Programming available
  * 5/17: {{courses:alg2009:mid2009_s.pdf|Suggested Solutions to Midterm Problems}} available
  * 5/7: {{courses:alg2009:hw6.pdf|Homework Assignment #6}} due on May 27 (Wednesday)
  * 5/7: {{courses:alg2009:hw5.pdf|Homework Assignment #5 (Programming Exercise #2)}} due on June 4
  * 5/7: slides for Graph Algorithms available
  * 4/24: {{courses:alg2009:hw4.pdf|Homework Assignment #4}} due on May 7
  * 4/24: {{courses:alg2009:hw3.pdf|Homework Assignment #3 (Programming Exercise #1)}} due on May 14
  * 4/14: partial solutions to {{courses:alg2009:hw1s.pdf|HW#1}} and {{courses:alg2009:hw2s.pdf|HW#2}} available
  * 4/9: slides for Data Structures and for Sorting, Searching, and String Processing available
  * 3/12: {{courses:alg2009:hw2.pdf|Homework Assignment #2}} due on April 1; slides for Design by Induction available
  * 3/9: slides for Analysis of Algorithms available; Note on Chapter 3 of [Manber] available
  * 2/26: {{courses:alg2009:hw1.pdf|Homework Assignment #1}} due on March 5; Note on Chapter 2 of [Manber] available
  * 2/23: slides for Introduction and Mathematical Induction available


=====Instructor=====
Yih-Kuen Tsay (蔡益坤), NTU IM Dept., 3366-1189, ''Xtsay@im.ntu.edu.twX'' (between the enclosing pair of X's).

=====Lectures=====
Thursday 2:20~5:20PM, Room 201, Management II.

=====Office Hours=====
Wednesday 1:30~2:30PM or by appointment, Room 1108, Management II.

=====Textbooks=====
//Introduction to Algorithms - A Creative Approach//, U. Manber, Addison-Wesley, 1989. \\ 
//Introduction to Algorithms, Second Edition//, T.H. Cormen, C.E. Leiserson, and R.L.
Rivest, MIT Press, 2001.

=====Syllabus/Schedule (with links to slides/notes)=====
The course will cover most of Manber's book plus supplementary mate-
rial, including a few chapters of the book by Cormen //et al.//:
  *Introduction - Chapter 1 (.5 week: 2/19a) [{{courses:alg2009:ch1slides.pdf|slides}}]
  *Mathematical Induction - Chapter 2 (1.5 weeks: 2/19b, 2/26) [{{courses:alg2009:ch2slides.pdf|slides}};{{courses:alg2009:ch2note1.pdf|note}}]
  *Analysis of Algorithms - Chapter 3 (1 week: 3/5) [{{courses:alg2009:ch3slides.pdf|slides}};{{courses:alg2009:ch3note1.pdf|note}}]
  *Design by Induction - Chapter 5 (2 weeks: 3/12, 3/19) [{{courses:alg2009:ch5slides.pdf|slides}}]
  *Data Structures: A Supplement - Sections 4.3.2,4.3.4,4.4,4.5 (1 week: 3/26) [{{courses:alg2009:ch4slides.pdf|slides}}]
  *Sorting, Searching, and String Processing - Chapter 6 (2 weeks: 4/9, 4/23)  [{{courses:alg2009:ch6slides.pdf|slides}}]
  *Graph Algorithms - Chapter 7 (2 weeks: 4/30, 5/7) [{{courses:alg2009:ch7slides.pdf|slides}}]
  *Selected Topics: Dynamic Programming, Mergeable Heaps, and Linear Programming - Chapters 15, 19, 20, and 29 of Cormen //et al.// (2 weeks: 5/14, 5/21) [{{courses:alg2009:dynamic_prog.pdf|Dynamic Programming}}]
  *NP-Completeness - Chapter 11 (2 weeks: 6/4, 6/11) [{{courses:alg2009:ch11slides.pdf|slides}};{{courses:alg2009:ch11note1.pdf|note}}]

=====Grading=====
Homework 20%, Participation 10%, Midterm (4/16) 35%, Final (6/18) 35%.

=====TA=====
Yi-Wen Chang (常怡文), 3366-1205, ''Xr97725004@ntu.edu.twX'' (between the enclosing pair of X's); \\ 
Chih-Pin Tai (戴智斌), 3366-1205, ''Xsteve750312@gmail.comX'' (between the enclosing pair of X's). \\ 
TA sessions will be scheduled prior to some of the class meetings (tentatively on 3/19, 4/9, 5/14, and 6/4), between 1:20 and 2:10PM.