Slides
We use http://www.cp.eng.chula.ac.th/~somchai/ULearn/Algorithms/Topics/pdf/ALGOALL.pdf as our main slide but I will also use some other slides from previous years as well.
Lecture Log

(20130603) Introduction, Stable Marriage Problem.

(20130605) Special Lecture from Dr. Damrong Guoy.

(20130610) Finished the Stable Marriage Problem. We talked about Pseudocode. We will use Pseudocode as a medium for communication. Covered the main slide pp. 2531. The classroom Exercise was to solve the following problem.
"Sum of Four Elements Problem" Input: four arrays of integers, each of size N. a[1..n],b[1..n],c[1..n],d[1..n] and a number X. Output: Either "Yes" or "No". It will be "Yes" if and only if there exists a[i]+b[j]+c[k]+d[l] == x.

(20130612) Showed the solution of the above problem in O(N^2), using hash or O(N^2 lg N) using binary search or AVL Tree. Intro to Analysis. What is the goal of analysis? Why we measure the growth of the function instead of the actual time. We can measure by either experiment (write a program and count the number of executed basic command), or by analysis (derive a function that describes the number of executed command and analyze the function). Done a classroom exercise. Cover the main slide pp. 63  75
The solution of the Sum of Four Elements is as follow
[collapsed title="O(N^2) using hash table"]
//input: a[1..n],b[1..n],c[1..n],d[1..n], x
//output: YES iff there exist i,j,k,l such that a[i]+b[j]+c[k]+d[l] == x
int FourElements(a[1..n],b[1..n],c[1..n],d[1..n], x)
Hash h = new Hash()
for i = 1..n // O(N^2)
for j = 1..n
h.add(a[i]+b[j])
for i = 1..n // O(N^2)
[/collapsed]
for j = 1..n
need = x  (c[i] + d[j])
if h.contain?(x)
return "YES"
return "NO"

(20130617) Revisit the asymptotic notation (O,\Theta,\Omega, etc.) Covered the main slide pp. 7997.

(20130619) We finished the Analysis of Algo with the Master Method. We covered the main slide pp. 7678 and 98109. Classroom exercise is to analyze this

(20130624) Introduction to Divide and Conquer (D&C). Examples are a binary search and a sequential search, both in recursive mode. We talked about Maximum Contiguous Sum of Subsequence. Classroom exercise is to write N^3 or N^2 of the MCS and to analyze another solution. We covered the slide from 2010
The pseudocode of the solutions are as follow
[collapsed title="O(N^3) iterativeapproach"]
//input: d[1..n]
//output: the maximum contiguous sum of subsequence
int MCS(d[1..n])
max = d[1]
for i = 1..n
for j = i..n
sum = 0
for k = i..j
sum = sum + d[i]
if sum > max
max = sum
return sum
[/collapsed]
[collapsed title="O(N^2) iterativeapproach with quicksum"]
//input: d[1..n]
//output: the maximum contiguous sum of subsequence
int MCS(d[1..n])
//compute prefix sum
prefix[0] = 0
for i = 1..n
prefix[i] = prefix[i1] + d[i]
max = d[1]
for i = 1..n
for j = i..n
sum = prefix[j]  prefix[i1]
if sum > max
max = sum
return sum
[/collapsed]
[collapsed title="O(N^2) divideandconquer approach with quicksum"]
//input: d[1..n]
//output: the maximum contiguous sum of subsequence
int MCS(d[1..n])
MCS_DC(d,1,n)
int MCS(d[1..n],left,right)
if (left >= right) return d[right]
mid = (left+right) / 2
//recursive call (divide step)
leftSubProblem = MCS_DC(d,left,mid)
rightSubProblem = MCS_DC(d,mid+1,right)
//conquer step
//compute prefix sum
prefix[left1] = 0
for i = left..right
prefix[i] = prefix[i1] + d[i]
maxCenter = d[mid] + d[mid+1]
for i = left..mid
for j = (mid+1)..right
sum = prefix[j]  prefix[i1]
if sum > maxCenter
maxCenter = sum
return max(maxCenter , max( leftSubProblem,rightSubProblem ) )
[/collapsed]
[collapsed title="O(N lg N) divideandconquer approach "]
//input: d[1..n]
//output: the maximum contiguous sum of subsequence
int MCS(d[1..n])
MCS_DC(d,1,n)
int MCS(d[1..n],left,right)
if (left >= right) return d[right]
mid = (left+right) / 2
//recursive call (divide step)
leftSubProblem = MCS_DC(d,left,mid)
rightSubProblem = MCS_DC(d,mid+1,right)
//conquer step
// left side
leftSum = d[mid]
maxLeft = leftSum
for i = (mid1)..left (step 1)
leftSum = leftSum + d[i]
if (leftSum > maxLeft) maxLeft = leftSum
// right side
rightSum = d[mid+1]
maxRight = rightSum
for i = (mid+2)..right
rightSum = rightSum + d[i]
if (rightSum > maxRight) maxRight = rightSum
maxCenter = maxLeft + maxRight
return max(maxCenter , max( leftSubProblem,rightSubProblem ) )
[/collapsed]

