ผลต่างระหว่างรุ่นของ "Ait-aa-2013"
ไปยังการนำทาง
ไปยังการค้นหา
Jittat (คุย | มีส่วนร่วม) |
Jittat (คุย | มีส่วนร่วม) |
||
แถว 36: | แถว 36: | ||
* Week10: Fibonacci heaps, van Em Bose trees | * Week10: Fibonacci heaps, van Em Bose trees | ||
− | |||
− | * | + | * Week11: Computational geometry |
+ | |||
+ | * Week12: String algorithms | ||
* Week13: NP-completeness I | * Week13: NP-completeness I |
รุ่นแก้ไขเมื่อ 14:52, 7 เมษายน 2556
This is a home page for CS304 Advanced Algorithms.
Homework
- Homework 1 from CLRS: (due 12 Feb 2013)
- Chapter 3: exercise 3.1-1, problems 3-4
- Chapter 4: problems 4-1, 4-5
- Chapter 5: execises 5.2-4, 5.2-5
- Chapter 8: exercises 8.1-2, 8.3-4
- Homework 2 from CLRS:
- Chapter 5: problems 5-1, 5-2
- Chapter 15: exercise 15.4-5, problems 15-1, 15-4, 15-6
Schedules
This is tentative. The actual course schedule will be updated along the way.
- Week1: Introduction, Growth functions, Recurrences and divide-and-conquer (CLRS Chapter 2; Section 4.1)
- Week2: Medians and order statistics, Sorting in linear time (CLRS Section (4.2), 4.3, 4.4, 4.5; Section 9.3, Section 8.1, 8.2, 8.3)
- Week3: Probabilistic analysis (CLRS Chapter 5, Section 7.3; see Appendix C for reviews on probability theory)
- Week4: Probabilistic analysis (cont.) / Dynamic programming I
- Week5: Dynamic programming II
- Week6: Greedy algorithms (CLRS Sections 16.1, 16.2, 16.3), Minimum spanning trees
- Midterm I
- Week7: Hash tables, B-trees
- Week8: Amortized analysis, scapegoat trees (see notes 15 from [1])
- Week9: Data structures for disjoint sets, binomial heaps
- Week10: Fibonacci heaps, van Em Bose trees
- Week11: Computational geometry
- Week12: String algorithms
- Week13: NP-completeness I
- Week14: NP-completeness II
- Week15: Approximation algorithms