# 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