University of Tsukuba | Grad. Scho. Syst. and Info. Eng. | Dept. Comp. Sci. | List of Courses
Takahito Kuno, Yoshio Sano
E-Mail T. Kuno: takahito (at), Y. Sano: sano (at)
Office hours F932 (T. Kuno), F834 (Y. Sano), A/N (appointment necessary)
Cource# 01CH109
Area Information Mathematics and Modeling
Basic/Advanced 基礎科目
Course style Lecture
Term SprA
Period Tue3,4
Room# 3B311
Keywords Mathematical Optimization, Algorithms, Computational Complexity
Prerequisites Linear Algebra, Calculus
relation degree program competence Knowledge Utilization Skills, Management Skills, International Skills, Research Skills, Expert Knowledge
Outline This course treats selected topics in mathematical optimization and computational complexity.
Course plan Lecure 1: Introduction to Mathematical Optimization
(Optimization Problem, Linear Programming, Integer Programming, Combinatorial Optimization, Traveling Salesman Problem, Shortest Path Problem, Algorithm, Computational Complexity)
Lecture 2: Algorithms and Computational Complexity
(Shortest Path Problem, Bellman-Ford Algorithm, Knapsack Problem, Dynamic Programming)
Lecture 3: NP-Completeness and Complexity Classes
(Decision Problem, Class P, Class NP, NP-completeness, NP-hardness, Polynomial-time Reduction, Karp's 21 NP-complete problems, Cook's Theorem)
Lecture 4: Efficient Algorithms and Mathematical Structure
(Maximum Spanning Tree Problem, Matroid, Independent Set, Base, Rank Function, Circuit, Greedy Algorithm, Characterization)
Lecture 5: Algorithm Design for Hard Optimization Problems
(Knapsack Problem, Heuristics, Approximation Algorithm, Enumeration, Branch and Bound)
Textbook Class materials are distributed via web.
References [1] B. Korte and J. Vygen: Combinatorial Optimization: Theory and Algorithms, Sixth Edition (Algorithms and Combinatorics 21), Springer (2018)
[2] J. Kleinberg and E. Tardos: Algorithm Design, Pearson (2005)
[3] A. Schrijver: Combinatorial Optimization: Polyhedra and Efficiency (Algorithms and Combinatorics 24), Springer (2003)
Evaluation Evaluate based on reports.
Evaluation criteria: A passing score is 60% of the total score. Scores A+ to C are based on this score.