2110327 Algorithm Design 2008
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
Syllabus
Important notice
This semester, we have a rule to require participation from
students. Students who have less than 80% attandance of the class
will not be permitted to sit in the examination. 30 minutes late
will be counted as missing the class.
What's new
Other lecture of this class
Somchai
Prasitjutrakul
2110327 course pages
my lecture of year 2007
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. This year special topic is
"String Matching" which contains many algorithmic styles including:
deterministic, probabilistic and approximate. I will try to encourage
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 Counting
Inversion & Matrix Mul (ppt from
Klienberg ch. 5) counting inversions
(my explanation and pseudocode)
Demo
Merge-and-count (ppt from Klienberg), More
examples
Lecture 5 Dynamic programming 1 (Klienberg) (CLR)
Lecture 6 Dynamic programming 2: Sequence
Alignment
week 8 Midterm exam.
Lecture 9 Graphs: (Klienberg
ch3) representation, MST (CLR lecture 16)
shortest paths (CLR lecture 17)
Lecture 10 Graphs: demo
Dijkstra Bellman-Ford
(Klienberg) Shortest paths
All-pairs Shortest path
Lecture 11 Greedy algorithms
Lecture 12 Generating all permutation
Lecture 13 State space search
Lecture 14 NP-Completeness: class P (ppt ), class NP (
ppt ), NP-complete problem & unsolvable ( ppt )
Lecture 15 String matching
Home work
1 Write two programs in your favourite language to perform
sorting:
1.1 Bubble sort
1.2 Merge sort
The input is a set of integers, n = 1,000,000.
Compare their running time if you can profile your running
program. If not, you can insert a counting statement to count the
number that your "barometer" is executed. This excercise gives
you the sense of difference between the running time of O(n^2) and O(n
lg n) algorithms.
2 Look up the information about the negative weight effect
on the shortest path algorithm. I will ask some question about it
in the next class (8 Aug 2008).
3 To know more about combinatorial objects
visit http://www.theory.csc.uvic.ca/~cos
Tools
Som language tools (Som v.3.0) for
sequence alignment
to
know more about Som language visit this page
Last update 15 Aug 2008