Lecturer: 江振瑞
Teacher Assistant: 葉政峰 廖基豪
Blackborad System: http://bb.ncu.edu.tw
(演算法B)
Time: Tuesday 15:00~17:50
Place: E6 - A2O9
TA Class: ~
Downloads:
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)(MyBookCh1)(JavaScript
簡介) (9/18)
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 summation of
all n's factors
except n. (D) Write
an algorithm to input an integer n
and output the largest perfect number less than n.
- Analysis of Algorithms (the complexity of algorithms) (AnalyzingAlgorithms.ppt)(SortAna.ppt) (9/26)
Homework2: (A) Write the binary
search
algorithm and analyze it's time complextity in the best case, worst
case and average case.
(B) Show the time
complexity of the (improved) bubble sort algorithm is O(n^2) in the
average case.
- The divide-and-conquer strategy (I): (10/2)
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)(10/2)
Homework3: 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. 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.
C. (Optional,
Bonus 3%) Write a program
to implement the improved divide-and-conqure 2D rank finding algorithm. (Deadline:
The midterm exam week)
D. (Optional, Bonus 3%) Write a program to
implement the divide-and-conqure
2D maxima finding
algorithm. (Deadline: The midterm exam week)
E. (Optional, Bonus 3%) Write a program to
implement the divide-and-conqure
closet pair of 2D points
algorithm. (Deadline: The midterm exam week)
- The greedy method: (10/16)
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)
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 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.
- The divide-and-conquer strategy (II): (10/23)
(FFT.zip)(ComputationGeometry.ppt)(ConvexHull.ppt)(Voronoi.ppt)(Voronoi/Delaunay
Applet)
Homework5:
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.
C. Show an example of FFT
(DFT) applications. (Bonus)
D. Show an output-sensitive
algorithm in details to find the convex hull of given points. (hint:
Jarvis's algorithm)(Bonus)
- The prune-and-search strategy: (10/30)
=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, k>0. Then T(n)=T((1-f)n)+O(nk).
Since 1-f<1, we have T(n)=O(nk) as n approaches infinite.
(PruneAndSearch.ppt)
Homework6: Referring to the note,
describe the Kirkpatrick-Seidel's Prune-and-Search Convex Hull
algorithm and show that its time complexity is O(n log h), where n is
the number of given planar points and h is the size of the output
convex hull.
- The lower bounds of problems (LowerBound.ppt)
(11/6)
A lower bound of a problem is the least time complexity required for
any algorithm which can be used to solve this problem.
- The theory NP-Completeness (Recipe,
Cook and Carp)(NPC.ppt)
(11/6)
If any one NP-complete problem can be solved in polynomial time,
then every problem in NP can also be solved in polynomial time (i.e.,
P=NP).
Homework7:
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. The partion problem is described as follows. Given a set S of
positive integers, does there exist a partion S1 and S2 of S such that
the sum of integers in S equals the sum of integers in S2. Show that
the partion probolem is a NP problem.
C. The sum of subsets problem is described as follows. Given a
set S of integers and a specific integer M, does there exist a subset
of
the integers that sum to M? Show that the sum of subsets problem is a
NP problem.
D. (Bonus) Show that binary search is optimal for all searching
algorithm performing comparisons only.
E. (Bonus) Show that the Euclidean minimal spanning tree problem has
the lower bound of OMEGA(n log n).
Midterm
Exam. for all materials taught before. (11/13)
- Dynamic programming: (11/20)
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 D1, D2, …, Dn. 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.pptx)
Homework8:
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. Optimally parenthesize a matrix-chain product whose sequence of
dimensions is <5, 20, 8, 60, 10, 12> by a dynamic programming
algorithm.
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.)
(
DynamicP2.pptx)
(11/27)
Homework9:
A. Given a 0/1 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 0/1 knapsack problem.
B. The resource allocation problem is defined as
follows. We are given m resources and n projects. A profit P(i, j) will
be obtained if i, 0<=i<=m, resources are allocated to project j.
The problem is to find an allocation of resources to maximize the total
profit. Solve the resource allocation problem with the following profit
matrix
Project (j)\Resources
allocated
(i)
|
1
|
2
|
3
|
Project 1
|
2
|
8
|
9
|
Project 2
|
5
|
6
|
7
|
Project 3
|
2
|
4
|
5
|
C. (Bonus) Write an algorithm to solve the resource allocation
problem.
