======Algorithms, Spring 2010======
The goal of this course 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.

=====Announcements=====
  * 7/09: grade report available; please send inquiries, if any, to the instructor by 12Noon July 10.
  * 5/31: {{courses:alg2010:hw10.pdf|HW#10}} due on June 11 
  * 5/31: slides for NP-Completeness and a note available 
  * 5/31: slides for Dynamic Programming available 
  * 5/17: {{courses:alg2010:hw9.pdf|HW#9}} due on May 31 
  * 5/17: slides for Advanced Graph Algorithms available 
  * 5/13: {{courses:alg2010:hw8.pdf|HW#8}} due on May 24 
  * 5/03: {{courses:alg2010:mid2010_s.pdf|Solutions to Midterm Problems}} available 
  * 5/03: slides for Basic Graph Algorithms available 
  * 4/26: {{courses:alg2010:hw5.pdf|HW#5}} and {{courses:alg2010:hw7.pdf|HW#7}} due on May 10 
  * 4/24: slides for String Processing available 
  * 4/16: solutions to selected homework problems: {{courses:alg2010:hw1s.pdf|HW#1}}, {{courses:alg2010:hw2s.pdf|HW#2}}, {{courses:alg2010:hw3s.pdf|HW#3}}, {{courses:alg2010:hw4s.pdf|HW#4}}
  * 4/13: {{courses:alg2010:hw6.pdf|HW#6}} due on April 26; HW#5 (a programming exercise) to be given later
  * 4/12: slides for Searching and Sorting available 
  * 3/29: {{courses:alg2010:hw4.pdf|HW#4}} due on April 8 (at 9AM, for this assignment) 
  * 3/28: slides for Data Structures: A Supplement available
  * 3/23: {{courses:alg2010:hw3.pdf|HW#3}} due on March 29 
  * 3/21: slides for Design by Induction available
  * 3/08: {{courses:alg2010:hw2.pdf|HW#2}} due on March 15 
  * 3/08: slides for Analysis of Algorithms and notes on Loop Invariants and Generating Functions available
  * 3/02: {{courses:alg2010:hw1.pdf|HW#1}} due on March 8  
  * 2/22: {{courses:alg2010:alg2010info.pdf|PDF version}} of this page (as of 2010/02/22, without the announcements)
  * 2/19: 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=====
Monday 2:20~5:20PM, Room 102, Management II.

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

=====Textbooks=====
  * [M] //Introduction to Algorithms - A Creative Approach//, U. Manber, Addison-Wesley, 1989. \\ 
  * [C] //Introduction to Algorithms, Third Edition//, T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, MIT Press, 2009.

=====Syllabus/Schedule (with links to slides/notes)=====
This course provides an introduction to the design and analysis of computer algorithms.
A particular emphasis is given to **principles of mathematical
induction** and their use in designing algorithms.
The course will cover most of Manber's book plus supplementary material, including
a few chapters of the book by Cormen //et al.//:
  *Introduction [M: Ch. 1; C: Ch. 1,2] (.5 week: 2/22a) [{{courses:alg2010:ch1slides.pdf|slides}}]
  *Mathematical Induction [M: Ch. 2; C: Ch. 4] (1.5 weeks: 2/22b, 3/1) [{{courses:alg2010:ch2slides.pdf|slides}};{{courses:alg2010:ch2note1.pdf|note}}]
  *Analysis of Algorithms [M: Ch. 3; C: Ch. 2,3,4] (1 week: 3/8) [{{courses:alg2010:ch3slides.pdf|slides}};{{courses:alg2010:ch3note1.pdf|note}}]
  *Design by Induction [M: Ch. 5] (2 weeks: 3/15, 3/22) [{{courses:alg2010:ch5slides.pdf|slides}}]
  *Data Structures: A Supplement [M: Ch. 4; C: Ch. 6,13,21] (1 week: 3/29) [{{courses:alg2010:ch4slides.pdf|slides}}]
  *Searching and Sorting [M: Ch. 6;  C: Ch. 6,7,8,9] (1.5 weeks: 4/12, 4/26a)  [{{courses:alg2010:ch6slides_a.pdf|slides}}]
  *String Processing [M: Ch. 6;  C: Ch. 32] (1.5 weeks: 4/26b, 5/3)  [{{courses:alg2010:ch6slides_b.pdf|slides}}]
  *Graph Algorithms [M: Ch. 7;  C: Ch. 22,23,24,25,26] (3 weeks: 5/10, 5/17, 5/24) [slides: {{courses:alg2010:ch7slides_a.pdf|Basic Graph Algorithms}}, {{courses:alg2010:ch7slides_b.pdf|Advanced Graph Algorithms}}]
  *Selected Topics: Dynamic Programming and Mergeable Heaps [C: Ch.15,19] (1 week: 5/31) [{{courses:alg2010:dynamic_prog.pdf|Dynamic Programming}}]
  *NP-Completeness [M: Ch. 11; C: Ch. 34] (2 weeks: 6/7, 6/14) [{{courses:alg2010:ch11slides.pdf|slides}};{{courses:alg2010:ch11note1.pdf|note}}]

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

=====TA=====
Yi-Wen Chang (常怡文), 3366-1205, ''Xr97725004@ntu.edu.twX'' (between the enclosing pair of X's); \\ 
Jen-Feng Shih (施任峰), 3366-1205, ''Xr98725050@ntu.edu.twX'' (between the enclosing pair of X's). \\ 
TA sessions will be scheduled prior to some of the class meetings (tentatively on 3/22, 4/12, 5/17, and 6/7), between 1:20 and 2:10PM.