Slides

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

Lecture Log

• (2013-06-03) Introduction, Stable Marriage Problem.

• (2013-06-05) Special Lecture from Dr. Damrong Guoy.

• (2013-06-10) Finished the Stable Marriage Problem. We talked about Pseudo-code. We will use Pseudo-code as a medium for communication. Covered the main slide pp. 25--31. 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.

• (2013-06-12) 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)

for i = 1..n // O(N^2)
for j = 1..n need = x - (c[i] + d[j]) if h.contain?(x) return "YES" return "NO" [/collapsed]

• (2013-06-17) Revisit the asymptotic notation (O,\Theta,\Omega, etc.) Covered the main slide pp. 79--97.

• (2013-06-19) We finished the Analysis of Algo with the Master Method. We covered the main slide pp. 76--78 and 98--109. Classroom exercise is to analyze this

• (2013-06-24) 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 pseudo-code of the solutions are as follow [collapsed title="O(N^3) iterative-approach"] //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) iterative-approach with quick-sum"] //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[i-1] + d[i]

return sum [/collapsed]

[collapsed title="O(N^2) divide-and-conquer approach with quick-sum"] //input: d[1..n] //output: the maximum contiguous sum of subsequence

[collapsed title="O(N lg N) divide-and-conquer approach "] //input: d[1..n] //output: the maximum contiguous sum of subsequence

• (2013-06-26) We had a quiz for 30 minutes on Analysis. Merge Sort are covered. See this page for the code of Merge Sort.

• (2013-07-01) Quick sort. x^m mod k, Closest pair, Strassen

• (2013-07-03) The rest of sorting, shell sort.

• (2013-07-08 and 2013-07-10) Class skipped, I went to www.IOI2013.org

• (2013-07-15) Introduction to Dynamic Programming, Memoization. Fibonacci, C(n,r)

• (2013-07-17) 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, 01-Knapsack, Matrix Chain Multiplication. In-class exercise is lots of memoization of the said algorithm.

• (2013-07-31) Class skipped. Sorry guys.

• (2013-08-05) After a loooong break and midterm, we met at last. Introduction to graph algorithm. BFS. In class exercise is find a "friend-of-friend" and "freind-of-freind-of-friend....".

• (2013-08-07) Finished the BFS and talked about DFS. There is a homework to modify DFS to detect a cycle in a graph.

• (2013-08-14) Topological Sorting, Strongly Connected Component.

• (2013-08-19) Prim's and Kruskal's. Disjoint Set. In-class exercise is to write Prim's before seeing the actual implementation.

• (2013-08-21) Cut Property. Greedy Algorithm. Activity Selection.

• (2013-08-26) Shortest Path. Dijkstra's Algorithm

• (2013-08-28) More on Dijkstra's Algorithm. Negative weight edge, Bellman-Ford

• (2013-09-02) Bellman-Ford, Floyd-Warshall

• (2013-09-04) State Space Search. Basic Combinatorial problem. Sum-of-subset problem.

[collapsed title="Choose R items from N items "] //input: N,R //output: array x[1..N] where x[i] == 1 means the i-th items are selected.

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]

• (2013-09-09) N-Queen, Permutation, BFS and DFS. In-class exercise is to write n-queen.

[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(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]