Algorithm Design and Analysis
算法设计与分析课程系统讲解常用算法设计方法与复杂度分析技术。核心内容包括分治法、动态规划、贪心算法、回溯法、分支限界法，以及图算法、字符串匹配、近似算法和NP完全性理论。课程注重算法正确性证明与时间空间复杂度分析，培养学生针对实际问题设计高效算法并通过实验验证其性能的能力。
This course systematically covers algorithm design techniques and complexity analysis. Topics include divide and conquer, dynamic programming, greedy algorithms, backtracking, branch and bound, graph algorithms, string matching, approximation algorithms, and NP-completeness. Emphasis is placed on correctness proof and complexity analysis, enabling students to design efficient algorithms and validate performance through experiments.
学生需选取经典动态规划问题（如0-1背包、最长公共子序列、矩阵链乘、编辑距离），实现动态规划解法并与朴素递归、记忆化搜索版本进行性能对比。要求给出状态转移方程推导、复杂度分析及不同输入规模下的运行时间数据。交付物为代码、测试报告及对比分析文档。
Students choose classic dynamic programming problems such as 0-1 knapsack, LCS, matrix chain multiplication, or edit distance, implement DP solutions, and compare them with naive recursion and memoization. Deliverables include code, a test report with state transition equations, complexity analysis, and runtime data across different input sizes.