01204512 ภาคต้น 2555

ใน วิชาอัลกอริทึมระดับบัณฑิตศึกษา เราจะศึกษาเนื้อหาในเชิงวิเคราะห์มากขึ้น และเป็นเนื้อหาที่มีความทันสมัยมากกว่าเนื้อหาที่เรียนในระดับปริญญาตรี

ประกาศ

• สำหรับการติดต่อและปรึกษาทั่วไป เราจะใช้ Group 01204512/55 Graduate algorithms บน facebook

การวัดผล

• การบ้าน: 20%
• สอบ: กลางภาค 30%, ปลายภาค 30%
• โครงงานกลุ่ม: 20% (ในส่วนโครงงานนี้อาจจะเป็นการนำเนื้อหาที่เรียนมาประยุกต์ใช้ในหัวข้อที่นิสิตสนใจ หรืออาจจะเป็นการช่วยกันอ่านเปเปอร์ทางอัลกอริทึมที่เกี่ยวข้องกับหัวข้อวิจัยและนำเสนอกับอาจารย์ผู้สอน)

เนื้อหาโดยรวม

• Divide-and-conquer method
• Dynamic programming
• Multiplicative weights update method and applications
• Graph algorithms: shortest paths and maximum flows
• Linear programming
• Randomized algorithms
• Algorithms in machine learning: perceptron, SVM, dimension reduction techniques

เนื้อหาแยกละเอียดเป็นสัปดาห์

• สัปดาห์ 1. Introduction, divide-and-conquer method, matrix multiplication, FFT
  • เอกสาร บทที่ 2 จากหนังสือ Algorithms โดย Dasgupta, Papadimitriou, Vazirani (ดาวน์โหลดดราฟต์ของบทดังกล่าวได้จากลิงก์)

• สัปดาห์ 2. Dynamic programming
  • เอกสาร บทที่ 6 จากหนังสือ Algorithms โดย Dasgupta, Papadimitriou, Vazirani

• สัปดาห์ 3. Review of shortest path and maximum flow problems. Dueling subroutines.
  • สามารถอ่านเนื้อหาละเอียดในส่วน shortest paths จากบทที่ 4 และเนื้อหาส่วน maximum flows จากส่วนที่ 7.2 จากหนังสือ Algorithms โดย Dasgupta, Papadimitriou, Vazirani
  • ส่วนของ Congestion minimization ดูจาก ปัญหา congestion minimization หรือเอกสาร lecture note จากเว็บ http://www.cs.berkeley.edu/~satishr/cs270/sp12/ หัวข้อ Introduction and Routing/Toll Games.

• สัปดาห์ 4. Maximum flow algorithms, Congestion minimization (cont.), Intro to Games
  • การวิเคราะห์ปัญหา congestion minimization

• สัปดาห์ 5. Two-player Games. Expert's algorithm.
  • lecture note จากเว็บ http://www.cs.berkeley.edu/~satishr/cs270/sp12/ หัวข้อ Game examples และ Expert's algorithm.

• สัปดาห์ที่ 6 Applications of the Expert's algorithm: solving two-player zero-sum games, AdaBoost, congestion minimization.
  • lecture note จากเว็บ http://www.cs.berkeley.edu/~satishr/cs270/sp12/ หัวข้อ Expert's algorithms Application to Min-Max for Games and Boosting

• สัปดาห์ที่ 7 Linear programming and duality
  • เอกสาร บทที่ 7 จากหนังสือ Algorithms โดย Dasgupta, Papadimitriou, Vazirani
  • Lecture 5-6 จากเว็บ http://theory.stanford.edu/~trevisan/cs261/

• สัปดาห์ที่ 8 Linear programming duality, weighted bipartite matching
  • 01204512/weight bipartite matching
  • เอกสารประกอบ:
    • lecture 10 Primal-Dual Algorithm for Weighted Bipartite Matching จากวิชา CS 598, UIUC
    • lecture notes on bipartite matching จากวิชา 18.433, MIT

• สัปดาห์ที่ 9 On-line bipartite matching, AdWords
  • On-line bipartite matching made simple Benjamin Birnbaum and Claire Mathieu, ACM SIGACT News, Volume 39 , Issue 1 (March 2008), pp. 80-87.

• สัปดาห์ที่ 10 Randomized algorithms pdf

• สัปดาห์ที่ 11 Sparsest cuts, eigenvalues, eigenvectors

• สัปดาห์ที่ 12 Cheeger's Inequality

• สัปดาห์ที่ 13 NP-Completeness
  • เอกสาร บทที่ 8 จากหนังสือ Algorithms โดย Dasgupta, Papadimitriou, Vazirani (ดาวน์โหลดดราฟต์ของบทดังกล่าวได้จากลิงก์)

• สัปดาห์ที่ 14 NP-Completeness (ต่อ) และวิธีการจัดการ
  • เอกสาร บทที่ 8 และ 9 จากหนังสือ Algorithms โดย Dasgupta, Papadimitriou, Vazirani (ดาวน์โหลดดราฟต์ของบทดังกล่าวได้จากลิงก์)

• สัปดาห์ที่ 15: Streaming algorithms
  • เอกสารหัวข้อ Streaming และ Streaming: Frequency Estimation จากเว็บ http://www.cs.berkeley.edu/~satishr/cs270/sp11/index.html

การบ้าน

• การบ้าน 1 กำหนดส่ง 8 ส.ค. 2555
  • ส่วนที่ 1: ไฟล์:01204512-55-hw01.pdf
  • ส่วนที่ 2: .pdf, .ps

• การบ้าน 2 กำหนดส่ง 22 ต.ค. 2555 .pdf

ลิงก์อื่น ๆ

• วิกิรายวิชาปี 2555 มีสรุปของแต่ละการบรรยายโดยนิสิต