2110327 Algorithm  Design 2007

Prabhas Chongstitvatana
office   Eng. Building 4,  Floor 18  Room 13,  tel: 02-2186982,    email me
Lecture hour  Wed, Fri  8:30am - 10pm , Eng Building 3, room 418
Teaching assistance is Putita, her office hour and email will be announced shortly

What's new

15 June 2007     There will be a quiz on Wed 20 June, 9:15-9:45am in the class.  Topics: growth of function and solving recurrences. Score 3%.
20 June 2007      The class on Friday 22 June is cancelled due to my appointment to see the medical operation.
27 June 2007     There will be a quiz on Fri 29 June, 8:30-9:00am in the class. Topics: growth of function and solving recurrences. Score 3%.  (we take the best of two quizes).

Other lecture of this class

Somchai Prasitjutrakul     2110327  course pages

my lecture of year    2006   2005   2004  2002   2001   2000 (only part 2)

Scope of this year lecture:

The first half is devoted to "easy" (P) problem, another half is "hard" (NP) problems and other interesting topics such as randomised and approximate algorithm..  I will concentrate on basic and the "design" aspect.  I prefer our students to have practical skill, ie. that they can "write" and "execute" the algorithms that they design in some language and test them.

Lecture 1   An overview of algorithmics    Intro to algorithms
Lecture 2   Asymptotic notation    Recurrence
Lecture 3    Analysis of Algorithms  (slides 4 up)    hand written slides examples of analysis   (they are from CD)
Lecture 4   Divide and Conquer   (pdf from MIT-Open Course Ware)   
                 Counting Inversion & Matrix Mul (ppt from Klienberg ch. 5)  counting inversions (my explanation and pseudocode)
Lecture 5   Demo Merge-and-count  (ppt from Klienberg)     Dynamic programming    Demo interval scheduling (Klienberg)
Lecture  6   Dynamic programming  (Klienberg)   (CLR) 
Lecture 7    Dynamic programming:  Sequence Alignment
Lecture  8    Graph algorithms
Lecture  9    Minimum spaning tree     Shortest path
Lecture 10   Max Flow     (Somchai p. slide)  (Kleinberg slide )  (Residual graph demo)

Home work

week 3       Please read about Stirling approximation (of n!)
week 4       Read counting inversion
week  5      Pretty print  (typesetting) problem 8-1,  and Scheduling problem 8-2 (dynamic programming)

Tools

Som compiler and language  currently version 3.0
Sequence alignment source and som-compiler executable

Last update  15 August 2007