• JDK: http://java.sun.com/javase/downloads/index.jsp
• MinGW C++ Compiler (G++): (http://prdownloads.sf.net/mingw/MinGW-3.0.0-1.exe?download)
• Editor for Java/C/C++/C#: Jeep4 (Jeep4Setup.exe) 

• 中 文Java程式設計 (第三版) SIM-908A , 江振瑞 著, 儒林出版社, 2006.
• 物 件導向資料結構 — 使用Java語言, 江振瑞 著, 松崗圖書公司, 2005.
• Introduction to the Design and Analysis of Algorithms -- A strategic approach, 2/e, R.C.T. Lee et. al., NcGraw Hill, 2005.
• Algorithms, S. Dasgupta, C. Papadimitriou and U. Vazirani, McGraw Hill, 2008.
  
• 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.

• Introduction to Algorithms (Alg.ppt)(Al-Khwarizmi-1)(Al-Khwarizmi-2)
  Homework1: Choose one of the following 7 problems to solve. You should submit your solution to the PC Judge or UVA Judge for verifying the correctness. Due: Oct. 8 12:00PM (Midnight)
  
• ACM-ICPC (ppt)
• The Universidad de Valladolid (UVa) judge: http://online-judge.uva.es
  
• Example: http://online-judge.uva.es/p/v100/10041.html (Vito's Family) (Vito.java) (Vito2.java) (Vito.cpp)

   1.    http://online-judge.uva.es/p/v101/10194.html (Football)
   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)  

• Analysis of Algorithms (the complexity of algorithms) (AnalyzingAlgorithms.ppt)(SortAna.zip)
  Homework2: Analyze the average case time complexity of the“improved bubble sort.”(Due: 24:00, Oct. 14)
  
• The lower bounds of problems
  (Alg02.zip) (Corrected version)
  Homework3: Show that to find the largest number in a list of n numbers requires at least n-1 comparisions.
  Homework4: Show that to find the second largest number in a list of n numbers requires at least n-2+/lceil log n/rceil comparisons.
  Homework5: Show that binary search is optimal for all searching algorithm performing comparisons only.
  Homework6: Write a program in C/C++/C#/Java to implement the heap sort method in the form HeapSort(int[] A). Note that earlier sumbissions will earn higher scores.
  (Homework 3, 4, 5, 6 Due: 24:00, Oct. 21) (Homework 6 will not be discussed in the practice class.)
  
• 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)
  

  Homework7: Consider the problem of making change for n cents using the fewest number of coins. Assume that each coin's value is an integer. Describe a greedy algorithm to make change consisting of quarters (25c), dimes (10c), nickels (5c), and pennies (1c). (Due: 24:00, Oct. 29)

  Homework8: Write a program in C/C++/C#/Java to implement Dijkstra's algorithm or Bellman-Ford algorithm or Floyd-Warshall algorithm for the shortest path problem. You should include some screenshots to support that your program can run properly. Note that earlier sumbissions will earn higher scores. (Due: 24:00, Nov. 12)
• Quiz1 
• 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-A.zip)(ConvexHull.zip)(Voronoi.ppt)(Voronoi/Delaunay Applet)

• A concept similar to the divide-and-conquer strategy:
  Based on recirsion, we can solve the problem by the solution solving the problem with smaller sizes.
  
  (Tower of Hanoi)(Tower of Hanio Applet)
  
  
• Midterm Examination (including all the materials listed above) (15:00~17:50 on Nov. 13)

• The theory of NP-Completeness (Recipe, cook and carp.zip)(NPC.ppt)
  Homework9: Exercise 8.1 in Lee's book (additional request: you should show the supports for your answers)
  Homework10: Show that 2SAT is a P problem. (Due: 24:00, Nov. 26)
• (NPC2.ppt)(Turing Machine.zip)
• Tree search (TreeSearch.ppt)
  Homework11: Write a program in C/C++/C#/Java to implement Use BFS, DFS, Hill-Climbing or Best-First Search schemes to solve the (n^2-1)-puzzle, n<=10, problem with the evaluation function being the number of misplaced tiles. (notice: 1. For an empty cell, take the left, right, up, down order to expand the search. 2. Programs with graphical output wil have higher scores.)
  For example: given an initial state and the goal state of the 8-puzzle problem, use the program to find the solution.
  (Due: Dec. 10, 24:00)
  
  Initial State:

  2		3
  1	8	4
  7	6	5

  Goal State:
  

  1	2	3
  8		4
  7	6	5

• 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.
  (BranchAndBound.ppt)(SpecializedAStar.ppt)
  Homework12: Use the branch-and-bound strategy to solve the traveling salesperson problem problem on page 217. (Due: Dec. 10, 24:00) (Note: You should draw the search tree.)
  Homework13: Use the A* algorithm to solve the multi-stage graph shortest path problem on page 216. (Due: Dec. 10, 24:00) (Note: You should draw the search tree.) 

• 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)
  Homework14: Use the dynamic programming scheme to solve the multistage graph problem of Ex. 7-1. (Due: Dec. 17, 24:00)
  Homework15: Use the dynamic programming scheme to find a longest common subsequence of S1=ababcdaef and S2=abeadf. (Due: Dec. 17, 24:00)
  
• 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(n^k) for some constant k. Then T(n)=T((1-f)n)+O(n^k). Since 1-f<1, we have T(n)=O(n^k) as n-->infinite.
  (BinarySearch.ppt)(Selection.ppt)(PruneAndSearch.zip)(Prue and Search Convex Hull Algorithm)
  Homework 15: Write the quick hull algorithm and compare it's time complexity with at least two other related algorithms'. (Due: Dec. 24, 24:00)
  
• Approximation algorithms (ApproximationAlgorithms.zip)(Andrew's Monotone Chain Convex Hull Algorithm.ppt)(VertexCover.ppt)
  
• Final Examination (including all materials taught after Midterm Exam.)(Date: Jan. 8 Time:15:00~17:00)

• Midterm 35%
• Final   35%
• Homework, Quiz and Inclass 30% (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
  

Back to My Home