ผลต่างระหว่างรุ่นของ "Ait-aa"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
 
(ไม่แสดง 24 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน)
แถว 1: แถว 1:
 
This is a homepage for '''CS304 Advanced Algorithms'''.
 
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].
 +
 +
* Homework 2 (due 14 Apr):
 +
** Chapter 17: Exercise 17.1-3, 17.2-1, 17.2-2
 +
** Chapter 15: Problems 15-1, 15-4, 15-6
 +
 +
* Homework 3 (due 21 Apr):
 +
** Chapter 5: Exercises 5.2-3, 5.2-4, 5.2-5; Problem 5-2
 +
** Chapter 8: Problem 8-4
 +
** Chapter 9: Problem 9-1
 +
 +
* Homework 4
 +
** Chapter 16: Exercise 16.1-2, 16.1-4
 +
** Chapter 22: Exercise 22.3-2
 +
** Chapter 23: Exercise 23.1-1, 23.1-5
 +
** Chapter 34: Exercise 34.1-4, 34.2-6, 34.5-1; Problems 34-1(a), 34-1(b)
 +
 +
== Course materials ==
 +
 +
* Week 1-1 (1/19): Introduction, insertion sort, asymptotic notations
 +
** 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]
 +
*** Examples for O-notation: [http://www.youtube.com/watch?v=2jERkhCh7Oc Full]
 +
 +
* Week 1-2 (1/21): More on big-O and algorithm analysis.  Divide and conquer (maximum subarray sum)
 +
** YouTube:
 +
*** Analysis of merge sort: [http://www.youtube.com/watch?v=UItoCEzvAe4 Part 1], [http://www.youtube.com/watch?v=U_S9iBybI6w 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: [http://www.youtube.com/watch?v=lYa4RtMpuMs Full]
 +
 +
* Week 2-1 (1/26 - 1:30 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.
 +
 +
* week 5-2 (18/2 - 1:30 hrs): Worst-case quick selection algorithm.  Randomized selection algorithm.  Intro to AVL trees.
 +
 +
* week 6-1 (23/2): AVL trees.  Amortized analysis: lazy deletions, dynamic tables, multi-level sorted arrays.
 +
 +
* week 7-1 (8/3): Potential methods. Splay trees.  Scapegoat trees.
 +
 +
* week 8-1 (15/3): Dynamic programming 1: Introduction, Rod cutting, Longest increasing subsequence
 +
 +
* week 8-2 (17/3): Dynamic programming 2: Matrix chain multiplication, Longest common substring
 +
 +
* week 9-1 (31/3 - 3 hrs): Dynamic programming 3: Review, Edit distance, Knapsack
 +
 +
* week 10-1 (7/4 - 3 hrs): Greedy algorithms (activity selection, Huffman codes)
 +
 +
* week 11-1 (12/4): Basic graph algorithms (graph search, DFS, BFS)
 +
 +
* week 12-1 (19/4): Minimum spanning trees, shortest paths
 +
 +
* week 12-2 (21/4): NP-completeness 1
 +
 +
* week 13-1 (25/4 - 3 hrs): NP-completeness 2.  Additional data structures (Hashing, B-trees, Fibonacci heaps, van Em Bose trees)
  
 
== Links ==
 
== Links ==
−
* Old home pages for [[ait-aa-2014|2014]] and [[ait-aa-2013]]
+
* Old home pages for [[ait-aa-2014|2014]] and [[ait-aa-2013|2013]]

รุ่นแก้ไขปัจจุบันเมื่อ 18:41, 24 เมษายน 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].
  • Homework 2 (due 14 Apr):
    • Chapter 17: Exercise 17.1-3, 17.2-1, 17.2-2
    • Chapter 15: Problems 15-1, 15-4, 15-6
  • Homework 3 (due 21 Apr):
    • Chapter 5: Exercises 5.2-3, 5.2-4, 5.2-5; Problem 5-2
    • Chapter 8: Problem 8-4
    • Chapter 9: Problem 9-1
  • Homework 4
    • Chapter 16: Exercise 16.1-2, 16.1-4
    • Chapter 22: Exercise 22.3-2
    • Chapter 23: Exercise 23.1-1, 23.1-5
    • Chapter 34: Exercise 34.1-4, 34.2-6, 34.5-1; Problems 34-1(a), 34-1(b)

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)
    • YouTube:
  • Week 2-1 (1/26 - 1:30 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.
  • week 5-2 (18/2 - 1:30 hrs): Worst-case quick selection algorithm. Randomized selection algorithm. Intro to AVL trees.
  • week 6-1 (23/2): AVL trees. Amortized analysis: lazy deletions, dynamic tables, multi-level sorted arrays.
  • week 7-1 (8/3): Potential methods. Splay trees. Scapegoat trees.
  • week 8-1 (15/3): Dynamic programming 1: Introduction, Rod cutting, Longest increasing subsequence
  • week 8-2 (17/3): Dynamic programming 2: Matrix chain multiplication, Longest common substring
  • week 9-1 (31/3 - 3 hrs): Dynamic programming 3: Review, Edit distance, Knapsack
  • week 10-1 (7/4 - 3 hrs): Greedy algorithms (activity selection, Huffman codes)
  • week 11-1 (12/4): Basic graph algorithms (graph search, DFS, BFS)
  • week 12-1 (19/4): Minimum spanning trees, shortest paths
  • week 12-2 (21/4): NP-completeness 1
  • week 13-1 (25/4 - 3 hrs): NP-completeness 2. Additional data structures (Hashing, B-trees, Fibonacci heaps, van Em Bose trees)

Links

ดึงข้อมูลจาก "http://158.108.32.49/wiki/index.php?title=Ait-aa&oldid=56673"