(20130626) We had a quiz for 30 minutes on Analysis. Merge Sort are covered. See this page for the code of Merge Sort.

(20130701) Quick sort. x^m mod k, Closest pair, Strassen

(20130703) The rest of sorting, shell sort.

(20130708 and 20130710) Class skipped, I went to www.IOI2013.org

(20130715) Introduction to Dynamic Programming, Memoization. Fibonacci, C(n,r)

(20130717) SUPER MAKE UP CLASS!!! We start at 8.00 until 12.00. at 9.00, we also had a quiz. We talked about dynamic programming. Longest Common Subsequence, 01Knapsack, Matrix Chain Multiplication. Inclass exercise is lots of memoization of the said algorithm.

(20130731) Class skipped. Sorry guys.

(20130805) After a loooong break and midterm, we met at last. Introduction to graph algorithm. BFS. In class exercise is find a "friendoffriend" and "freindoffreindoffriend....".

(20130807) Finished the BFS and talked about DFS. There is a homework to modify DFS to detect a cycle in a graph.

(20130814) Topological Sorting, Strongly Connected Component.

(20130819) Prim's and Kruskal's. Disjoint Set. Inclass exercise is to write Prim's before seeing the actual implementation.

(20130821) Cut Property. Greedy Algorithm. Activity Selection.

(20130826) Shortest Path. Dijkstra's Algorithm

(20130828) More on Dijkstra's Algorithm. Negative weight edge, BellmanFord

(20130902) BellmanFord, FloydWarshall

(20130904) State Space Search. Basic Combinatorial problem. Sumofsubset problem.
[collapsed title="Choose R items from N items "]
//input: N,R
//output: array x[1..N] where x[i] == 1 means the ith items are selected.
Choose(N,R) {
X = new array[1..n] of integer
choose(x,N,0,0,R,0,NR)
}
choose(x,n,step,num_one,max_one,num_zero,max_zero) {
if (step == n) {
print(x); // ...or use x to do something...
} else {
if (num_zero < max_zero)
x[step+1] = 0; choose(x,n,step+1, num_one , max_one, num_zero+1, max_zero);
if (num_one < max_one)
x[step+1] = 1; choose(x,n,step+1, num_one+1, max_one, num_zero , max_zero);
[/collapsed]
}
}
 (20130909) NQueen, Permutation, BFS and DFS. Inclass exercise is to write nqueen.
[collapsed title="Permutation R items from N items "]
//input: N,R
//output: array x[1..R] where x contain the permutation (e.g., x = {1,2,3}, x = {1,3,2}, x = {2,1,3}....)
Choose(N,R) {
X = new array[1..n] of integer.
used = new array[1..n] of boolean, initialized with false;
choose(x,n,0,0,r,0,nr)
}
choose(x,used,n,r,step) {
if (step == r) {
print(x); // ...or use x to do something...
} else {
for (int i = 1;i <= n;i++) {
if (used[i] == false) {
used[i] = true;
x[step+1] = i;
permu(x,used,n,step+1);
used[i] = false;
}
}
}
}
[/collapsed]