Important dates
2021/12/23:
2021/12/30: (報告組別)
黃得為、蔡若穎、陳昱臻
陳柏諺、蔡秉倫、張綺舫
鄭暐翰、楊翊辰、曾則儒
2021/01/06: (報告組別)
姚秉均、楊秉軒、施承甫
陳兆閔、陳冠廷
呂昀珊、鄭思怡、林于立
Info
Course: Computation Theory
Semester: 110-1
Credit: 3
Time: Thu 9:10-12:10
Classroom: S204
(Google meet) https://meet.google.com/tow-gghp-nhw
Textbook
Michael Sipser. Introduction to the Theory of Computation, 3/e. CENGAGE Learning.
Reference
Christos H. Papadimitriou. Computational Complexity. Addison-Wesley
Grading
Midterm 40% (take-home exam)
Final 50% (oral presentation)
Participation 10%
Syllabus
Introduction (last update: 2021/09/22)
Regular languages (last update: 2021/09/22)
The Church-Turing thesis (last update: 2021/09/30)
Decidability (last update: 2021/10/14)
Reducibility (last update: 2021/10/21)
Time complexity (last update: 2021/11/18)
Space complexity (last update: 2021/12/01)
Intractability (last update: 2021/12/16)
Selected topics
Papers for final report
Alex Churchill, Stella Biderman and Austin Herrick. Magic: the Gathering is Turing Complete. https://arxiv.org/abs/1904.09828
黃得為、蔡若穎、陳昱臻
Allan Scott, Ulrike Stege, and Iris van Rooij. Minesweeper may not be NP-complete but is hard nonetheless. The Mathematical Intelligencer, 33:5–17, 2011. https://link.springer.com/article/10.1007/s00283-011-9256-x
姚秉均、楊秉軒 + (施承甫)
E. Costa, V. L. Pessoa, R. Sampaio, R. Soares: PSPACE-completeness of two graph coloring games, TCS 824 (2020), 36-45.
陳柏諺、蔡秉倫 + (張綺舫)
R. R. Madireddy, A. Mudgal: Approximability and hardness of geometric hitting set with axis-parallel rectangles. IPL 141 (2019), pp. 9-15
鄭暐翰、楊翊辰、曾則儒
Y. Faenza, I. Mourtos, M. Samaris, J. Sethuraman: (Un)stable matchings with blocking costs. OR Letters 49 (2021), pp. 655–662.
陳兆閔、陳冠廷
Y. Iwata: A faster algorithm for dominating set analyzed by the potential method. IPEC 2011, LNCS 7112, pp. 41–54,
呂昀珊、鄭思怡、林于立