計算理論

• 課程資訊

• 九十一學年度投影片

• 講義

  • 第一章    Introduction
  • 第二章    Turing Machines
  • 第三章    Computability
  • 第四章    Boolean Logic
  • 第七章    Relations Between Complexity Classes
  • 第八章    Reductions and Completeness
  • 第九章    NP-complete Problems

• 考試

  • 期中考
  • 期末報告：選擇下列任一篇 paper, 寫一篇心得報告, 6/24前交
    • PRIMES is in P
    • A Sublinear Algorithm for Weakly Approximating Edit Distance
    • Uniform Hashing in Constant Time and Linear Space
    • Approximate Counting by Dynamic Programming
    • Short Path Queries in Planar Graphs in Constant Time
    • Generating Random Regular Graphs