User Tools

Site Tools


courses:alg2009:home

Algorithms, Spring 2009

This course is an introduction to the design and analysis of computer algorithms. Its goal 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. A particular emphasis will be given to principles of mathematical induction and their use in designing algorithms.

Announcements

Instructor

Yih-Kuen Tsay (蔡益坤), NTU IM Dept., 3366-1189, Xtsay@im.ntu.edu.twX (between the enclosing pair of X's).

Lectures

Thursday 2:20~5:20PM, Room 201, Management II.

Office Hours

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

Textbooks

Introduction to Algorithms - A Creative Approach, U. Manber, Addison-Wesley, 1989.
Introduction to Algorithms, Second Edition, T.H. Cormen, C.E. Leiserson, and R.L. Rivest, MIT Press, 2001.

The course will cover most of Manber's book plus supplementary mate- rial, including a few chapters of the book by Cormen et al.:

  • Introduction - Chapter 1 (.5 week: 2/19a) [slides]
  • Mathematical Induction - Chapter 2 (1.5 weeks: 2/19b, 2/26) [slides;note]
  • Analysis of Algorithms - Chapter 3 (1 week: 3/5) [slides;note]
  • Design by Induction - Chapter 5 (2 weeks: 3/12, 3/19) [slides]
  • Data Structures: A Supplement - Sections 4.3.2,4.3.4,4.4,4.5 (1 week: 3/26) [slides]
  • Sorting, Searching, and String Processing - Chapter 6 (2 weeks: 4/9, 4/23) [slides]
  • Graph Algorithms - Chapter 7 (2 weeks: 4/30, 5/7) [slides]
  • Selected Topics: Dynamic Programming, Mergeable Heaps, and Linear Programming - Chapters 15, 19, 20, and 29 of Cormen et al. (2 weeks: 5/14, 5/21) [Dynamic Programming]
  • NP-Completeness - Chapter 11 (2 weeks: 6/4, 6/11) [slides;note]

Grading

Homework 20%, Participation 10%, Midterm (4/16) 35%, Final (6/18) 35%.

TA

Yi-Wen Chang (常怡文), 3366-1205, Xr97725004@ntu.edu.twX (between the enclosing pair of X's);
Chih-Pin Tai (戴智斌), 3366-1205, Xsteve750312@gmail.comX (between the enclosing pair of X's).
TA sessions will be scheduled prior to some of the class meetings (tentatively on 3/19, 4/9, 5/14, and 6/4), between 1:20 and 2:10PM.

courses/alg2009/home.txt · Last modified: 2022/12/09 11:04 by tsay2