======Algorithms, Spring 2012======
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=====
  * 07/04: grade report available (updated 07/09); please send inquiries, if any, to the instructor by 2PM July 07.
  * 06/11: slides for Reduction and a note on NP-Completeness available.
  * 06/11: slides from TA sessions: {{courses:alg2012:hw6slides.pptx|HW#6}}, {{courses:alg2012:hw7slides.pptx|HW#7}},  {{courses:alg2012:hw8slides.pptx|HW#8}},  {{courses:alg2012:hw9slides.pptx|HW#9}}.
  * 06/04: slides for NP-Completeness available.
  * 05/28: {{courses:alg2012:hw10.pdf|HW#10}} due on June 11.
  * 05/28: slides for Dynamic Programming available.
  * 05/14: {{courses:alg2012:hw9.pdf|HW#9}} due on May 28.
  * 05/14: slides for Advanced Graph Algorithms available.
  * 05/14: {{courses:alg2012:hw8.pdf|HW#8}} due on May 21.
  * 05/02: {{courses:alg2012:alg2012mid_s.pdf|Suggested Solutions to Midterm Problems}} available (revised on 05/06).
  * 04/30: {{courses:alg2012:hw7.pdf|HW#7}} due on May 7.
  * 04/23: slides for String Processing and Basic Graph Algorithms available.
  * 04/13: old exams: 1996-2011.
  * 04/13: slides from TA sessions: {{courses:alg2012:hw1slides.pptx|HW#1}}, {{courses:alg2012:hw2slides.pptx|HW#2}},  {{courses:alg2012:hw3slides.pptx|HW#3}},  {{courses:alg2012:hw4slides.pptx|HW#4}}.
  * 03/26: reminder: TA session on Apr. 9, 1:20-2:10PM.
  * 03/26: reminder: no class meeting on Apr. 2.
  * 03/26: {{courses:alg2012:hw6.pdf|HW#6}} due on Apr. 16.
  * 03/25: slides for Searching and Sorting available.
  * 03/19: {{courses:alg2012:hw5.pdf|HW#5}} due on Apr. 9.
  * 03/18: slides for Data Structures (A Supplement) available.
  * 03/12: reminder: TA session on Mar. 19, 1:20-2:10PM.
  * 03/12: {{courses:alg2012:hw4.pdf|HW#4}} due on Mar. 26.
  * 03/11: slides for Design by Induction available.
  * 03/05: {{courses:alg2012:hw3.pdf|HW#3}} due on Mar. 19.
  * 03/03: {{courses:alg2012:hw2.pdf|HW#2}} due on Mar. 12.
  * 03/03: slides for Analysis of Algorithms and a note on Solving a Recurrence Relation with Generating Functions available.
  * 02/20: {{courses:alg2012:hw1.pdf|HW#1}} due on Mar. 5.
  * 02/20: eight copies of [Manber 1989] available for loan; please contact TAs Lai or Chang.
  * 02/19: slides for Introduction and Mathematical Induction and a note on Proving a Loop Invariant available.

=====Instructor=====
[[http://im.ntu.edu.tw/~tsay/|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=====
Monday 1:30~2:00PM, Thursday 1:30~2:00PM, or by appointment, Room 1108, Management II.

=====TA=====
Jing-Jie Lin (林靖婕), 3366-1205, ''Xgrace6349@gmail.comX'' (between the enclosing pair of X's); \\ Jui-Shun Lai (賴瑞舜), 3366-1205, ''Xnarration.lai@gmail.comX'' (between the enclosing pair of X's). \\ Wei-Hsien Chang (張暐獻), 3366-1205, ''Xb96705043@ntu.edu.twX'' (between the enclosing pair of X's). \\
TA sessions will be scheduled prior to some of the class meetings between 1:20 and 2:10PM.

=====Textbooks=====
  * [M] //[[http://www.amazon.com/Introduction-Algorithms-Creative-Udi-Manber/dp/0201120372/ref=sr_1_1?s=books&ie=UTF8&qid=1329702126&sr=1-1|Introduction to Algorithms - A Creative Approach]]//, U. Manber, Addison-Wesley, 1989. (Five copies of this book have been put on reserve at NTU Library in the 教師指定參考書區 under the name "BM-4演算法".) \\ 
  * [C] //[[http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844/ref=pd_bxgy_b_img_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.// (Note: A TA session will precede a class meeting whose date is marked with an *. There are four TA sessions on 3/19, 4/9, 5/21, and 6/4, making up the missed class meeting on 4/2.)
  *Introduction [M: Ch. 1; C: Ch. 1,2] (.5 week: 2/20a) [slides: {{courses:alg2012:ch1slides_print.pdf|print}},{{courses:alg2012:ch1slides.pdf|display}}]
  *Mathematical Induction [M: Ch. 2; C: Ch. 4] (1.5 weeks: 2/20b, 3/3) [slides: {{courses:alg2012:ch2slides_print.pdf|print}}, {{courses:alg2012:ch2slides.pdf|display}}; notes: {{courses:alg2012:ch2note1.pdf|Proving a Loop Invariant}}]
  *Analysis of Algorithms [M: Ch. 3; C: Ch. 2,3,4] (1 week: 3/5) [slides: {{courses:alg2012:ch3slides_print.pdf|print}}, {{courses:alg2012:ch3slides.pdf|display}}; notes: {{courses:alg2012:ch3note1.pdf|Solving a Recurrence Relation with Generating Functions}}]
  *Design by Induction [M: Ch. 5] (1 week: 3/12) [slides: {{courses:alg2012:ch5slides_print.pdf|print}}, {{courses:alg2012:ch5slides.pdf|display}}]
  *Data Structures: A Supplement [M: Ch. 4; C: Ch. 6,13,21] (.5 week: 3/19a*) [slides: {{courses:alg2012:ch4slides_print.pdf|print}}, {{courses:alg2012:ch4slides.pdf|display}}]
  *Searching and Sorting [M: Ch. 6;  C: Ch. 6,7,8,9] (2.5 weeks: 3/19b, 3/26, 4/9*) [slides: {{courses:alg2012:ch6slides_a_print.pdf|print}}, {{courses:alg2012:ch6slides_a.pdf|display}}]
  * **Midterm** (**2012/04/16**)
  *String Processing [M: Ch. 6;  C: Ch. 32] (1.5 weeks: 4/23, 4/30a) [slides: {{courses:alg2012:ch6slides_b_print.pdf|print}}, {{courses:alg2012:ch6slides_b.pdf|display}}]
  *Graph Algorithms: Basic [M: Ch. 7;  C: Ch. 22,23,24,25,26] (1.5 weeks: 4/30b, 5/7) [slides: {{courses:alg2012:ch7slides_a_print.pdf|print}}, {{courses:alg2012:ch7slides_a.pdf|display}}]
  *Graph Algorithms: Advanced [M: Ch. 7;  C: Ch. 22,23,24,25,26] (1 week: 5/14) [slides: {{courses:alg2012:ch7slides_b_print.pdf|print}}, {{courses:alg2012:ch7slides_b.pdf|display}}]
  *Dynamic Programming [C: Ch.15] (1 week: 5/21*) [slides: {{courses:alg2012:dynamic_prog_slides_print.pdf|print}}, {{courses:alg2012:dynamic_prog_slides.pdf|display}}]
  *Reduction [M: Ch. 10; C: Ch. 29] (1 week: 5/28) [slides: {{courses:alg2012:ch10slides_print.pdf|print}}, {{courses:alg2012:ch10slides.pdf|display}}]
  *NP-Completeness [M: Ch. 11; C: Ch. 34] (2 weeks: 6/4*, 6/11) [slides: {{courses:alg2012:ch11slides_print.pdf|print}}, {{courses:alg2012:ch11slides.pdf|display}}; notes: {{courses:alg2012:ch11note1.pdf|An NP-Completeness Proof}}]
  * **Final** (**2012/06/18**)

=====References=====
  * [[http://en.wikipedia.org/wiki/Mathematical_induction|Mathematical Induction]] (a Wikipedia page)
  * [[http://dl.acm.org/citation.cfm?id=2093549&CFID=70582427&CFTOKEN=84470362|What is an Algorithm?]] (M.Y. Vardi, Communications of the ACM, Volume 55 Issue 3, March 2012)
  * MIT OpenCourseWare: [[http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-spring-2008/|Introduction to Algorithms]]
  * Stanford Coursera: [[https://www.coursera.org/algo/auth/welcome|Design and Analysis of Algorithms]]
  * [[http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html|Animated Sorting Algorithms]]
  * [[http://www.cs.sunysb.edu/~skiena/combinatorica/animations/|Graph Animations with Combinatorica]]

=====Grading=====
Homework 20%, Participation 10%, Midterm 30%, Final 40%.