Browsed by
Category: 算法

练习7-1Edit distance的心得体会

练习7-1Edit distance的心得体会

花了总共6个小时,最后还是没有给出正确的解答。然而俗话说得好,失败乃成功它娘,虽然这次失败了,还是有些收获的: 进行编程之前,要把算法推导无误之后再进行,虽然在当下我的确认为自己是正确的方法,可是最后才发现是不对的。在纸上推导可能花的时间要比实际编程少得多,所以一定要确认之后再编程。 C语言这种高级语言中的低级语言,给自己的自由度很大,同时也意味着,它没有诸如c++、java、Python等语言完善的配备,很多东西都得自己写,这样会花费不少时间在制作车轮;然而,我觉得这个是值得的,一来可以使自己熟悉C语言,毕竟工作后就用得少,二来程序可以直接用gcc输出汇编代码,可以对比学习,更加了解编译后的输出。 最后总结下这道题做错的原因。题目用动态规划来解答,可是我想当然的认为从顶到下的解决问题,我认为第一个最优化解会构成第二个最优化解,以此类推,最终解决出最优化的方案,正因为如此,在最后程序完成后,发现,如果第一个解不是最优化的,那么,后面的解都不是,最终得出错误的解答。而正确的应该是至底向上的,最后一个字母+上一个最优化解,构成最优化解答。

MIT – SMA5503 – Introduction to Algorithms 小提示

MIT – SMA5503 – Introduction to Algorithms 小提示

刚才突然想到的,给同看这个视频的同学一点小提示。 这个系列会有很多的assignment,每个都很有意思,问题就是很难,如果你苦心去想每一个problem,会花很多时间,而且可能也想不到。这就让我想起一开始看schedule的时候,发现每个assignment后面都有out、due两个状态,当时想,不过就是due比较重要,out似乎没什么用。刚才突然想到,out也很重要,这个作业布置的时候,也许你还没有看到相应的章节,但是没有关系,你这个时候就应该先看看作业,让作业在你脑海中有个印象,接下来在学习的过程,你再慢慢思考,而不是等章节都学习完毕之后,再一口气想。

阶段总结–目前学习的进度

阶段总结–目前学习的进度

按部就班的学习,目前的进度已经过半,也该是进行阶段总结的时候了。前面没有写blog,记录下每次的进度,如果以后有时间再补充上。 废话不多说了,总结目前的进度: 算法分析的方法 代换法 Substitution Method 递归树 Recursion-tree Method 主方法 Master Method 算法的重要思想—分治法 矩阵乘法Strassen算法 斐波那契 Fibonacci 排序 插入排序 Insertion Sort 合并式排序 Merge Sort 堆排序 Heapsort 快速排序 Quicksort 随机快速排序 Randomized Quicksort 优先级队列 Priority Queues 计数排序 Counting Sort 基数排序 Radix Sort 桶排序 Bucketsort 中位数 基于快速排序的Randomized select Selection in worst-case linear time 哈希表 直接寻址表 散列函数 除法散列 乘法散列 全域散列 开放寻址法 Open addressing 完全散列 Perfect Hashing 树 二叉查找树 Binary Search Trees 红黑树 Red-black Trees B树 B-trees Treaps 区间树 Interval Trees 扩展数据结构 Augmenting Data Structures 顺序统计树…

Read More Read More

站在十字路口上

站在十字路口上

当前阅读中遇到了一些困难,其中最为明显的就是在算法的分析部分。这里面包括的难点是: 一些已经基本遗忘的初等数学知识 高等数学知识 概率论的知识 虽然说CLRS中附录部分有提及补充相关知识的章节。可是,还是有一些问题不明白。之所以这篇文章的标题叫站在十字路口上,是因为,就CLRS的进度来说,已经过半,可是现在如果跳开教材,而转而阅读别的相关补充基础知识的书籍,就会影响看教材的进度。思来想去还是决定继续完成CLRS,回头有空再看这方面的书。 据说The Art of Computer Programming里面会有补充这方面知识的章节,我决定有空的时候再看看Donald E. Knuth的经典著作。 P.S. Knuth的巨著实在太贵了,只能看电子版了,之前曾经找到一个PDF版的,不仅文件个头大(>50M),而且是扫描版的,不清楚。这次找到了一个djvu版本的,个头小,里面内容是电子的。赞一个~ 推荐一下到http://windjview.sourceforge.net/下载最新版阅读器来阅读djvu文件(好绕口)。

算法学习-开篇

算法学习-开篇

本来打算在系统学习完成之后才开始更新这个系列的文章的,今天回过头在看看上次写heap sort的代码,才发现似乎有点陌生了。也就是说,很可能我今后回头再写的时候,可能会忘记当时的一些要点。所以,还是决定,边学习边写心得了。 因为live spaces要移除所有的用户,所以我不得不把文章放在这个站上。无奈的穷人,等我以后有钱了,再把站点迁移到合适的空间吧,暂时这个空间也没有别的内容,就放在这里吧,起码这里的速度比上wordpress.com还是要快的。