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 จากเว็บ [1] หัวข้อ Introduction and Routing/Toll Games.

• 4. Maximum flow algorithms, Approximating max-flow using congestion minimization algorithms, Games

ลิงก์อื่น ๆ

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