CourseInfo

2016 Spring Semester 演算法概論 Introduction to Algorithms course syllabus @ National Chiao Tung University, Hsinchu, Taiwan, R.O.C

• Instructor: 陳健 Chien Chen
• Office hours: Thuesday 1:30 - 3:30PM @ EC125B
• email: [email protected]
• Prerequisite: Programming & Data Structure
• Course descriptions and objectives: This course introduces students to the analysis and design of computer algorithms.
• Text book: Introduction to Algorithms, 3rd Ed, the MIT Press, by Cormen, Leiserson, Rivest and Stein.
• Current course No.: 1198
• Permanent course No.: DCP3573
• Credits: 3
• Required/Elective: Required

Topics:

1. Introduction to analysis of algorithms
2. Asymtotic notation
3. divide and conquer
4. Recurrences, summations
5. Randomized quicksort
6. Median, order statistics
7. Sorting in linear time
8. Hash
9. Red-Black tree
10. Dynamic Programming
11. Greedy algorithms
12. Minimum spanning tree
13. Graph algorithms: depth-first search, topological sorting, breadth-first search
14. Graph algorithms: Single-source shortest paths, Dijkstra's algorithm
15. Bellman-Ford algorithm, dag shortest paths
16. All-pairs shortest paths, Floyd-Warshall algorithm
17. Network flow
18. Introduction to NP-completeness

Homework and Assignments:

• 4 - 6 Homework
• 3 - 5 Programming assignments

Exams and Quizzes:

• 2 quizzes
• 1 midterm
• 1 Final

Grading Policy:

• Homework assignment (10%)
• Programming assignment (25%)
• Quiz (20%);
• Mid-term (20%)
• Final exam (25%)
• Class participation (+/-)