Algorithms (演算法)
Teacher Assistant：cathie@axp1.csie.ncu.edu.tw (胡為凱)
TA Page: http://acnlab.csie.ncu.edu.tw/course/alg/
Time: Tue. 15:00~17:50
Place: E6-A208
TA Class: Wed. night
Downloads:
- MinGW C++ Compiler (G++): (http://prdownloads.sf.net/mingw/MinGW-3.0.0-1.exe?download)
- Editor for Java/C/C++: Jeep3 (Jeep3Setup.exe) (Alas! This software needs JDK 1.4.1 or earlier versions. Jeep4 is coming soon. Please be patient.)
- Programs-1 (詹宜智)
- Programs-2 (周建男)
- Programs-3 (粘存賢)
- Introduction of Algorithms (Al-Khwarizmi-1)(Al-Khwarizmi-2)(AlgIntro.zip)
- From Algorithms to Programs (programs)
(ICPC-homework1, Due: Oct. 11 noon, You must submit your solution to the PC Judge. You should register your accout by your student ID by Sep. 18 noon for the PC Judge classroom named Alg2005.)
(Homework1, Due: Oct. 3 noon)
- The complexity of algorithms and the lower bounds of problems
(SortAna.zip)(Alg02.zip)
(Homework2: Analyze the average case time complexity of the“improved bubble sort”Due: Oct. 3 noon)
(ICPC-Homework2(PC Judge ID: 110401), Due: Nov. 4 noon)
-
The greedy method:
A greedy algorithm builds a solution to a problem in steps. At each step, it adds a part of the solution. Which part of the solution to add next is determined by a greed rule. The rule is "greedy" in the sense that among all of the parts of solution that might be choosen, the best available is selected.
(Greedy.zip)(Greedy2.zip)
(Homework3: Show the correctness of Prim's MST algorithm, Due: Oct. 14 noon)
(Homework4: Show the correctness of Dijkstra's shortest path algorithm, Due: Oct. 17 noon)
- Dynamic programming:
Dynamic programming solves a problem by dividing the problem into subproblems. It then solves all subproblems that might be potentially needed. To avoid solving the same subprolems over and over, once the solution to a subproblem is computed, it is stored in a table (array). When a solution to a subproblem is needed, instead of recomputing the solution, the algorithm obtains it from the table. A dynamic-programming algorithm computes the simplest subproblems first and then works its way up to the original problem. (DynamicP.zip)(DynamicP2.zip)
Homework5: Exercise 7.1 in Lee's book (Hand in a hard copy just before the class on Oct. 25th.)
For TA class discussion (Nov. 2): The RNA Maximum Base Pair Matching Problem (pp. 270~282)
(ICPC-Homework3(PC Judge ID: 111105), Due: Nov. 28 midnight)
- Quiz1 (2005/10/19)
- The divide-and-conquer strategy:
If the problem is small, it is solved directly. If the problem is large, it is divided into two or more parts called subproblems. Each subproblem is then solved (conquered) in the same manner. Afterwards, the solutions to the subproblems are combined (merged) into a solution to the original problem.(Divide-Conquer.zip)(Divide-Conquer2.zip)(Divide-Conquer3.zip)
(Voronoi/Delaunay Applet)(Voronoi.ppt)(FFT.zip)
(Coloured_Voronoi_2D.png)(Delaunay_triangulation.png)(Euclidean minimum spanning tree.png)
- Midterm Examination
(including all the materials listed above) (QuestionSheeAndAnswer)
(Nov. 8, 15:00~17:50, Close-Book)
- The theory of NP-Completeness
(NPC.zip)
(NPC2.zip)(Special Sets in Graphs)(Recipe, cook and carp.zip)(Turing Machine.zip)
Homework6: Exercise 8.1 and 8.2 in Lee's book (Due: Nov. 21 noon)
- The prune-and-search strategy:
=This strategy consists of several iterations. At each iteration, it prunes away a fraction, say f, of input dataq, and then it invokes the same algorithm recursively to solve the problem for the remaining data. After a certain number of iterations, the size of input data will be so small that the problem can be sloved directly in some constant time.
=Assume that the time complexity of a prune-and-search algorithm is T(n) and the time needed to execute each iteration is O(nk) for some constant k. Then T(n)=T((1-f)n)+O(nk). Since 1-f<1, we have T(n)=O(nk) as n-->infinite.
(Selection.ppt)(PruneAndSearch.zip)
Homework 7 (for discussion): What is the main concept of the Prune-nad-Search mechanism? How can we ensure that the time-complexity of the whole prue-and-search process is of the same order as the time-complexity in each iteration?
- The branch-and-bound strategy:
=To find a way to split the solution space (to branch). Then, to predict a lower bound for each class of the solutions. Also find a feasible solution to get an upper bound of the problem. If the lower bound of a solution exceeds the upper bound, this solution cannot be optimal and thus we should terminate the branching associated with this solution.
=A* algorithm: This algorithm can be considered a special type of branch-and-bound algorithm. It employs the best-first search strategy to expand the search tree node of the solution space. The A* algorithm has the following termination rule: If a selected node is also a goal node, then this node represents an optimal solution and the process may be terminated.
(TreeSearch.ppt)(BranchAndBound.ppt)(SpecializedAStar.ppt)
Homework8: Use BFS, DFS, Hill-Climbing and Best-First Search schemes to solve the following 8-puzzle problem with the evaluation function being the number of misplaced tiles. (Note: for an empty cell, please take the left, right, up, down order to expand the search) (Due: Dec. 5 noon)
Initial State:
Goal State:2
3184765
1238
47
65
- Homework9: Write an algorithm to generate the solution tree of a partially ordered list. (Due: Dec. 12 noon)
- Homework10: Exercise
5.4 in Lee's book. (Due: Dec. 19 noon) Bonus: Write a program to generate the
answer automatically. (Due: Jan 17, 2006 to hand in to TA Hu)
- Distributed algorithms (DistributedAlgorithms.zip)
Homework11: Design a distributed algorithm for leader election on rings. The algorithm must be better than that introduced in the class. (Due day: Dec. 26 noon)
- Approximation algorithms (ApproximationAlgorithms.zip)(TheSetCoveringProb.ppt)(Andrew's
Monotone Chain Convex Hull Algorithm.ppt)(Demo
of Andrew's Convex Hull Algorithm)(VertexCover.ppt)
Homework12: Show that GREEDY-SET-COVER algorithm has a ratio bound of ln |X|+1. (Due day: Jan. 2 noon)
- Some Distributed System Examples: (MUREX.ppt)(QuorumSystems.ppt)(QPS-NCU.ppt)(HPS2.ppt)
- Final Examination
(including all materials above taught after Midterm Exam.)
(Jan. 10, 15:00~17:50, Close-Book)
Textbooks:
- Introduction to the Design and Analysis of Algorithms -- A strategic approach, R.C.T. Lee et. al., NcGraw Hill
- 物件導向資料結構—使用Java語言, 江振瑞 著, 松崗圖書公司, 2005
- Introduction to Algorithms, Cormen et. al., MIT Press (開發代理)
- Programming Challenges, Steven S. Skiena and Miguel Revilla, Elsevier, 2003.
- The Algorithm Design Manual, Steven S. Skiena, Elsevier.
- 中文Java程式設計, 江振瑞 著, 儒林出版社
- Midterm 35%
- Final 40%
- Homework, Quiz and Inclass 25% (Notice! 10%~15%
for TA)
- The ACM-ICPC International Collegiate Programming Contest Web Site
- The Programming Challenges (PC) judge: http://www.programming-challenges.com
- The Universidad de Valladolid (UVa) judge: http://online-judge.uva.es
