[Coursera] Standford Algorithm Design & Analysis II

Coursera上的Stanford算法设计与分析（下）已经开课一星期了。不知道跟着学的版友们多不多。我来试着开一贴。

第一周：

Topics
- Two Motivating Applications (Sequence Alignment and Internet Routing)
- Selected Review from Part I (Optional)
- Introduction to Greedy Algorithms
- A Scheduling Application
- Prim's Minimum Spanning Tree Algorithm

Homework
- Due December 16
- Problem Set #1: Greedy algorithms and MSTs
- Programming Assignment #1: Greedy scheduling and Prim's MST algorithm

m4reiiy编辑：请大家不要随便贴code，如果想求学分可以像2L一样给PA的得分截图，谢谢！
请参见置顶贴
请注意公开课的Honor Code，不要随意share code

开始的晚，好歹把第一周的赶上了。。申请完了只想玩游戏 - -

这作业是真心难啊，做了三次才对了四个。还好意思说自己是科班出身。。

截屏求学分是这样么，

@m4reiiy ，problem set 真心不好做。。programming 照着算法来就是了，有工作量但是没太大难度。这些选择题都是证明正确性的，第2题现在还没搞懂。。

programming 截图

贴下我代码吧，刚开始用ruby，不够地道，

第一题和第二题
【删】
第三题。找不到好用的heap实现，就先用数组了。那个algorithms的gem搞不懂怎么用的，有空照python的写个。、
【删】
在公开课的论坛里有测试数据，可以先验证下代码对不对。

【编辑：貌似是不能把代码块搞成白色的？只好把code去掉了。】
【编辑-2：把代码删了】

不好意思，Code删除了

饿，那个什么，coursera好像说不要贴出code....

把两次的作业放一块好了。。。
PA1：

PA2：

小K 发表于 2012-12-16 08:02
饿，那个什么，coursera好像说不要贴出code....

好嘞～那我把代码删了。之前是看说可以设成白色的。

自己查错的过程也算是学习吧，第三题我本来死活搞不过了，用CLRS上的数据测试也没问题。后来想找别人的代码看看 - -，幸亏在那之前就找到了一份测试数据，然后改对了 ;)

PA3，这周的。第二个大数据的速度感觉不太行，用C++写跑了14s。

第二题我做了好多遍，因为我一开始想，只要计算长为0、1、2的边的条数，然后再用总的结点数减去它就对了。
但是与答案亦有偏差，现在还在想为什么。
后来做出正确答案是用了一种稍微有些变化的方法做的。
－－－－－
我发觉python比c++要适合做这些作业，因为我对这些算法了解不够，而这个算法课的侧重点是算法设计的思路，而非低层的优化（对比之下，像ray tracer就不适合python做。）

再求学分 赶在deadline之前做完第二周的。。

第二题真纠结。ruby，跑了38s。我以为有很简洁的数学办法呢，看论坛上的优化方法也挺暴力的。

话说别的公开课好像都是一周一帖啊。。

=====

稍微改了下，时间变12s了。忘了整数可以直接用位运算来修改某一位。。