Essential

• The lecture by Aj. Somchai is at http://www.cp.eng.chula.ac.th/~somchai/ULearn/Algorithms/index.htm The slide can be downloaded there as well.
• The syllabus is here
• Facebook group is the same as one used in Data Structure, https://www.facebook.com/groups/611971252174334/
• The grader system can be accessed at https://www.nattee.net/grader

Lecture Logs

(2014-08-13 Wed)

The first lecture. All sections gathered together for one big class. There was a short lecture about 'What is algorithm' and why are we having this class. Syllabus are handed out and we had a small discussion about how the class is supposed to be.

(2014-08-18 Mon)

Our first sectioned lecture. We talked about Stable Marriage Problem: what it is, how we define unstable. First classroom activities is to write an algorithm, in pseudo-code, on checking if a matching is stable. At the end of the class, a drawing-by-instruction exercise was performed to understand that it is non-trivial to be precise, even for a simple thing.

(2014-08-20 Wed)

More on Stable Marriage Problem. Now we are trying to tackle the problem. But for a quick warm-up, a classroom activities is to write an algorithm to check if matching is perfect. This is a simple problem but admits several solution ranging from O(n), O(n log n), \Theta(n), O(n^2). Different data structures are used by the student.

The assignment was to read the analysis part of Aj. Somchai's book, page 24 -- 50.

(2014-08-25 Mon)

Start on analysis of algorithm. The goal of analysis is to be able to predict the behavior of algorithms in term of efficiency. We focus on the rate of growth of the time used with respect to the size of input. We talked about how to analyze the rate of growth. The barometer operation is explained and some example are given. Comparing the rate of growth of two functions are defined using limit to the infinity. Asymptotic notation are also defined.

In this lecture, we saw the use of Mercurial as a distribution of source code and as a version control of homework submission. There are some youtube video about the usage of Mercurial for this class.

1. http://www.youtube.com/watch?v=p4cjVHtXhsc What is HG and how we use it
2. http://www.youtube.com/watch?v=aikHdChtGno Quick example of using HG
3. http://www.youtube.com/watch?v=PMcanq8p7lg A step-by-step in using HG to do the assignment.

In short, the student should fork nattee/algo-class repositories in bitbucket.org and clone it to your harddisk. The recommended gui for HG is TortoiseHG but you can use anything you like. The in class problem are given at tag l4.1 and l4.2.

In class activities is to modify the source code for sum of two element in arrays problem. The problem is to decide whether there are two elements, one from different array, such that their sum equal to a specific value. The student have to 1) modify the program to count the barometer operation and 2) modify the output to let the algorithm takes specific step.

(2014-08-27 Wed)

More on analysis. We summarized the method to analysis the algorithm. More definition of the asymptotic notation are given. Quick analysis of several type of basic program flows are given with some examples. The flows are sequential, conditional, iterative, and recursive. The recursive flow will be discussed in the next week. We also saw example of two algorithms: Insertion sort and binary search.

In class activity is to solve the problem of sum4, an extension of sum of two elements: Given four array A[], B[], C[], D[], we have to decide whether there exists A[i] + B[j] + C[k] + D[l] that equals to X. The solution are given as tag l5 in the nattee/algo-class. The detail is shown in the video at http://www.youtube.com/watch?v=V9WDwFG5DW0 .

The homework of this week are as follows.

1. Design an algorithm that solve the sum4 problem.
2. Analyze the example solution given in bitbucket.

The answer must be written on a paper and must be submitted to the box at Room 17-14, Eng 4 Building before noon of Friday 29 Aug.

(2014-09-01 Mon)

Introduction to Divide and Conquer. Few example of divide and conquer, Binary Search, a^k mod m. We touched a little of RSA encryption.

In class activities is to solve the problem of finding a repeating value in the array of size [n+1] containing only a value of 1..n.

(2014-09-01 Wed)

More on D&C: Multiplying of large numbers, Strassen. A brief example of solving a recurrent relation by a recursion tree.

In class exercise is to write a pseudo code of insertion sort using divide-and-conquer approach.

Grader is operational at https://www.nattee.net/grader

(2014-09-08 Mon)

More on analysis of algorithm, especially in recursive algorithm, recursion tree, and how to solve recurrent relation. Master's Method is discussed. Additional D&C algorithms, merge sort and quick sort are presented. A brief overview of Maximum Contiguous Sum of Subsequence are also explained.

EX01 exercise in grader is available.

(2014-09-10 Wed)

Final class of D&C. We talked about MCS, QuickSelect using mm5. Celebrity problem.

The students are instructed to watch the video lecture of aj. somchai on the problem of min-max and the closest pair.

(2014-09-15 Mon)

Start working on Dynamic Programming. Definition of what is Dynamic Programming, Memoization, top-down, bottom-up. Two representative problems are discussed, Fibonacci and C(n,k). We also talk about "quick sum" technique for both linear array and 2D arrays. Let A[][] be a 2D array, S[i][j] is summation of A[1..i][1..j]. With S, we can calculate the summation from A[bottom..top][left..right] in O(1). The calculation of S itself is also can be done in O(nm) where n,m is the row,col count of the array.

In class exercise is to write an algorithm using quick sum. Also there are homework to write a bottom up version of Quick Sum table.

(2014-09-17 Wed)

QUIZ!!!!

(2014-09-22 Mon)

More on Dynamic Programming. We mostly talked about Longest Common Subsequence Problem and a brief discussion on the Number Triangle problem.

In class exercise is to write a top-down version of the LCS problem using the given recurrent. The students are instructed to watch the matrix chain multiplication problem before Wednesday class.

(2014-09-24 Wed)

Dynamic Programming: Matrix Chain Multiplication.

(2014-10-01 Mon) && (2014-10-03 Wed)

-- MIDTERM WEEK; NO CLASS --

(2014-10-06 Mon)

We have our midterm today.

(2014-10-08 Wed)

Greedy: Activity Selection and Fractional Knapsack. In class exercise: find example of knapsack where greedy is not working in the case of 01-Knapsack. Finding an example with minimal number of items against various greedy strategy.

(2014-10-13 Mon)

Greedy: More on Fractional Knapsack and Huffman Coding.

(2014-10-15 Wed)

Graph: Graph basic and data structure for graphs. Intro to DFS and BFS.

(2014-10-20 Mon)

Graph: More on DFS and BFS, Connected Component on an undirected graph. In class exercise: Identifying push order, pop order of DFS and BFS, Identifying best order that minimize memory.

(2014-10-22 Wed)

Graph: Topological Sorting, Strongly Connected Component.

(2014-10-27 Monday)

Problem Session: In class exercises are "Detecting a cycle in an undirected Graph" and "Finding largest cycle in a directed graph". We also provide a brief introduction to a minimal spanning tree: Prim's and Kruskal's algorithms.