難解計算問題專論(英文授課)

Selected Topics in Intractable Problems

學期

107-2

學分

0 學分

當期課號

5241

永久課號

IOC5204

開課單位

資訊科學與工程研究所

授課教師

蔡孟宗

校區

光復

類別

選修

上課時間表

* 根據陽明交大上課時間表所列

概述

Understand the limit of computers, and learn how to design algorithms better than exhaustive search for intractable problems.

先修科目

Introduction to Algorithms, Introduction to Formal Language, Probability, Linear Algebra, Data Structures and Object-Oriented Programming

備註

無備註

教學方式

TA: TBA; Course Materials: https://e3new.nctu.edu.tw/login/index.php ; Online Judge: https://oj.nctu.me

評分方式

4 written assignments and 4 programming assignments. Take best 5 out of the 8 assignments.

課程大綱

教師未提供此項資料

週次計畫

週次	主題
第 1 週	NP-hardness, Exponential-time Hypothesis
第 2 週	NP-intermediate, Sparse Languages, Ladner's Theorem, Mahaney's Theorem
第 3 週	Enumeration, Heap's Algorithm
第 4 週	CPU-dependent Instruction Sets, Inline Assembly, Bitwise Parallelism
第 5 週	Table-lookups, Hashing, Dynamic Programming
第 6 週	Pruning by Fractional Solutions, Linear Programming
第 7 週	Pruning by Shortcutting, Matching, Graph Bandwidth
第 8 週	#P-hardness, Permanent, Ryser's Formula
第 9 週	Probabilistic Methods
第 10 週	PTAS, Separator Theorems, Planar Graphs, k-nearest Neighbor Graphs
第 11 週	PCP Theorem, APX-hardness, log-APX-hardness, poly-APX-hardness, APX-intermediate
第 12 週	Approximation Algorithms
第 13 週	Approximation Algorithms
第 14 週	W Hierarchy
第 15 週	Fixed-Parameter Algorithms
第 16 週	Fixed-Parameter Algorithms
第 17 週	RP, co-RP, BPP, ZPP, Randomized Algorithms
第 18 週	Randomized Rounding, Linear Programming, Semidefinite Programming

教科書

Research papers

Office Hours