Algorithms: Design and Analysis, Part 2[Week 5-6]

本课第5、第6周：

January 14-20 Topics P, NP, and What They Mean Reductions Between Problems NP-Complete Problems The P vs. NP Problem Solvable Special Cases of NP-Complete Problems Smarter (But Still Exponential-Time) Search Algorithms for NP-Complete Problems	Homework Due January 27 Problem Set #5: NP-Complete Problems and Smarter Search Algorithms for Them Programming Assignment #5: The Traveling Salesman Problem	Suggested Readings: CLRS Chapter 34 DPV Section 8.1, 8.2, 9.1 KT Sections 8.1-8.4, 8.10, 10.1, 10.2
January 21-27 Topics Heuristics with Provable Guarantees Local Search	Homework Due Februrary 3 Problem Set #6: TBA Programming Assignment #6: TBA	Suggested Readings: TBA

PA5，算法基本按slide上的写的，基本没有什么优化，跑了一个小时。。。

你好 ，我最近做公开课algo2 的pa4 和 pa5 ，出现瓶颈 ，尤其是pa4 一直过不了，可以发你的代码给我看下么？谢谢了。
或者邮件联系 ，我的 邮箱 fuxiang90@gmail.com

fuxiang90 发表于 2013-1-25 01:27
你好 ，我最近做公开课algo2 的pa4 和 pa5 ，出现瓶颈 ，尤其是pa4 一直过不了，可以发你的代码给我看下么？ ...

PA4的算法不难编，如果是运行速度的问题，可以尝试下用矩阵向量化处理，比array快几十倍。
比如在Python中使用numpy的矩阵，或者用matlab。
或者你可以把你觉得有问题的那部分代码贴上来。

P.A. 5没有优化…我的电脑关掉了交换分区，故内存不够，放到学校的机器上提交了个pbs job运行了57分钟才完成

还是超过DEADLINE了… 555

觉得就运行时间而言，4和5一下难度就变大了，最Naive的解法想要照顾速度的话都得用c++，如果用Python的话就得加上一些很fancy的优化。

cs900601 发表于 2013-1-28 11:13
P.A. 5没有优化…我的电脑关掉了交换分区，故内存不够，放到学校的机器上提交了个pbs job运行了57分钟才完成 ...

对的。Python的话可以用numpy作向量化。速度是array的20多倍。

默默上最后一个PA的结果，刷存在感
苦战了一天（苦战是因为效率不高，毕竟今天是Deadline，紧张嘛），提交了3次才过
用西加加写的转成SCC的解法（毕竟是O(N)时间嘛），速度还行吧！ 8秒钟计算出了最后一个输入。
有点小悲剧的是我在上Algo class 1时编的SCC那个作业少了个头文件，不能运行了。所以就重新写了一个SCC。
对比半年前的Code，我觉得我现在写的Code比较好看，而且还学会用STL容器了。
有一个Bug捉了一个下午没捉出来，然后出去跑了个步，重新想问题在哪里，结果就想出来了。
那个问答留言板上的人真是各种牛逼，Haskell、OCaml、F#之类只听过名字的语言和某些连名字都没听过的语言都出来了。真是大Hacker啊。以后如果去谷歌之类的地方工作，身边或许都是那种人吧…还是要加油啊。

cs900601 发表于 2013-2-3 20:41
默默上最后一个PA的结果，刷存在感
苦战了一天（苦战是因为效率不高，毕竟今天是Deadline，紧张嘛），提交 ...

Haskell、OCaml、F# 这些全都是函数式编程语言，我最近在跟Programming Languages，稍有涉及。Coursera上还有专门教函数式语言的，是Scala的创始人讲课。
其实没听说过的语言未必牛，基本概念搞清楚了，学新语言的语法还是很快的。
我记得你之前上计算机图形学的吧，很厉害啊。

!!!!!!!!!!!!!!!!!!!!