ผลต่างระหว่างรุ่นของ "Ait-aa-2014"
ไปยังการนำทาง
ไปยังการค้นหา
Jittat (คุย | มีส่วนร่วม) |
Jittat (คุย | มีส่วนร่วม) ล (Ait-aa ถูกเปลี่ยนชื่อเป็น Ait-aa-2014) |
||
| (ไม่แสดง 17 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน) | |||
| แถว 3: | แถว 3: | ||
== Announcements == | == Announcements == | ||
* Homework 1 is announced. You should work on this in class during the 1st hour of Jan 17th's class. It is due on Feb 7th. <del>Jan 24th.</del> | * Homework 1 is announced. You should work on this in class during the 1st hour of Jan 17th's class. It is due on Feb 7th. <del>Jan 24th.</del> | ||
| + | * Grading scheme: Midterm-1 25%, Midterm-2 25%, Final 30%, Homework 20%. | ||
== Homework == | == Homework == | ||
| + | Each problem refers to the problem in the 3rd Edition of CLRS. For owners of the 2nd Edition book, most problems remain the same, for those which are different, an equivalent problem in the 2nd Edition is provided in brackets. | ||
* Homework 1: (to start working in class on Friday 17th, due Friday, Feb 7th <del>Friday 31st</del> <del>Friday 24th</del>) | * Homework 1: (to start working in class on Friday 17th, due Friday, Feb 7th <del>Friday 31st</del> <del>Friday 24th</del>) | ||
| − | ** Ch.2: Problems 2-2, 2-3 | + | ** Ch.2: Problems 2-2, 2-3. |
| − | ** Ch.3: Exercises 3.1-1, 3.1-2; Problems 3-1a, 3-1b, 3-2, 3-4 | + | ** Ch.3: Exercises 3.1-1, 3.1-2; Problems 3-1a, 3-1b, 3-2, 3-4. |
| − | * Homework 2: | + | * Homework 2: (announced Jan 30th, due Feb 14th) |
| + | ** Ch.4: Exercises 4.4-1 [4.2-1], 4.4-2 [no eq.], 4.4-9 [4.2-5]; Problems 4-1(a,b,d), 4-3(e,f,j) [4-4(e,f,j)], 4-5 [4-6]. | ||
| + | * Homework 3: (announced Feb 11th, due Feb 28th) | ||
| + | ** Ch.5: Exercises 5.2-3, 5.2-4, 5.2-5; Problem 5-2. | ||
| + | * Homework 4: (announced Apr 9th, due Apr 25th) | ||
| + | ** Ch 8: Problem 8-4 | ||
| + | ** Ch 9: Problem 9-1 | ||
| + | ** Ch 11: Exercise 11.2-1, Problem 11-1 | ||
| + | ** Ch 15: Problems 15-1, 15-4, 15-6 | ||
== Course materials == | == Course materials == | ||
| − | * Week 1: Introduction, insertion sort, asymptotic notations | + | * Week 1 (1/10): Introduction, insertion sort, asymptotic notations |
** YouTube: | ** YouTube: | ||
*** Merge procedure: [http://www.youtube.com/watch?v=hKsbzzY7kts Part 1], [http://www.youtube.com/watch?v=JvnDiQxhRUo Part 2], [http://www.youtube.com/watch?v=d3prchuiNhc Part 3] | *** Merge procedure: [http://www.youtube.com/watch?v=hKsbzzY7kts Part 1], [http://www.youtube.com/watch?v=JvnDiQxhRUo Part 2], [http://www.youtube.com/watch?v=d3prchuiNhc Part 3] | ||
*** Examples for O-notation: [http://www.youtube.com/watch?v=2jERkhCh7Oc Full] | *** Examples for O-notation: [http://www.youtube.com/watch?v=2jERkhCh7Oc Full] | ||
| − | |||
| − | * Week 2: Divide and conquer, recurrences | + | * Week 2 (1/17): Divide and conquer, recurrences |
| + | ** YouTube: Analysis of merge sort: [http://www.youtube.com/watch?v=UItoCEzvAe4 Part 1], [http://www.youtube.com/watch?v=U_S9iBybI6w Part 2] | ||
| + | |||
| + | * Week 3 (1/31): Divide and conquer, continue | ||
** YouTube: | ** YouTube: | ||
*** Integer Multiplication: [http://www.youtube.com/watch?v=uIA4CXVWvXA Part 1], [http://www.youtube.com/watch?v=mbRyDOEDTdk Part 2] | *** Integer Multiplication: [http://www.youtube.com/watch?v=uIA4CXVWvXA Part 1], [http://www.youtube.com/watch?v=mbRyDOEDTdk Part 2] | ||
| − | *** Solving recurrences with the recursion-tree method: [www.youtube.com/watch?v=lYa4RtMpuMs Full] | + | *** Solving recurrences with the recursion-tree method: [http://www.youtube.com/watch?v=lYa4RtMpuMs Full] |
| + | |||
| + | * Week 4 (2/7): Probabilistic analysis | ||
| + | ** YouTube: Probability Theory Review [http://www.youtube.com/watch?v=-i81rnyXydk part 1], [http://www.youtube.com/watch?v=nBJQY-hEGmY part 2] | ||
| + | |||
| + | * Week 5 (2/14): Median and order statistics (9.2, 9.3) | ||
| + | |||
| + | * Week 6 (2/21): Sorting in linear time. (8.1, 8.3, 8.4) | ||
| + | ** YouTube: Lowerbound on comparion-based sorting [http://www.youtube.com/watch?v=cYTZjmB83bE Full] | ||
| + | |||
| + | * Week 7 (2/28): Hash tables (11.1, 11.2, 11.3, 11.4); Dynamic programming (15.1) | ||
| + | |||
| + | * Week 8 (3/28): Dynamic programming (15.2, 15.4) | ||
| + | |||
| + | * Week 9 (4/4): Dynamic programming (15.4 cont), Greedy algorithms (16.1) | ||
| + | |||
| + | * Week 10 (4/11): Greedy algorithms (16.2, 16.3) | ||
| + | |||
| + | * Week 11 (4/18): Amortized analysis (17.1, 17.2, [17.3], 17.4), Data structures for disjoint sets (21.1, 21.2, 21.3) | ||
| + | |||
| + | * Week 12 (4/25): | ||
| + | |||
| + | * Week 13 (4/28): | ||
== Links == | == Links == | ||
* [[Ait-aa-2013|Last year course]] | * [[Ait-aa-2013|Last year course]] | ||
รุ่นแก้ไขปัจจุบันเมื่อ 14:36, 18 มกราคม 2559
This is a homepage for CS304 Advanced Algorithms.
Announcements
- Homework 1 is announced. You should work on this in class during the 1st hour of Jan 17th's class. It is due on Feb 7th.
Jan 24th. - Grading scheme: Midterm-1 25%, Midterm-2 25%, Final 30%, Homework 20%.
Homework
Each problem refers to the problem in the 3rd Edition of CLRS. For owners of the 2nd Edition book, most problems remain the same, for those which are different, an equivalent problem in the 2nd Edition is provided in brackets.
- Homework 1: (to start working in class on Friday 17th, due Friday, Feb 7th
Friday 31stFriday 24th)- Ch.2: Problems 2-2, 2-3.
- Ch.3: Exercises 3.1-1, 3.1-2; Problems 3-1a, 3-1b, 3-2, 3-4.
- Homework 2: (announced Jan 30th, due Feb 14th)
- Ch.4: Exercises 4.4-1 [4.2-1], 4.4-2 [no eq.], 4.4-9 [4.2-5]; Problems 4-1(a,b,d), 4-3(e,f,j) [4-4(e,f,j)], 4-5 [4-6].
- Homework 3: (announced Feb 11th, due Feb 28th)
- Ch.5: Exercises 5.2-3, 5.2-4, 5.2-5; Problem 5-2.
- Homework 4: (announced Apr 9th, due Apr 25th)
- Ch 8: Problem 8-4
- Ch 9: Problem 9-1
- Ch 11: Exercise 11.2-1, Problem 11-1
- Ch 15: Problems 15-1, 15-4, 15-6
Course materials
- Week 1 (1/10): Introduction, insertion sort, asymptotic notations
- Week 3 (1/31): Divide and conquer, continue
- Week 5 (2/14): Median and order statistics (9.2, 9.3)
- Week 6 (2/21): Sorting in linear time. (8.1, 8.3, 8.4)
- YouTube: Lowerbound on comparion-based sorting Full
- Week 7 (2/28): Hash tables (11.1, 11.2, 11.3, 11.4); Dynamic programming (15.1)
- Week 8 (3/28): Dynamic programming (15.2, 15.4)
- Week 9 (4/4): Dynamic programming (15.4 cont), Greedy algorithms (16.1)
- Week 10 (4/11): Greedy algorithms (16.2, 16.3)
- Week 11 (4/18): Amortized analysis (17.1, 17.2, [17.3], 17.4), Data structures for disjoint sets (21.1, 21.2, 21.3)
- Week 12 (4/25):
- Week 13 (4/28):
