课程大纲
COURSE SYLLABUS
1.
课程代码/名称
Course Code/Title
CSE5003/高级算法 Advanced Algorithms
2.
课程性质
Compulsory/Elective
Elective
3.
课程学分/学时
Course Credit/Hours
3/64
4.
授课语言
Teaching Language
英文 English
5.
授课教师
Instructor(s)
Hisao Ishibuchi
6.
是否面向本科生开放
Open to undergraduates
or not
Yes
7.
先修要求
Pre-requisites
（ 如 面 向 本 科 生 开 放 ， 请 注 明 区 分 内 容 。 If the course is open to
undergraduates, please indicate the difference.）
CS208 算 法 设 计 与 分 析 Algorithm Design and Analysis (for undergraduate
students)
For postgraduate students, no prerequisites.
8.
教学目标
Course Objectives
This course explains various algorithms for a wide variety of combinatorial optimization problems such as load
balancing, center selection, set covering, vertex cover, disjoint path, and knapsack problems. As a related topic to
center selection, some clustering algorithms are also explained. For each problem, a greedy algorithm is firstly
explained. Students will learn the mechanism of the greedy algorithm. Next, a theoretical lower bound of the solution
quality obtained by the greedy algorithm is derived. Students will learn how to evaluate the greedy algorithm
theoretically. Then it is explained that the performance of the greedy algorithm depends on some randomness such
as a random initial choice and a random tiebreak. Appropriate handling of such randomness is discussed. Finally,
the greedy algorithm is further analyzed by applying to various problem instances. Students will deeply understand
the mechanism of the greedy algorithm by creating both easy and difficult problem instances. Students will also
understand how to evaluate the greedy algorithm empirically, especially the importance of appropriate selection of
test problem instances. After explaining the greedy algorithm for each problem, some other approaches are
explained. They are linear programming-based relaxation for load balancing and vertex cover, local search, dynamic
programming, and branch-and-bound for knapsack problems. For the vertex cover problem, three algorithms are
compared: a pricing method, a greedy set cover algorithm, and a linear program-based relaxation method. Students
will learn that the performance of each algorithm depends on the characteristic features of a problem instance: No
algorithm work well on all problem instances.
9.
教学方法
Teaching Methods
Lectures, weekly assignments and presentations.
10.
教学内容
Course Contents
Section 1
Greedy nearest neighbor TSP algorithm
[Lab 1] Creation of test problems to explain the greedy nearest neighbor TSP
algorithm
Section 2
Greedy load balancing.
- Short presentations by students on clustering.
- Taxonomy of optimization: approximate optimization (greedy, iterated
improvement) and exact optimization.
- Greedy load balancing algorithm.
- Theoretical lower bound of the solution quality.
[Lab 2] Implementation of the greedy load balancing algorithm. Creation of simple
and difficult problem instances.
Section 3
Sorted greedy load balancing.
- Short presentations by students on greedy load balancing.
- Dependency of the performance of the greedy load balancing algorithm on the
order of jobs.
- Sorted greedy load balancing algorithm.
- Theoretical lower bound of the solution quality
[Lab 3] Implementation of the sorted greedy load balancing algorithm. Creation of
simple and difficult problem instances.
Section 4
Center selection.
- Short presentations by students on sorted greedy load balancing.
- Virtual center selection algorithm.
- Center selection algorithm.
- Theoretical lower bound of the solution quality.
[Lab 4] Implementation of the center selection algorithm. Creation of simple and
difficult problem instances.
Section 5
Clustering.
- Short presentations by students on center selection.
- Dependency of the result of the center selection algorithm on the choice of the
first site.
- k-means algorithm.
- Choice of initial cluster centers.
- Choice of the number of clusters.
[Lab 5] Implementation of the k-means algorithm. Design of an initialization
method.
Section 6
Fuzzy clustering.
- Short presentations by students on clustering.
- Fuzzy c-means algorithm.
- Comparison between k-means and fuzzy c-means.
- Effect of the parameter m in the fuzzy c-means algorithm on clustering results.
[Lab 6] Implementation of the fuzzy c-means algorithm. Creation of a data set to
clearly demonstrate the difference between c-means and fuzzy k-means. Creation
of a data set to clearly demonstrate the effect of m on clustering results by fuzzy k-
means.
Section 7
Set cover.
- Short presentations by students on fuzzy clustering.
- Greedy set cover algorithm.
- Theoretical lower bound of the solution quality.
[Lab 7] Implementation of the greedy set cover algorithm. Creation of simple and
difficult problem instances.
Section 8
Vertex cover.
- Short presentations by students on set cover.
- Reformulation of vertex cover problems as set cover problems.
- Pricing method.
- Theoretical lower bound of the solution quality.
[Lab 8] Implementation of the pricing method. Creation of simple and difficult
problem instances. Comparison between the greedy set cover algorithm and the
pricing method for vertex cover.
Section 9
Greedy set cover algorithm and pricing method.
- Short presentations by students on vertex cover.
- Comparison between the greedy set cover algorithm and the pricing method.
- Linear programming.
[Lab 9] Download of some linear programming software packages. Their
comparison on large-scale linear programming problem instances.
Section 10
Linear programming-based relaxation method for vertex cover.
- Short presentations by students on linear programming.
- Relaxation problems of integer programming problems.
- Linear programming-based relaxation method for vertex cover.
- Theoretical lower bound of the solution quality.
[Lab 10] Comparison among the greedy set cover algorithm, the pricing method
and the linear programming-based relaxation method for vertex cover by creating a
difficult problem instance for each method.
Section 11
Generalized load balancing.
- Short presentations by students on the performance comparison of the three
methods.
- Generalization of the load balancing problem.
- Linear programming-based relaxation method for generalized load balancing.
- Theoretical lower bound of the solution quality.
[Lab 11] Creation of a problem instance where a graph with no cycle is obtained.
Creation of another problem where a graph with one or two cycles are obtained.
Section 12
Disjoint paths problem with the edge capacity c = 1.
- Short presentations by students on generalized load balancing.
- Greedy disjoint paths algorithm.
- Theoretical lower bound of the solution quality.
[Lab 12] Creation of easy and difficult problem instances.
Section 13
Disjoint paths problem with the edge capacity c > 1.
- Short presentations by students on disjoint paths with c = 1.
- Pricing method for disjoint paths with c > 1.
- Theoretical lower bound of the solution quality.
[Lab 13] Creation of easy and difficult problem instances for the pricing method
with c = 2.
Section 14
Knapsack Problem: Greedy algorithm
- Short presentations by students on disjoint paths with c = 2.
- Greedy algorithm.
- Theoretical lower bound of the solution quality.
[Lab 14] Implementation of the greedy algorithm. Creation of easy and difficult
problem instances.
Section 15
Knapsack Problem: Exact optimization algorithms and local search
- Short presentations by students on the greedy algorithm for knapsack
problems.
- Branch-and-bound algorithm.
- Implementation issues of branch-and-bound.
- Local search.
- Neighborhood structure.
- Variable neighborhood search.
- Iterated local search.
- Constraint handling.
- Representation of solutions: 0-1 variables, real number variables, and
permutations.
[Lab 15] Preparation for the final presentation on algorithms.
Section 16
Final presentation on algorithms.
[Lab 16] Final presentation on algorithms (continue).
11.
课程考核
Course Assessment
（
○
1
考核形式 Form of examination；
○
2
.分数构成 grading policy；
○
3
如面向本科生开放，请注明区分内容。
If the course is open to undergraduates, please indicate the difference.）
Class performance including attendance, assignments and presentations: 40%
Final presentation: 10%
Final examination: 50%
(no difference between postgraduate and undergraduate students)
12.
教材及其它参考资料
Textbook and Supplementary Readings
Supplementary Readings:
Book Title: Algorithm Design
Authors: Jon Kleinberg and Eva Tardos
Publisher: PEARSON Addison Wesley
