204512 ภาคต้น 2550

วิชาการออกแบบและวิเคราะห์อัลกอริทึม (Design and analysis of algorithms)

This course provides an overview on the design and analysis of algorithms at a graduate level. We will focus on many useful algorithms, which should provide a good guide for the students on fundamental algorithm design techniques.

Course syllabus: pdf

• อาจารย์ผู้สอน: จิตร์ทัศน์ ฝักเจริญผล

ประกาศ

• สอบกลางภาคครั้งที่สอง 10 ตุลาคม 2550 เวลา 18-21 น.
  • อนุญาตให้นำ เอกสารใด ๆ ก็ได้ เข้าห้องสอบ
  • เนื้อหา Shortest paths, Minimum spanning trees และ Network flows
  • เอกสารเพิ่มเติม: ข้อสอบ กลางภาค และ ปลายภาค วิชา algorithms ของป.ตรี เนื้อหาบางข้อไม่เกี่ยวข้องกับการสอบครั้งนี้
• สอบกลางภาคครั้งแรก 21 กค 50 เวลา 9-12 น. ห้อง 507. (เพิ่มเติม) 22 กค 50 เวลา 9-12 น.
• ยินดีต้อนรับสู่วิชา

การบ้าน

• การบ้าน 1 กำหนดส่ง 2 ส.ค. 2550
• การบ้าน 2 ทำเฉพาะข้อที่มีเครื่องหมายอัศเจรีย์ (ข้ออื่น ๆ จะทำหรือไม่ก็ได้) กำหนดส่ง 9 ต.ค. 2550

บันทึกคำบรรยาย

เว็บนี้เป็นวิกิ และใช้ซอฟต์แวร์เดียวกับวิกิพีเดีย

อ่านวิธีการแก้ไขวิกิที่ วิธีการแก้ไขหน้าวิกิ อย่าลืมว่าลิงก์ดังกล่าวจะพาท่านไปที่วิกิพีเดีย ถ้าต้องการทดลองแก้ไขหน้าในเว็บนี้ ให้ทดลองที่นี่: กระบะทราย

การแก้ไขทั้งหมดในวิกินี้ถูกเผยแพร่ภายใต้ GFDL นั่นคือใครก็ตามสามารถจะนำเอกสารที่คุณเขียนไปใช้ได้อย่างเสรี

จะมีเครื่องมือเพิ่มเติมช่วยในการเขียนเร็ว ๆ นี้...

• การบรรยายครั้งที่ 1 (วันที่ 6 มิ.ย.): ทฤษฎีจำนวนเบื้องต้น พีชคณิตมอดุโล การแบ่งปันความลับ
• การบรรยายครั้งที่ 2 (วันที่ 13 มิ.ย.): Divide and conquer. Recurrences. FFT
  • เอกสารประกอบ ร่างบทที่ 2 Divide and Conquer ของหนังสือ Algorithms โดย Dasgupta, Papadimitriou, และ Vazirani
• การบรรยายครั้งที่ 3 (วันที่ 20 มิ.ย.): Data Structure#1 Tree, Amortized Analysis
  • เอกสารประกอบ Animation Demo Binary Search Tree
  • เอกสารประกอบ Animation Demo AVL Tree
  • เอกสารประกอบ Animation Demo Splay Tree
• การบรรยายครั้งที่ 4 (วันที่ 27 มิ.ย.): Probability, Skip List, Hashing
• การบรรยายครั้งที่ 5 (วันที่ 4 ก.ค.): Minimum spanning trees, Union-Find data structure
• การบรรยายครั้งที่ 6 (วันที่ 11 ก.ค.): Shortest Paths
• การบรรยายครั้งที่ 7 (วันที่ 18 ก.ค.): Network Flows
• การบรรยายครั้งที่ 8 (วันที่ 1 ส.ค.): Blocking Flows update: 2 ตุลาคม, 8 ตุลาคม
• การบรรยายครั้งที่ 9 (วันที่ 8 ส.ค.): Dynamic Programming
• การบรรยายครั้งที่ 10 (วันที่ 29 ส.ค.): Linear Programming
• การบรรยายครั้งที่ 11 (วันที่ 5 ก.ย.): Linear Programming (ต่อ)
• การบรรยายครั้งที่ 12 (วันที่ 12 ก.ย.): Min-cost flow
• การบรรยายครั้งที่ 13 (วันที่ 19 ก.ย.): NP-completeness
• การบรรยายครั้งที่ 14 (วันที่ 26 ก.ย.): Approximation algorithms
• การบรรยายครั้งที่ 15 Algorithmic game theory
• การบรรยายครั้งที่ 16 Algorithmic game theory

Useful links

• ภาคเรียนก่อน 2547, 2548, 2549
• 6.854/18.415J MIT Advanced Algorithms
• CS270 Berkeley Combinatorial Algorithms and Data Structures
• CS 473 UIUC Algorithms <-- อันนี้ link ไปไม่เจอแล้วครับ
• CS 683 Cornell Advanced Algorithms