MA5007: Algorithm I, Spring 2025

https://www.printables.com/model/287434-physical-traveling-salesman-problem-map/files

Textbook: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2022.

Grading: exam 22% x 3, coding assignment 34%

Coding platform: https://ncuma-oj.math.ncu.edu.tw

Schedule

• Week 01, 02/19 practice 1

  • [Foundation] Syllabus, what is algorithm, big O notation, insertion sort, divide-and-conquer, merge sort

• Week 02, 02/26 End of course selection practice 2

  • Divide-and-conquer, merge sort, Strassen's algorithm, solving recurrences

  • coding assignment: merge sort

• Week 03, 03/05 practice 3

  • [Sorting & order statistics] Heapsort, Quicksort

  • coding assignment: heapsort

• Week 04, 03/12 practice 4

  • Quicksort, sorting in linear time, medians and order statistics

  • coding assignment: count segment intersection

• Week 05, 03/19 practice 5

  • [DP & greedy] Dynamic Programming (DP)

  • coding assignment: Longest Common Subsequence

• Week 06, 03/26 Exam 1

• Week 07, 04/02 No class

• Week 08, 04/09 practice 6

  • Dynamic Programming (DP)

  • coding assignment: printing problem

• Week 09, 04/16 practice 7

  • Greedy algorithms

  • coding assignment: gold mining

• Week 10, 04/23 practice 8

  • Greed algorithms, [Graph algorithms] Breadth Frist Search (BFS)

  • coding assignment: BFS

• Week 11, 04/30 practice 9

  • Deapth First Search (DFS), [Shortest Paths]

  • coding assignment: DFS

• Week 12, 05/07 Exam 2

  • 05/09 students' deadline to drop

• Week 13, 05/14 practice 10

  • Shortest path algorithms: Dijkstra's, Bellman-Ford, DAG

  • coding assignment: Dijkstra's shortest path algorithm

• Week 14, 05/21 practice 11

  • [Minimum spanning tree]

  • coding assignment: MST algorithm

• Week 15, 05/28

  • [NP-completeness]

• Week 16, 06/04 Exam 3

• Week 20, 06/30 Instructor's deadline to upload scores