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.

Midterm Score

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