卜神算法作业整理
这学期选修了卜老师的算法课，都说这课是神课，上过之后果然是神课。同样是算法课，别人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