Algorithmics (演算法) 2009

Lecturer: 江振瑞
Teacher Assistant: 葉政峰洪兆緯
Blackborad System: http://bb.ncu.edu.tw (演算法B)
Time: Tuesday 15:00~17:50
Place: E6 - A211
TA Class: Monday
Downloads:

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)
( data )

TextBook:

Introduction to the Design and Analysis of Algorithms -- A Strategic Approach (2/e), R.C.T. Lee et. al., McGraw Hill, 2005.

Reference Books:

Introduction to Algorithms (2/e), Thomas Cormen, Charles Leiserson, Ronald Rivest and Clifford Stein, MIT Press, 2001.
Computer Algorithms, Ellis Horowitz et. al., Silicon Press, 2008.
中文Java程式設計 (第三版) SIM-908A , 江振瑞著, 儒林出版社, 2006.
物件導向資料結構 — 使用Java語言, 江振瑞著, 松崗圖書公司, 2005.
Algorithms, S. Dasgupta, C. Papadimitriou and U. Vazirani, McGraw Hill, 2008.
Programming Challenges, Steven S. Skiena and Miguel Revilla, Elsevier, 2003.
The Algorithm Design Manual, Steven S. Skiena, Elsevier.

Syllabus:

Introduction to Algorithms (Alg.ppt)(Al-Khwarizmi)
Homework1: (a) Exercise 1.2-3 in Cormen's book. (b) Problem 1-1 in Cormen's book. (c) Write an algorithm to input an integer n and output the total number of the factors of n.
Analysis of Algorithms (the complexity of algorithms) (AnalyzingAlgorithms.ppt)(SortAna.zip)
Homework2: Write the binary search algorithm and analyze it's time complextity in the best case, worst case and average case.
The lower bounds of problems (Alg02.zip)
Homework3: Exercises 2.6 and 2.10 in Lee's book. Due date: midnight of the day before next TA class
- Show that to find the second largest number in a list of n numbers requires at least n-2+/lceil log n/rceil comparisons.
- Show that binary search is optimal for all searching algorithm performing comparisons only.
- Show that the Euclidean minimal spanning tree problem has the lower bound of OMEGA(n log n)
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.ppt)(Bellman-Ford.zip)(ShortestPath.zip)
Homework4: Due date: midnight of the day before next TA class

A. 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).
B. Show the correctness of Kruskal's algorithm or Prim's algorithm or Huffman's algorithm. (You should prove the correctness of at least one algorithm. If you prove 2 or more algorihtms, you will get a bonus.)
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)(ComputationGeometry-ConvexHull.zip)(Voronoi.ppt)(Voronoi/Delaunay Applet)
Homework5: Due date: Hand in before next TA class (You should choose either problem A or problem B)
A. Show the details (data structures and procedures) of how to improve the divide-and-conqure 2D rank finding algorithm by presorting.
B. Show the details (data structures and procedures) of how to improve the divide-and-conqure 2D maxima finding algorithm by presorting.
Homework6: Due date: Hand in before next TA class (You should choose either problem A or problem B)
A. Show how to achieve Euclidean nearest neighbor searching in O(log n) time with O(n log n) preprocessing.
B. Show how to solve the Euclidean all nearest neighbor problem in O(n) time with O(n log n) preprocessing.
Midterm Project (5%): Write a program to solve either the Convex Hull or the Voronoi Diagram Problem (due: Nov. 16 before TA's class). You should hand in a hardcopy report and upload your report and program via FTP. TA will ask you to demo your program in TA's class.
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 approaches infinite.
(PruneAndSearch.ppt)
Bonus Project (3%): Write a program to solve the constrained 1-center problem. (Due date: Nov. 23 before TA's class). You should hand in a hardcopy report and upload your report and program via FTP. TA will ask you to demo your program in TA's class.
Test (6%): Nov. 10 (one hour) (Scope: 1. Introduction to Algorithms 2. Analysis of Algorithms 3. The lower bounds of problems)
Dynamic programming:
Dynamic programming is typically applied to solve optimization problems that satisfy the principle of optimality. (Principle of Optimality: Suppose that in solving a problem, we have to make a sequence of decisions D₁, D₂, …, D_n. If this sequence is optimal, then the first k or the last k decisions altogether must be optimal, 1 <= k <= n.)
Dynamic programming algorithm 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)
Homework7: Due date: before next TA class on Nov. 16. (You should choose either Problem A or B.)
A. Write a divide-and-conquer algorithm to solve the consecutive longest monotonically increasing subsequence problem. You should also analyze the time complexity of your algorithm.
B. Write a dynamic programming algorithm to solve the longest monotonically increasing subsequence problem. You should also analyze the time complexity of your algorithm.
Homework8: Due date: before Midterm Exam. on Nov. 24. (You should choose either Problem A or B.)
A. Show how to modify the PRINT-STATIONS procedure for the assembly-line scheduling problem to print out the stations in increasing
order of station number.
B. (Edit Distance) Let A=a1a2...am and B=b1b2...bn. We may transform A to B by the following three edit operations:
1. deletion of a character from A.
2. insertion of a character into A.
3. substitution of a character in A with another character.
Assume that each operations are associated with costs of 3, 2 and 1 respectively. Show the operations that altogether have the minimum cost of transforming GTXYT to TXGYCT. (Hint: You can solve the problem by the dynamic programming strategy.)
Midterm Examination (25%): Nov. 24 (Scope: Greedy, divide-and-conquer, prune-and-search, dynamic programming methods)
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)
Exercise: http://online-judge.uva.es/p/v102/10258.html (Contest Scoreboard)
Exercise: http://online-judge.uva.es/p/v5/531.html (Compromise)

Homework9:

The theory of NP-Completeness ("Recipe, Cook and Carp.zip)(NPC.ppt)
Homework10: (Both problems are bonus) Due date: before next TA class
A. Prove that 3-SAT belongs to NPC.
B. Prove that the "exact set cover" problem reduces to the "sum of subsets" problem.
Tree search (TreeSearch.ppt)
Homework11: Draw diagrams to show how to solve the following 8-puzzle problem by the the Best-First Search scheme with the evaluation function being the number of misplaced tiles. If there is a tie, use the up, left, down, right search order. Due date: before next TA class.

Initial State:

2		3
1	8	4
7	6	5

Goal State:

1	2	3
8		4
7	6	5

Homework12 (Bonus):

Write a program in C/C++/C#/Java to implement the Best-First Search scheme to solve the

(n^2-1)-puzzle, n<=5, problem with the evaluation function being the number of misplaced tiles. Deadline: 9:00pm, Janunary 18, 2010.

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)
Homework13:
A. Use the branch-and-bound strategy to solve the traveling salesperson problem problem on page 217. (Note: You should draw the search tree.)
B. (Bonus) Use the A* algorithm to solve the multi-stage graph shortest path problem on page 216. (Note: You should draw the search tree.)
C. (Bonus) Use the branch-and-bound strategy to solve the following sum of subset problem. Given a set S={7, 1, 4, 6, 14, 25, 5, 8} and M=18. Find a set whose elements add up to M.
Approximation algorithms (ApproximationAlgorithm.ppt)
Final Examination (including all materials taught after Midterm Exam.)

Scoring：

Test 6%
Midterm 25%
Midterm Project 5%
Final 30%
Homework, Quiz and Inclass 35% (Notice! 20%~25% for TAs)

Links：

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