Algorithmics (演算法) 2010

Lecturer: 江振瑞
Teacher Assistant: 葉政峰黃達育吳玠儀
Blackborad System: http://bb.ncu.edu.tw (演算法B)
Time: Tuesday 15:00~17:50
Place: E6 - A211
TA Class: ~
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 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)(ShortestPath.zip)
Homework3: 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 a counter example that Dijkstra algorithm does not work.
C. Show the correctness of Kruskal, Prim, Dijkstra, Bellman-Ford, or Floyd-Warshell algorithms. (You should prove the correctness of at least one algorithm. If you prove the correctness of more than one algorithm, you will get a bonus.)
D. (Bonus) Show that Bellman-Ford algorithm can detect a negative-weight cycle.
E. (Bonus) Write a program to implement Kruskal, Prim, Dijkstra, Bellman-Ford, or Floyd-Warshell algorithms in any language.
F. (Bonus) Given a plan of nodes (or points) N0, N1,..., Nm, where each node has a constrainted out-degree (or capacity) C0, C1,...,Cm, write a greedy algorithm to construct a spanning tree rooted at N0 shuch that the tree has the smallest summation of "accumulated distances" from N0 to every other nodes.
Paper: Jehn-Ruey Jiang, Chao-Wei Hung, and Jih-Wei Wu, "Bandwidth- and Latency-Aware Peer-to-Peer Instant Friendcast for Online Social Networks," 4th International Workshop on Peer-to-Peer Networked Virtual Environment (P2P-NVE 2010), Shanghai, China, 2010.
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)
Homework4: Due date: before next TA class. (You should choose either Problem A or B.)
A. Write a dynamic programming algorithm to solve the longest monotonically increasing subsequence problem. You should also analyze the time complexity of your algorithm.
B. (Bonus) Write an algorithm that outputs two trajetories with the highest similarity among n given trajectories, each of which is a list of points in a 2D plane sampled per specific time interval.
Paper: Jehn-Ruey Jiang, Ching-Chuan Huang, and Chung-Hsien Tsai, "Avatar Path Clustering in Networked Virtual Environments," 4th International Workshop on Peer-to-Peer Networked Virtual Environment (P2P-NVE 2010), Shanghai, China, 2010.
C. (Bonus) (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.)
Homework5: Due date: before next TA class.
A. Optimally parenthesize a matrix-chain product whose sequence of dimensions is <5, 20, 8, 60, 10, 7> by a dynamic programming algorithm.
B. On the basis of the dynamic programming algorithm to optimally parenthesize a matrix-chain product shown in the slides, write an algorithm to print the optimal pattern of the parenthesized matrix-chain product.
C. (Bonus) Wrtie a program to implement the dynamic programming algorithm to optimally parenthesize a matrix-chain product.
D. (Bonus) Write a program to implement the dynamic programming algorithm to output the longest common subsequence for two given sequences of symbols.
E. (Bonus) Write a program to implement the dynamic programming algorithm to output the optimal binary search tree for n given keys k1, ..., kn with access probabilities p1,..., pn, and n+1 dummy keys d0,...,dn with access probabilities q0,...,qn.
Homework6: Due date: before next TA class. (You should solve at least 2 problems with others being bonuses. Choose either A or B and then choose either C or D.)
A. A multistage graph G=(V,E) is a directed graph in which the vertices are partitioned into k>=2 disjoint sets V1, V2,.., Vk, each of which defines a stage in the graph. In addition, if <u,v> is an edge in E then u belongs to Vi and v belongs to Vi+i for some i, 1<=i<k. The set V1 and Vk are such that |V1|=|Vk|=1. The multistage graph problem is to find a minimum cost path from s in V1 to t in Vk. Below is list representing a multistage graph. Use dynamic programming to solve the correspondling multistage graph problem.
( ((4,3)), ((10,*,9,*),(6,5,*,11)),((4,3,5,3))
B. Given a knapsack problem with knapsack capacity C=10, and 3 objects with weights 10, 3, 5 and profits 40, 20, 30, use the recursive-form dynamic programming technique to solve the knapsack problem.
* Another version of the "knapsack problem" can be used as the basis of public key cryptosystem (PKC): "Given a one-dimensional knapsack of length S and n rods of lengths a1, a2,..., an, the knapsack problem is to find a subset of the rods that exactly fill the knapsack, if such a subset exists." from the paper entitled "Hiding information and signatures in trapdoor knapsacks" by Merkle and Hellman, 1978. You are referred to "A note on security of KMN PKC" by Nasako, Murakami and Kasahara for more details.
* The above-mentioned knapsack problem can also be expressed as the "subset sum" problem: "Given a set of integers and an integer s, does any non-empty subset sum to s?
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)
Homework6: Due date: Hand in before next TA class (You should choose either problem A or problem B)
C. Show the details (data structures and procedures) of how to improve the divide-and-conqure 2D rank finding algorithm by presorting.
D. Show the details (data structures and procedures) of how to improve the divide-and-conqure 2D maxima finding algorithm by presorting.
E. (Bonus) Write a program to implement the improved divide-and-conqure 2D rank finding algorithm. (Deadline: 11/22)
F. (Bonus) Write a program to implement the improved divide-and-conqure 2D maxima finding algorithm. (Deadline: 11/22)
Homework7: 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.
(Bonus) Midterm Project (5%): Write a program to solve either the Convex Hull or the Voronoi Diagram Problem (due: Dec. 6 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 lower bounds of problems (Alg02.ppt)
Homework8: You should solve 2 out of the three problems. Due: before next TA class

A. Show that to find the second largest number in a list of n numbers requires at least n-2+/lceil log n/rceil comparisons.
B. Show that binary search is optimal for all searching algorithm performing comparisons only.
C. Show that the Euclidean minimal spanning tree problem has the lower bound of OMEGA(n log n)

The theory of NP-Completeness ("Recipe, Cook and Carp.zip)(NPC.ppt)
Homework9: (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.
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, k>0. 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)
Homework 10 (Bonus 3%): Write a program to solve the constrained 1-center problem. (Due date: January 3, 2011). 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.

Tree search: (TreeSearch.ppt)
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)
Homework11: (Due date: before the next TA class)
A. Draw diagrams to show how to solve the following 8-puzzle problem by one of the schemes: breadth-first search, depth-first search, hill climbing and best-first search. The evaluation function of the last two schemes is the number of misplaced tiles. If there is a tie, use the up, left, down, and right moving order.
Initial State:

2		3
1	8	4
7	6	5

Goal State:

1	2	3
8		4
7	6	5

B. (Bonus 3%) Write a program to implement the hill climbing or the best-first search scheme to solve the 8-puzzle problem given in 11(A). (Due date: January 3, 2011). 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.
C. (Bonus 6%) Write a program to implement the branch-and-bound strategy to solve the 0/1 knapsack problem. (Due date: January 3, 2011). 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.
Homework 12:
A. Use the branch-and-bound strategy to solve the traveling salesperson problem problem on page 217 of Lee's book. (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 5%) Write a program to implement the A* algorithm to solve the multi-stage graph shortest path problem. (Due date: January 17, 2011). 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.

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)

Exercise:

Approximation algorithms (ApproximationAlgorithm.ppt)
Final Examination (including all materials taught after Midterm Exam. except for NPC)
Distributed Algorithms -- 2 Talks:

The first talk by Prof. Huang, Jiung Yao from National Taipei University (NTPU)

Topic: Mirror Reality – The Society that crosses Virtuality and Reality
Time: 10:00-11:50 on January 4, 2011
Place: A211

The second talk by Porf. Ooi, Wei Tsang from National University of Singapore (NUS)

Topic: Pause and Seek: Effects of Playback Interaction on Server Load in Peer-Assisted Video-on-Demand Systems
Time: 15:00-17:50 on January 4, 2011
Place: A211

Scoring：

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