ผลต่างระหว่างรุ่นของ "Ait-aa"
ไปยังการนำทาง
ไปยังการค้นหา
Jittat (คุย | มีส่วนร่วม) |
Jittat (คุย | มีส่วนร่วม) |
||
แถว 26: | แถว 26: | ||
* Week 3-1 (2/2): Practice on divide and conquer (convex hull problem). Review on probability theory. The hiring problem. The birthday problem. | * Week 3-1 (2/2): Practice on divide and conquer (convex hull problem). Review on probability theory. The hiring problem. The birthday problem. | ||
− | * week 3-2: | + | * week 3-2 (2/4): Balls and bins. Analysis of the heaviest bins. Binomial and geometric random variables. Coupon collector's problem. |
* week 4-1 (9/2 - 1:45 hrs): Randomized quick sort. Comparison-based sorting lower bound. | * week 4-1 (9/2 - 1:45 hrs): Randomized quick sort. Comparison-based sorting lower bound. |
รุ่นแก้ไขเมื่อ 04:34, 17 กุมภาพันธ์ 2559
This is a homepage for CS304 Advanced Algorithms.
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 (due 18 Feb):
- Chapter 2: Problem 2-3.
- Chapter 3: Exercises 3.1-1, 3.1-2; Problems 3-1a, 3-1b, 3-2, 3-4.
- Chapter 4: Exercises 4.4-1 [4.2-1], 4.4-2 [no eq.], 4.4-9 [4.2-5]; Problem 4-5 [4-6].
Course materials
- Week 1-1 (1/19): Introduction, insertion sort, asymptotic notations
- Week 1-2 (1/21): More on big-O and algorithm analysis. Divide and conquer (maximum subarray sum)
- Week 2-1 (1/26 - 1.5 hours): Integer multiplication. Solving recurrences. Master's theorem. Balls and bins.
- Week 3-1 (2/2): Practice on divide and conquer (convex hull problem). Review on probability theory. The hiring problem. The birthday problem.
- week 3-2 (2/4): Balls and bins. Analysis of the heaviest bins. Binomial and geometric random variables. Coupon collector's problem.
- week 4-1 (9/2 - 1:45 hrs): Randomized quick sort. Comparison-based sorting lower bound.
- week 5-1 (16/2 - 1:45 hrs): Linear time sorting algorithms. Intro to selection algorithms.