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