======Algorithms, Spring 2014======
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=====
  * 06/30: grade report revised.
  * 06/28: grade report available; please send inquiries, if any, to the instructor by 2PM 06/30.
  * 06/03: notes/slides for NP-Completeness and an appendix available.
  * 05/28: {{courses:alg2014:hw10.pdf|HW#10}} due on 06/10.
  * 05/27: notes/slides for Dynamic Programming and Reduction available.
  * 05/20: {{courses:alg2014:hw9.pdf|HW#9}} due on 06/03.
  * 05/20: notes/slides for Advanced Graph Algorithms available. 
  * 05/13: {{courses:alg2014:hw8.pdf|HW#8}} due on 05/20.
  * 05/06: (incomplete) {{courses:alg2014:alg2014mid_s.pdf|Suggested Solutions to Midterm Problems}} available.
  * 04/29: notes/slides for Basic Graph Algorithms available. 
  * 04/22: {{courses:alg2014:hw7.pdf|HW#7}} due on 04/29.
  * 04/22: notes/slides for String Processing available. 
  * 04/08: slides from TA sessions: {{courses:alg2014:hw1slides.pptx|HW#1}}, {{courses:alg2014:hw2slides.pptx|HW#2}},  {{courses:alg2014:hw3slides.pptx|HW#3}},  {{courses:alg2014:hw4slides.pptx|HW#4}}.
  * 04/08: {{courses:alg:old_exams.zip|old exams}}.
  * 04/08: {{courses:alg2014:hw6.pdf|HW#6}} due on 04/15.
  * 04/08: {{courses:alg2014:hw5.pdf|HW#5}} (Programming Exercise #1) due on 04/22.
  * 04/01: notes/slides for A Supplement to Data Structures and for Searching and Sorting available. 
  * 03/18: {{courses:alg2014:hw4.pdf|HW#4}} due on 04/01.
  * 03/11: {{courses:alg2014:hw3.pdf|HW#3}} due on 03/21.
  * 03/10: due date of HW#2 postponed till 3/14.
  * 03/10: notes/slides for Design by Induction available. 
  * 03/04: notes/slides for Analysis of Algorithms and an appendix on Solving a Recurrence Relation with Generating Functions available.
  * 03/03: {{courses:alg2014:hw2.pdf|HW#2}} due on 03/11.
  * 02/25: {{courses:alg2014:hw1.pdf|HW#1}} due on 03/04.
  * 02/18: notes/slides for Introduction and Mathematical Induction and an appendix on Proving a Loop Invariant available. 
  * 02/17: this website created.
=====Instructor=====
[[http://im.ntu.edu.tw/~tsay/|Yih-Kuen Tsay (蔡益坤)]], NTU IM Dept.,
3366-1189, ''Xtsay@ntu.edu.twX'' (between the enclosing pair of X's).

=====Lectures=====
Tuesday 2:20~5:20PM, Room 205, Management Building 2. \\ TA
sessions will be scheduled prior to some of the class meetings between 1:20
and 2:10PM; see the course schedule below.

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

=====TAs=====
施舜元, 3366-1209, ''Xr02725014@ntu.edu.twX'' (between the enclosing pair of X's). \\
李孟, 3366-1209, ''Xr02725032@ntu.edu.twX'' (between the enclosing pair of X's). 

=====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. (Four copies of this book have been put on reserve at NTU Library in the B1-教師指定參考書區 under 演算法(BM-4). Additionally, ten copies are available for loan; please contact one of the TAs.)
  * [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. (開發圖書代理; one copy of this book has been put on reserve at NTU Library in the B1-教師指定參考書區 under (FF-9).)

=====Syllabus/Schedule (with links to notes/slides)=====
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/18, 4/8,
5/20, and 6/3, making up the missed class meeting on 3/25.)
  *Introduction [M: Ch. 1; C: Ch. 1,2] (.5 week: 2/18a) [{{courses:alg2014:ch1_notes.pdf|notes}}, {{courses:alg2014:ch1_slides.pdf|slides}}]
  *Mathematical Induction [M: Ch. 2; C: Ch. 4] (1.5 weeks: 2/18b, 2/25) [{{courses:alg2014:ch2_notes.pdf|notes}}, {{courses:alg2014:ch2_slides.pdf|slides}}, {{courses:alg2014:ch2_appendix.pdf|Proving a Loop Invariant}}]
  *Analysis of Algorithms [M: Ch. 3; C: Ch. 2,3,4] (1 week: 3/4) [{{courses:alg2014:ch3_notes.pdf|notes}}, {{courses:alg2014:ch3_slides.pdf|slides}}, {{courses:alg2014:ch3_appendix.pdf|Solving a Recurrence Relation with Generating Functions}}]
  *Design by Induction [M: Ch. 5] (1 week: 3/11) [{{courses:alg2014:ch5_notes.pdf|notes}}, {{courses:alg2014:ch5_slides.pdf|slides}}]
  *Data Structures: A Supplement [M: Ch. 4; C: Ch. 6,13,21] (.5 week: 3/18a*) [{{courses:alg2014:ch4_notes.pdf|notes}}, {{courses:alg2014:ch4_slides.pdf|slides}}]
  *Searching and Sorting [M: Ch. 6;  C: Ch. 6,7,8,9] (2.5 weeks: 3/18b, 4/1, 4/8*) [{{courses:alg2014:ch6_notes_a.pdf|notes}}, {{courses:alg2014:ch6_slides_a.pdf|slides}}]
  * **Midterm** (**2014/04/15**)
  *String Processing [M: Ch. 6;  C: Ch. 32] (1 week: 4/22) [{{courses:alg2014:ch6_notes_b.pdf|notes}}, {{courses:alg2014:ch6_slides_b.pdf|slides}}]
  *Graph Algorithms: Basic [M: Ch. 7;  C: Ch. 22,23,24,25,26] (3 weeks: 4/29, 5/6, 5/13) [{{courses:alg2014:ch7_notes_a.pdf|notes}}, {{courses:alg2014:ch7_slides_a.pdf|slides}}]
  *Graph Algorithms: Advanced [M: Ch. 7;  C: Ch. 22,23,24,25,26] (1 week: 5/20*) [{{courses:alg2014:ch7_notes_b.pdf|notes}}, {{courses:alg2014:ch7_slides_b.pdf|slides}}]
  *Dynamic Programming [C: Ch.15] (.5 week: 5/27a) [{{courses:alg2014:dynamic_prog_notes.pdf|notes}}, {{courses:alg2014:dynamic_prog_slides.pdf|slides}}]
  *Reduction [M: Ch. 10; C: Ch. 29] (.5 week: 5/27b) [{{courses:alg2014:ch10_notes.pdf|notes}}, {{courses:alg2014:ch10_slides.pdf|slides}}]
  *NP-Completeness [M: Ch. 11; C: Ch. 34] (2 weeks: 6/3*, 6/10) [{{courses:alg2014:ch11_notes.pdf|notes}}, {{courses:alg2014:ch11_slides.pdf|slides}}, {{courses:alg2014:ch11_appendix.pdf|An NP-Completeness Proof}}]
  * **Final** (**2014/06/17**)

=====References=====
  * [[http://en.wikipedia.org/wiki/Mathematical_induction|Mathematical Induction]] (a Wikipedia page)
  * 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://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)
  * [[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]]
  * The website of [[http://icpc.baylor.edu/welcome.icpc|ACM-ICPC]] (International Collegiate Programming Contest)

=====Grading=====
Homework 20%, Participation 10%, Midterm 35%, Final 35%.