01204512 ภาคต้น 2555
ไปยังการนำทาง
ไปยังการค้นหา
ใน วิชาอัลกอริทึมระดับบัณฑิตศึกษา เราจะศึกษาเนื้อหาในเชิงวิเคราะห์มากขึ้น และเป็นเนื้อหาที่มีความทันสมัยมากกว่าเนื้อหาที่เรียนในระดับปริญญาตรี
เนื้อหา
ประกาศ
- สำหรับการติดต่อและปรึกษาทั่วไป เราจะใช้ Group 01204512/55 Graduate algorithms บน facebook
ตารางนัด present
- วันพฤหัสที่ 18 ต.ค.
- บ่าย
- 1
- 2
- 3
- เย็น
- 1
- 2
- 3
- บ่าย
- วันจันทร์ที่ 22 ต.ค.
- เย็น
- 1: Pisit Makpaisit
- 2: Atikan Muang-ngeon
- 3: Narongsak Thipjoy
- เย็น
- วันพุธที่ 24 ต.ค.
- บ่าย
- 1: Sasithorn Suchaiya
- 2: Pasakorn Tiwatthanont
- 3
- เย็น
- 1: KaoPoon Pabo
- 2: Suphamit Plathong
- 3: Natapon Aom Saengtaiyarak
- บ่าย
การวัดผล
- การบ้าน: 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
- สัปดาห์ 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 มีสรุปของแต่ละการบรรยายโดยนิสิต
