วิชาอัลกอริทึมระดับบัณฑิตศึกษา

ผู้สอน: Jittat Fakcharoenphol
TA: TBA
เวลาเรียน: พฤหัส 6pm - 9pm, ห้อง 507

• คะแนนต่าง ทั้งคะแนนการบ้าน และคะแนนสอบ จะทยอยประกาศที่ลิงก์นี้
• ข้อมูลการส่งการบ้าน ถ้ามีข้อผิดพลาดรีบติดต่อด้วย มีหนึ่งคนที่ส่งการบ้านเป็นกระดาษแต่ไม่ได้เขียนชื่อ กรุณาติดต่อด้วย
• การบ้านโปรแกรมจะมีเพิ่มอีก 2 ข้อ แต่เป็นโบนัส จะประกาศเร็ว ๆ นี้ ไม่มีแล้ว
• สอบปลายภาค ห้อง 503 เวลา 18 - 21
• แบบฝึกหัดสำหรับสอบปลายภาค
  • fin-practice.pdf
  • ข้อสอบเก่า NP-Complete
• สอบกลางภาคครั้งที่ 2 เวลา 9:00 - 12:00 วันอาทิตย์ที่ 26 ก.ย. 2553 ห้อง 503
  • เนื้อหาที่ออก: กราฟและการประยุกต์ใช้งาน, shortest paths, MST, network flows, และ dynamic programming
• สอนชดเชย วันที่ 26 ก.ย. 2553 เวลา 13:00 - 16:00 ห้อง 202
• แบบฝึกหัดสำหรับการสอบกลางภาคครั้งที่ 2
  • mid2-practice1.pdf
  • mid2-practice2.pdf
  • mid2.pdf
  • fin49.pdf ข้อ 3, 4, 5, และ 6
  • brother.png
• สอบกลางภาควันที่ 26 สิงหาคม 2553 เปิดเอกสารได้
• ไม่มีการเรียนการสอนในวันที่ 19 สิงหาคม
• การบ้าน 1 ส่งภายในวันที่ 5 สิงหาคม 2553
• ไม่มีการเรียนการสอนในวันที่ 17 และ 24 มิถุนายน
• สำหรับการเขียนบันทึกคำบรรยาย ดูตัวอย่างจากคำบรรยายเมื่อปีการศึกษา 2550 เราสามารถเขียนสมการคณิตศาสตร์ใน Media Wiki ได้ สะดวก กรุณาดูตัวอย่าง

• การบ้าน 1 ส่งภายในวันที่ 5 สิงหาคม 2553

• Week 1: บทนำ ตัวอย่างการวิเคราะห์ขั้นตอนวิธี: บันทึกคำบรรยาย
• No class on June 17th and June 21th
• Week 2: Data structures
  • Proving correctness using loop invariants
  • Review of running time analysis: Big-O
  • Binary search trees
    • Balanced binary search trees: red-black trees
• Week 3: Divide and Conquer. Recurrences.
  • Red-black trees (cont.)
  • Review, merge sort, quick sort
  • Finding medians in linear time
  • FFT and polynomial multiplication
• Week 4: Data structures
  • FFT and polynomial multiplication (cont.)
  • Hashing
    • Balls and bins experiments
• Week 5:
  • Hashing: Universal hashing
  • Review of priority queues: heaps
  • Randomized Quicksort
  • Treaps
• Midterm I
• Week 6: Minimum spanning trees
• Week 7: Shortest paths
• Week 8: Network flows
• Week 9: Dynamic programming
• Midterm II
• Week 10: Linear programming
• Week 11: Linear programming
• Week 12: NP-completeness
• Week 13: NP-completeness
• Week 14: Additional topics
• Week 15: Additional topics

• Scribe Note 5%
• Homework 15%
• Midterm Exam I 20%
• Midterm Exam II 20%
• Final Exam 30%
• Project 10%

• Algorithms Course Materials by Jeff Erickson
• รายวิชาเมื่อปีการศึกษา 2550