Algorithms, Spring 2015
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/14: grade report available; please send inquiries, if any, to the instructor by 2PM 07/16.
-
06/18: the
old_exam zip file updated to include the Final of 2014.
06/08: notes/slides for NP-Completeness and an appendix available.
06/02:
HW#10 due on 06/16.
06/01: notes/slides for Dynamic Programming and Reduction available.
05/26:
HW#9 due on 06/02.
05/26: notes/slides for Advanced Graph Algorithms available.
-
05/12:
HW#8 due on 05/19.
05/05:
HW#7 due on 05/12.
05/05: TA session of 5/26 moved one week earlier to 5/19.
05/05: notes/slides for Basic Graph Algorithms available.
04/28: notes/slides for String Processing available.
-
-
04/06:
HW#6 due on 04/21.
03/31:
HW#5 due on 04/14.
03/30: notes/slides for Searching and Sorting available.
03/23:
HW#4 due on 03/31.
03/23: notes/slides for A Supplement to Data Structures available.
03/16:
HW#3 due on 03/24.
03/16: notes/slides for Design by Induction available.
03/10:
HW#2 due on 03/17.
03/10: notes/slides for Analysis of Algorithms and an appendix on Solving a Recurrence Relation with Generating Functions available.
03/02:
HW#1 due on 03/10.
03/02: a note on Proving a Loop Invariant available.
02/24: notes/slides for Introduction and for Mathematical Induction available.
02/24: this website announced.
Instructor
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-1205, Xr03725007@ntu.edu.twX (between the enclosing pair of X's).
唐維佋, 3366-1205, Xpa4373@gmail.comX (between the enclosing pair of X's).
Textbooks
[M]
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, eight copies are available for loan; please contact one of the TAs.)
[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/24, 4/14,
5/19, and 6/9.)
Introduction [M: Ch. 1; C: Ch. 1,2] (.5 week: 2/24a) [
notes,
slides]
-
-
Design by Induction [M: Ch. 5] (1.5 weeks: 3/17, 3/24a*) [
notes,
slides]
Data Structures: A Supplement [M: Ch. 4; C: Ch. 6,13,21] (.5 week: 3/24b) [
notes,
slides]
Searching and Sorting [M: Ch. 6; C: Ch. 6,7,8,9] (3 weeks: 3/31, 4/7, 4/14*) [
notes,
slides]
Midterm (2015/04/21)
String Processing [M: Ch. 6; C: Ch. 32] (1 week: 4/28) [
notes,
slides]
Graph Algorithms: Basic [M: Ch. 7; C: Ch. 22,23,24,25,26] (3 weeks: 5/5, 5/12, 5/19*) [
notes,
slides]
Graph Algorithms: Advanced [M: Ch. 7; C: Ch. 22,23,24,25,26] (1 week: 5/26) [
notes,
slides]
Dynamic Programming [C: Ch.15] (.5 week: 6/2a) [
notes,
slides]
Reduction [M: Ch. 10; C: Ch. 29] (.5 week: 6/2b) [
notes,
slides]
-
Final (2015/06/23)
References
-
-
-
-
-
-
The website of
ACM-ICPC (International Collegiate Programming Contest)
Grading
Homework 20%, Participation 10%, Midterm 35%, Final 35%.