这学期选修了卜老师的算法课，都说这课是神课，上过之后果然是神课。同样是算法课，别人12月底就考完了，我们要1月底才考试。

本课程主要讲了以下几个专题：

• Divide-and-conquer
• Dynamic programming
• Greedy
• Linear programming
• Linear programming: duality
• Network flow
• Problem hardness: Polynomial-time reduction
• NP-Completeness
• Approximation algorithm

前三个专题的算法大多数本科时学过的，但是经卜老师讲一遍还会有新的收获。后六个专题接触较少，学到了很多新算法。

下图是卜老师每节课必讲的问题求解思路图：

（待我回家把图画出来...）

本课程最神的要数课后作业了，一般deadline是周五，每到周四晚上，大家都做好熬通宵赶作业的准备，没熬到两三点都不好意思睡觉，我同学有一次甚至熬到了第二天六点！

每次作业大概有10题，前7题是算法设计，后3题是算法实现，每题都不是省油的灯，不过如果把每道题都理解消化，算法及编程能力会有很大的提高。

下面是我整理出来的算法题目和个人解答，大家感受一下。（仅供完成作业之后交流使用，拒绝抄袭！）

• Assignment1_DandC.zip
• A1sol.pdf   |  A1sol.tex
• A1sol_supplement.pdf   |   A1sol_supplement.tex_.zip
• Assignment2_DP.zip
• A2sol.pdf   |   A2sol.tex_.zip
• A2sol_supplement.pdf   |   A2sol_supplement.tex
• Assignment3_Greedy.zip
• A3sol.pdf  |  A3sol.tex_.zip
• A3sol_supplement.pdf  |   A3sol_supplement.tex
• Assignment4_LP.zip
• A4sol.pdf   |   A4sol.tex
• A4sol_supplement.pdf   |   A4sol_supplement.tex
• Assignment5_NF.zip
• A5sol.pdf   |   A5sol.tex
• A5sol_supplement.pdf   |   A5sol_supplement.tex
• Assignment6_NP.pdf
• A6sol.pdf   |   A6sol.tex
• Assignment7_App.pdf
• A7sol.pdf   |   A7sol.tex