Course title
アルゴリズム解析特論   [Selected Topics in Algorithm Analysis]
Course category courses for doctoral programs  Requirement   Credit 2 
Department   Year   Semester 3rd 
Course type 3rd  Course code 1080430
Instructor(s)
宮代 隆平   [MIYASHIRO Ryuhei]
Facility affiliation Faculty of Engineering Office afjgxte/L1151  Email address

Course description
This lecture demonstrates some efficient algorithms and algorithm theory, such as follows: computational complexity, P and NP, network flow, divide and conquer, greedy methods, local search, approximation/randomized algorithm, dynamic programming.

Expected Learning
- Learning the whole knowledge related to the theory of algorithms
- Learning the ability to make efficient algorithms
Course schedule
(1) Introduction to the algorithm theory
(2) Computational complexity
(3) NP-complete
(4) NP-hardness
(5) Network flow
(6) Network flow (cont.)
(7) Matchings
(8) Divide and Conquer
(9) Greedy algorithms
(10) Local search
(11) Approximation algorithms
(12) Randomized algorithms
(13) Dynamic programming
(14) Online algorithms
(15) Conclusion
Prerequisites
Basic algorithm theory and programming skill
Required Text(s) and Materials
None
References
- Algorithm Design, Kleinberg & Tardos
Assessment/Grading
Report & Examinations
Message from instructor(s)
Course keywords
Algorithm, NP-complete, Computational Complexity
Office hours
Please e-mail me when you have questions.
Remarks 1
Remarks 2
Related URL
Lecture Language
Japanese
Language Subject
Last update
12/25/2019 4:28:10 PM