Algorithms (演算法)
Teacher Assistant: chrysler@acnlab.csie.ncu.edu.tw (詹謨澤) chiajen@axp1.csie.ncu.edu.tw (張家仁)
Blackborad System: http://bb.ncu.edu.tw (0951演算法B)
Time: Tue. 15:00~17:50
Place: E6 - A208
TA Class: Mon. 12:00~14:00
Downloads:
- JDK 1.5: http://java.sun.com/j2se/1.5.0/download.jsp
- MinGW C++ Compiler (G++): (http://prdownloads.sf.net/mingw/MinGW-3.0.0-1.exe?download)
- Editor for Java/C/C++: Jeep3 (Jeep3Setup.exe)
- Introduction of Algorithms (Alg.ppt)(Al-Khwarizmi-1)(Al-Khwarizmi-2)
(ICPC-homework1, Due: Sept. 25, You can submit your solution to the PC Judge for verifying the correctness.)(Example: ICPC-Scoreboard) - ICPC Examples:
-
10901 Ferry Loading III 10902 Pick-up Sticks 10903 Rock-Paper-Scissors Tournament 10905 Children's Game 10906 Strange Integration 10908 Largest Square 10910 Marks Distribution 10911 Forming Quiz Teams 10912 Simple Minded Hashing 10913 Walking on a Grid 10914 Abundance and Perfect Numbers 10915 War on Weather 10916 Factstone Benchmark 10917 Walk Through the Forest 10918 Tri Tiling 10919 Prerequisites? 10920 Spiral Tap 10921 Find the Telephone 10922 2 the 9s 10923 Seven Seas 10924 Prime Words 10925 Krakovia 10926 How Many Dependencies? 10928 My Dear Neighbours 10929 You can say 11 10930 A-Sequence - Analysis of Algorithms(AnalyzingAlgorithms.ppt)(SortAna.zip)
Homework2: Complete the time complexity of insertion sort algorithm. (Due: Oct. 1)(InsertionSort.ppt)(Solution)
Homework3: Analyze the average case time complexity of the“improved bubble sort.”(Due: Oct. 1)
- The complexity of algorithms and the lower bounds of problems
(Alg02.zip)(SortComparison.ppt)
Homework4: Show that to find the largest number in a list of n numbers requires at least n-1 comparisions.
Homework5: Show that to find the second largest number in a list of n numbers requires at least n-2+/lceil log n/rceil comparisons.
Homework6: Show that binary search is optimal for all searching algorithm performing comparisons only.
(Due: Oct. 15)
ICPC-Homework7: Choose one of the following 8 problems to solve. If you solve more than one problem, you will get bonus in your final score.)(Due: Oct. 15)
1. http://online-judge.uva.es/p/v100/10041.html (Vito's Family)
2. http://online-judge.uva.es/p/v1/120.html (Stacks of Flapjacks)
3. http://online-judge.uva.es/p/v100/10037.html (Bridge)
4. http://online-judge.uva.es/p/v101/10191.html (Longest Nap)
5. http://online-judge.uva.es/p/v100/10026.html (Shoemaker's Problem)
6. http://online-judge.uva.es/p/v101/10138.html (CDVII)
7. http://online-judge.uva.es/p/v101/10152.html (ShellSort)
8. http://online-judge.uva.es/p/v101/10194.html (Football) -
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)
- 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)
Homework8: Exercise 7.5 in Lee's book (additional request: draw a multi-stage graph)
- Quiz1 (2006/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)
We only take the tilling a defective chessboard, the binary search, the merge sort, the 2-D maxima finding, the closest 2D point pair, and the convex hull problems before the midterm exam.
(Tower of Hanoi)(Tower of Hanio Applet)(Voronoi/Delaunay Applet)(Voronoi.ppt)
(Coloured_Voronoi_2D.png)(Delaunay_triangulation.png)(Euclidean minimum spanning tree.png)(FFT.zip)(FourierSeries.ppt)
- Midterm Examination
(including all the materials listed above) (2006/11/14)
- The theory of NP-Completeness
(NPC.zip)
(NPC2.zip)(Special Sets in Graphs)(Recipe, cook and carp.zip)(Turing Machine.zip)
Homework9: Exercise 8.1 in Lee's book (additional request: you should show the supports for your answers) (Due: Nov. 26)
(NPC-3.ppt)
Homework10: Show that 2SAT is a P problem. (Due: Dec. 3) - There is no class on Dec. 5 since I have to chair a session
for ICS'06.
- The prune-and-search strategy:
=This strategy consists of several iterations. At each iteration, it prunes away a fraction, say f, of input data, 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.
(BinarySearch.ppt)(Selection.ppt)(PruneAndSearch.zip)(ConvexHull.zip)
Homework 11: Depict the worse case of prune-and-search convex hull algorithm (quick hull algorithm) for 10 points. Show that the worst case time complexity is O(n2) for given n points. (Due: Dec. 17)
- 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)
Homework12: Use BFS, DFS, Hill-Climbing and Best-First Search schemes to solve the multi-stage problem in the sildes TreeSearch.ppt. (The evaluation function is defined to be the cost from source V0 to the current node.) (Due: Dec. 24) (Note: You should draw the search tree.)
Exercise: 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)
Initial State:
Goal State:2
3184765
1238
47
65
Homework13: Use the A* algorithm to solve the multi-stage graph shortest path problem on page 216. (Due: Jan. 7) (Note: You should draw the search tree.)
Bonus programming: Write a program to implement the A* algorithm to solve the multi-stage graph shortest path problem on page 216. You should hand in a hard copy to TA and an eletronic copy via email of TA (chrysler@acnlab.csie.ncu.edu.tw 詹謨澤, Room 306-1). (Due: Jan. 16 noon)(Up to 5% bonus)
- Approximation algorithms (TSP-ApproximationAlgorithms.ppt)
(ApproximationAlgorithms.zip)
(Andrew's
Monotone Chain Convex Hull Algorithm.ppt) (The
Convex Hull of a 2D Point Set or Polygon) (VertexCover.ppt)
- Final Examination (including all materials above taught after Midterm Exam.)(Date: Jan. 9 15:00-17:30)
Books:
- 中文Java程式設計 (第三版) SIM-908A , 江振瑞 著, 儒林出版社, 2006.
- 物件導向資料結構 — 使用Java語言, 江振瑞 著, 松崗圖書公司, 2005.
- Introduction to the Design and Analysis of Algorithms -- A strategic approach, 2E, R.C.T. Lee et. al., NcGraw Hill, 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.
- 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
