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

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

===== ประกาศ =====
  * [[https://spreadsheets.google.com/pub?key=0AjfseVoRVfDkdDA1U25IbERaNlJXUHR2OUg0dVp4bHc&hl=en&output=html|คะแนนต่าง ทั้งคะแนนการบ้าน และคะแนนสอบ]] จะทยอยประกาศที่ลิงก์นี้
  * [[https://spreadsheets.google.com/pub?key=0AjfseVoRVfDkdDA1U25IbERaNlJXUHR2OUg0dVp4bHc&hl=en&single=true&gid=0&output=html|ข้อมูลการส่งการบ้าน]]  ถ้ามีข้อผิดพลาดรีบติดต่อด้วย  มีหนึ่งคนที่ส่งการบ้านเป็นกระดาษแต่ไม่ได้เขียนชื่อ กรุณาติดต่อด้วย
  * <del>การบ้านโปรแกรมจะมีเพิ่มอีก 2 ข้อ แต่เป็นโบนัส จะประกาศเร็ว ๆ นี้</del> ไม่มีแล้ว
  * สอบปลายภาค ห้อง 503 เวลา 18 - 21 
  * แบบฝึกหัดสำหรับสอบปลายภาค
    * [[http://www.cpe.ku.ac.th/~jtf/204512-53/practices/fin-practice.pdf|fin-practice.pdf]]
    * [[http://theory.cpe.ku.ac.th/wiki/index.php/%E0%B8%82%E0%B9%89%E0%B8%AD%E0%B8%AA%E0%B8%AD%E0%B8%9A%E0%B9%80%E0%B8%81%E0%B9%88%E0%B8%B2_204512_%E0%B8%9A%E0%B8%B2%E0%B8%87%E0%B8%AA%E0%B9%88%E0%B8%A7%E0%B8%99|ข้อสอบเก่า 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
    * [[http://www.cpe.ku.ac.th/~jtf/204512-53/practices/mid2-practice1.pdf|mid2-practice1.pdf]]
    * [[http://www.cpe.ku.ac.th/~jtf/204512-53/practices/mid2-practice2.pdf|mid2-practice2.pdf]]
    * [[http://www.cpe.ku.ac.th/~jtf/204512-53/practices/mid2.pdf|mid2.pdf]]
    * [[http://www.cpe.ku.ac.th/~jtf/204512-53/practices/fin49.pdf|fin49.pdf]] ข้อ 3, 4, 5, และ 6 
    * [[http://www.cpe.ku.ac.th/~jtf/204512-53/practices/brother.png|brother.png]]
  * สอบกลางภาควันที่ 26 สิงหาคม 2553 เปิดเอกสารได้
  * ไม่มีการเรียนการสอนในวันที่ 19 สิงหาคม
  * [[http://www.cpe.ku.ac.th/~jtf/204512-53/hw01.pdf|การบ้าน 1]] ส่งภายในวันที่ 5 สิงหาคม 2553
  * ไม่มีการเรียนการสอนในวันที่ 17 และ 24 มิถุนายน
  * สำหรับการเขียนบันทึกคำบรรยาย ดูตัวอย่างจาก[[http://theory.cpe.ku.ac.th/wiki/index.php/204512-50|คำบรรยายเมื่อปีการศึกษา 2550]]  เราสามารถเขียนสมการคณิตศาสตร์ใน Media Wiki ได้ สะดวก กรุณาดูตัวอย่าง

===== การบ้าน =====

  * [[http://www.cpe.ku.ac.th/~jtf/204512-53/hw01.pdf|การบ้าน 1]] ส่งภายในวันที่ 5 สิงหาคม 2553

===== Course Outline =====

  * **Week 1:** บทนำ ตัวอย่างการวิเคราะห์ขั้นตอนวิธี: [[http://theory.cpe.ku.ac.th/wiki/index.php/204512-53/lecture1|บันทึกคำบรรยาย]]
  * 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: [[http://en.wikipedia.org/wiki/Red-black_tree|red-black trees]]
  * **Week 3:** Divide and Conquer.  Recurrences.
    * Red-black trees (cont.)
    * Review, merge sort, quick sort
    * Finding medians in linear time
    * [[http://en.wikipedia.org/wiki/Fast_Fourier_transform|FFT]] and polynomial multiplication
  * **Week 4:** Data structures
    * FFT and polynomial multiplication (cont.)
    * [[http://en.wikipedia.org/wiki/Hash_table|Hashing]]
      * Balls and bins experiments
  * **Week 5:** 
    * Hashing: [[http://en.wikipedia.org/wiki/Universal_hashing|Universal hashing]]
    * Review of [[http://en.wikipedia.org/wiki/Priority_queue|priority queues]]: [[http://en.wikipedia.org/wiki/Heap_%28data_structure%29|heaps]]
    * Randomized [[http://en.wikipedia.org/wiki/Quicksort|Quicksort]]
    * [[http://en.wikipedia.org/wiki/Treap|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

===== Gradings =====

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

===== ลิงก์ =====

  * [[http://compgeom.cs.uiuc.edu/~jeffe/teaching/algorithms/|Algorithms Course Materials]] by [[http://compgeom.cs.uiuc.edu/~jeffe/|Jeff Erickson]]
  * [[http://theory.cpe.ku.ac.th/wiki/index.php/204512-50|รายวิชาเมื่อปีการศึกษา 2550]]