Yih-Kuen Tsay's Wiki @ IM.NTU

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
======Algorithms, Spring 2011======
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=====
  * 04/17: suggested solutions to {{courses:alg2011:hw3s.pdf|HW#3}} and {{courses:alg2011:hw4s.pdf|HW#4}} available.
  * 04/11: slides for Data Structures (A Supplement) available.
  * 03/25: reminder: no class meeting on 3/28.
  * 03/21: suggested solutions to {{courses:alg2011:hw1s.pdf|HW#1}} improved.
  * 03/21: {{courses:alg2011:hw4.pdf|HW#4}} due on 04/07.
  * 03/20: suggested solutions to {{courses:alg2011:hw1s.pdf|HW#1}} and {{courses:alg2011:hw2s.pdf|HW#2}} available.
  * 03/19: slides for Design by Induciton available.
  * 03/14: Slide 23 for Analysis of Algorithms enhanced.
  * 03/14: {{courses:alg2011:hw3.pdf|HW#3}} due on 03/21.
  * 03/13: slides for Analysis of Algorithms and a note on Solving a Recurrence Relation with Generating Functions available.
  * 03/07: {{courses:alg2011:hw2.pdf|HW#2}} due on 03/14.
  * 02/21: Problem 3 (2.19) replaced by Problem 3 (2.14) in HW#1.
  * 02/21: {{courses:alg2011:hw1.pdf|HW#1}} due on 03/07.
  * 02/18: slides for Introduction and Mathematical Induction and a note on Proving a Loop Invariant available.

=====Instructor=====
Yih-Kuen Tsay (蔡益坤), NTU IM Dept., 3366-1189, ''http://im.ntu.edu.tw/~tsay/'', ''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.

=====TA=====
Ming-Hsien Tsai (蔡明憲), 3366-1205, ''Xmhtsai208@gmail.comX'' (between the enclosing pair of X's); \\ 
Jing-Jie Lin (林靖婕), 3366-1205, ''Xgrace6349@gmail.comX'' (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 between 1:20 and 2:10PM.

=====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.// (Note: A TA session will precede a class meeting whose date is marked with an *. There are four TA sessions on 3/21, 4/11, 5/16, and 5/30, making up the missed class meeting on 3/28.)
  *Introduction [M: Ch. 1; C: Ch. 1,2] (.5 week: 2/21a) [{{courses:alg2011:ch1slides.pdf|slides}}]
  *Mathematical Induction [M: Ch. 2; C: Ch. 4] (1.5 weeks: 2/21b, 3/7) [{{courses:alg2011:ch2slides.pdf|slides}};{{courses:alg2011:ch2note1.pdf|note}}]
  *Analysis of Algorithms [M: Ch. 3; C: Ch. 2,3,4] (1 week: 3/14) [{{courses:alg2011:ch3slides.pdf|slides}};{{courses:alg2011:ch3note1.pdf|note}}]
  *Design by Induction [M: Ch. 5] (1.5 weeks: 3/21*, 4/11a*) [{{courses:alg2011:ch5slides.pdf|slides}}]
  *Data Structures: A Supplement [M: Ch. 4; C: Ch. 6,13,21] (.5 week: 4/11b) [{{courses:alg2011:ch4slides.pdf|slides}}]
  * **Midterm** (**2011/04/18**)
  *Searching and Sorting [M: Ch. 6;  C: Ch. 6,7,8,9] (1.5 weeks: 4/25, 5/2a)  [{{courses:alg2011:ch6slides_a.pdf|slides}}]
  *String Processing [M: Ch. 6;  C: Ch. 32] (1.5 weeks: 5/2b, 5/9)  [{{courses:alg2011:ch6slides_b.pdf|slides}}]
  *Graph Algorithms [M: Ch. 7;  C: Ch. 22,23,24,25,26] (2 weeks: 5/16*, 5/23) [slides: {{courses:alg2011:ch7slides_a.pdf|Basic Graph Algorithms}}, {{courses:alg2011:ch7slides_b.pdf|Advanced Graph Algorithms}}]
  *Dynamic Programming [C: Ch.15] (1 week: 5/30*) [{{courses:alg2011:dynamic_prog.pdf|slides}}]
  *NP-Completeness [M: Ch. 11; C: Ch. 34] (1 week: 6/13) [{{courses:alg2011:ch11slides.pdf|slides}};{{courses:alg2011:ch11note1.pdf|note}}]
  * **Final** (**2011/06/20**)

=====Grading=====
Homework 20%, Participation 10%, Midterm 30%, Final 40%.
Yih-Kuen Tsay's Wiki @ IM.NTU

User Tools

Site Tools

Page Tools
