204313 Analysis and design of algorithms


ผู้สอน: จิตร์ทัศน์ ฝักเจริญผล
ผู้ช่วยสอน: TBA
หมู่ 1: จ. 9:00-10:30 พฤ. 9:00-10:30 ห้อง E202

เวลาเข้าพบ: TBA
email: jtf@ku.ac.th


ประกาศ

รายละเอียด

วิชานี้มุ่งหวังให้นิสิตมีพื้นฐานในการออกแบบและวิเคราะห์อัลกอริทึมในเชิงคณิตศาสตร์. อัลกอริทึมที่เน้นในวิชานี้จะเป็นอัลกอริทึมที่สามารถวิเคราะห์ได้อย่างชัดเจนเท่านั้น (นั่นคือจะไม่รวมอัลกอริทึมที่เป็น heuristic ต่างๆ เช่น genetic algorithms หรือ neural networks).

เนื้อหา. Basic of algorithm analysis. Algorithms on graphs. Greedy algorithms. Divide and conquer. Dynamic programming. Network flows. NP and Computational Intractability. Approximation algorithms. Local search. Randomized algorithms.

ประกาศวิชา (.pdf) (.ps)


หนังสือประกอบ: Kleinberg and Tardos. Algorithm Design. Addison Wesley. 2005.

การบ้าน

การบ้านที่ให้แต่ละชุดมีกำหนดส่งภายเวลา 9 น. ของวันอังคารถัดจากอาทิตย์ที่ให้. โดยประมาณเราจะมีการบ้านทั้งสิ้น 12-13 ชุด. ในการคิดคะแนน เราจะตัดการบ้านครั้งที่นิสิตได้คะแนนน้อยที่สุดออก. ในการทำการบ้านนั้น นักเรียนสามารถทำงานเป็นกลุ่มได้ แต่ในการเขียนส่งนั้น นักเรียนแต่ละคนต้องเขียนด้วยตัวเอง พร้อมทั้งระบุชื่อของเพื่อนที่ร่วมทำการบ้านด้วยกันด้วย.

ตารางเรียน

ตารางนี้อาจเปลี่ยนแปลงได้
CH DATE TOPICSREADING NOTES
CH.1 1.M6/6 Intro. Stable matching 1.1
CH.2 1.W8/6 Problem examples. Asymtotic order of growth. 1.2, 2.1, 2.2
2.M13/6 Algorithm implementation 2.3, 2.4
2.W15/6 Data structure: priority queues 2.5
CH.3 3.M20/6 Graphs. Graph connectivity and graph travelsal Implementing DFS and BFS with stacks and queues. 3.1, 3.2, 3.3
3.W22/6 Testing bipartiteness. Strong connectivity. 3.4, 3.5
4.M27/6 Directed acyclic graphs, topological ordering 3.6
CH.4 4.W29/6 Interval scheduling 4.1
5.M4/7 Scheduling to minimize lateness. Shortest paths 4.2, 4.4
5.W6/7 Minimum spanning trees. 4.5
MIDTERM I
6.M11/7 Union-Find data structures 4.6
CH.5 6.W13/7 Divide and conquer: Merge sort. Recurrence relations 5.1, 5.2
7.M18/7 Counting Inversions. 5.3
7.W20/7 Closet pair of points 5.4
CH.6 8.M25/7 Weighted Interval scheduling: Memoization 6.1
No class (MIDTERM WEEK)
8.M8/8 Weighter Interval scheduling: Iterative. Segmented Least squares. 6.2, 6.3
8.W10/8 Subset sum. sequence alignment 6.4, 6.6
9.M15/8 Shortest paths using dynamic programming. 6.8, 6.9
CH.7 9.W17/8 Network flows 7.1, 7.2
10.M22/8 Network flows: Edmond-Karp. Applications 7.3, 7.5
10.W24/8 More network flow applications 7.7, 7.8, 7.9, 7.10, 7.12
MIDTERM II
CH.8 11.M29/8 Polynomial-time reduction. Gadget 8.1, 8.2
11.W31/8 NP Completeness. 8.3, 8.4
12.M5/9 NP Complete problems 8.5-8.8
CH.9 12.W7/9 PSPACE 9.1-9.3
CH.11 13.M12/9 Bounds on the optimum. 11.1, 11.2
13.W14/9 Set cover 11.3, 11.6
CH.12 14.W19/9 Local search 12.1-12.3
CH.13 14.W21/9 Contension resolution 13.1
15.M26/9 Global mincut. Random variables and expectations. 13.2, 13.3
15.W28/9 MaxSAT. Randomized divide and conquer 13.4, 13.5
FINAL

เอกสารเพิ่มเติม