This page is for the general information of the 2110-327 Algorithm Design
List of Algorithms
Here is the list of algorithm covered in the class, along with its implementation, exercise, etc. The exercise is the problem code for the grader
Category | Algo/prob.| C++ | ruby | exercise
---------|------|-----|------|------------
Divide & Conquer | Merge Sort | | http://www.nattee.net/?q=node/2182 |
Divide & Conquer | Quick Sort | | |
Divide & Conquer | Maximum Contiguous Sum
of Subsequece | | |
Divide & Conquer | Closest Pair | | |
Divide & Conquer | Strassen's Algorithm | | |
Dynamic Programming | Fibonacci Number | | |
Dynamic Programming | Binomial Coefficient | | |
Dynamic Programming | Maximum Contiguous Sum
of Subsequece | | |
Dynamic Programming | Longest Common Subsequence | | |
Dynamic Programming | Matrix Chain Multiplication | | |
Dynamic Programming | 01-Knapsack | | |
Greedy | Prim's (MST) | | |
Greedy | Kruskal's (MST) | | |
Greedy | Interval Scheduling | | |
Graph | Depth First Search | | |
Graph | Connected Component | | |
Graph | Linearization | | |
Graph | Breadth First Search | | |
Graph | Dijkstra's (shortest path) | | |
Graph | Bellman & Ford's (shortest path) | | |
Graph | Floyd & Warshall's (shortest path) | | |
Search | Combination | | |
Search | Permutation | | |
Search | N-Queen | | |
Search | 15-Puzzle | | |
Search | Branch & Bound (Knapsack) | | |
Resource
Grader
We adopt automated exercise grading system called "cafe-grader" created by aj. Jittat and aj. Pong from Kasetsart University. The student are encourage to use this system which can be accessed here
The username and password will be the same as the Chulalongkorn email.
There are introduction instruction and Screen Cast for the grader.
Lecture Note, Lab's document, problems,
- Aj. Somchai's video class are one of the best, check it here. It contains tons of e-learning material and the slide. The experimental analysis of algorithm is at http://www.cp.eng.chula.ac.th/~somchai/JLab/jprofile/
- In 2009, we set up some self-learning activities called "Labs". It can be accessed here
- In 2010, there are several homework available in grader system. Check it here
C++
Most student are familiar with Java from their freshy year and hopefully all students should be OK with C, C++ Since 2110-211 (Data Structure) use them extensively. Nevertheless, here are list of C++ resources.
- An Introduction to C Programming for Java Programmers is a good starting point since you all are familiar with JAVA
- Website cprogramming.com has very good tutorials. We suggest reading lesson 1 to lesson 10.
- Array and pointer in C is more complex than that of JAVA, check this one for a good introduction.
- The C Book, another book for C beginners.
- Thinking in C++ by Bruce Eckel, a must-read for most C++ developers. The second edition of the book can be downloaded for free.
- The Stony Brook Algorithm Repository contains a vast selection of algorithm, and multiple implementation in various language, for several problems. If you need a reference code, you can check it here.