Table of Contents
วิชาอัลกอริทึมระดับบัณฑิตศึกษา
ผู้สอน: Jittat Fakcharoenphol
TA: TBA
เวลาเรียน: พฤหัส 6pm - 9pm, ห้อง 507
ประกาศ
- คะแนนต่าง ทั้งคะแนนการบ้าน และคะแนนสอบ จะทยอยประกาศที่ลิงก์นี้
- ข้อมูลการส่งการบ้าน ถ้ามีข้อผิดพลาดรีบติดต่อด้วย มีหนึ่งคนที่ส่งการบ้านเป็นกระดาษแต่ไม่ได้เขียนชื่อ กรุณาติดต่อด้วย
การบ้านโปรแกรมจะมีเพิ่มอีก 2 ข้อ แต่เป็นโบนัส จะประกาศเร็ว ๆ นี้ไม่มีแล้ว- สอบปลายภาค ห้อง 503 เวลา 18 - 21
- แบบฝึกหัดสำหรับสอบปลายภาค
- สอบกลางภาคครั้งที่ 2 เวลา 9:00 - 12:00 วันอาทิตย์ที่ 26 ก.ย. 2553 ห้อง 503
- เนื้อหาที่ออก: กราฟและการประยุกต์ใช้งาน, shortest paths, MST, network flows, และ dynamic programming
- สอนชดเชย วันที่ 26 ก.ย. 2553 เวลา 13:00 - 16:00 ห้อง 202
- แบบฝึกหัดสำหรับการสอบกลางภาคครั้งที่ 2
- fin49.pdf ข้อ 3, 4, 5, และ 6
- สอบกลางภาควันที่ 26 สิงหาคม 2553 เปิดเอกสารได้
- ไม่มีการเรียนการสอนในวันที่ 19 สิงหาคม
- การบ้าน 1 ส่งภายในวันที่ 5 สิงหาคม 2553
- ไม่มีการเรียนการสอนในวันที่ 17 และ 24 มิถุนายน
- สำหรับการเขียนบันทึกคำบรรยาย ดูตัวอย่างจากคำบรรยายเมื่อปีการศึกษา 2550 เราสามารถเขียนสมการคณิตศาสตร์ใน Media Wiki ได้ สะดวก กรุณาดูตัวอย่าง
การบ้าน
- การบ้าน 1 ส่งภายในวันที่ 5 สิงหาคม 2553
Course Outline
- 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.)
-
- Balls and bins experiments
- Week 5:
- Hashing: Universal hashing
- Review of priority queues: heaps
- Randomized Quicksort
- 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
Gradings
- Scribe Note 5%
- Homework 15%
- Midterm Exam I 20%
- Midterm Exam II 20%
- Final Exam 30%
- Project 10%