横看成岭侧成峰，远近高低各不同
課程：COMP5713
作者：stanab [12级 CSE]
創建於：2014-06-05 01:24:49
課程：COMP5713
作者：stanab [12级 CSE]
創建於：2014-06-05 01:24:49
课程时间：2014年秋季
授课教授：Timothy M. Chan
这门课的Grade：Grade较好
在介绍这门课之前，请允许我先讲述一下这门课的教授。Timothy Chan是一位从University of Waterloo来的客座教授，一个最能说明其强大之处的就是，他有Wikipedia的页面...(http://en.wikipedia.org/wiki/Timothy_M._Chan)，从中我摘录以下这段最令我感到震惊与惊奇之处：He graduated with BA (summa cum laude) from Rice University in 1992, and completed his Ph.D. in Computer Science at UBC in 1995 at the age of 19.
在这里，我似乎看到了我虚度光阴的过去。Computational Geometry是这位教授的主要方向，但他也在很多其他field里做出了很多贡献，这个学期刚开始时，CS department就有一次Theory Seminar是由他介绍他及他同事刚刚做出的Restore Model上的Sorting和Median Finding。一言以蔽之，教授是一位大神级人物。
课上也处处显出了这样一位大神级人物的风采，由于计算几何是这位教授的老本行，这个领域里很多最好的结果都是由他做出的。最出名的大概是2D凸包算法里的Chan's Algorithm(没错，就是以他名字命名的)，这里插一个轶事，其实这个算法是他写PhD paper时提出的，本来他要研究4D空间里的凸包，决定先看看2D里是什么情况，就不小心发明了这个Algorithm。很多次他介绍某些算法目前的最好成果，到最后时总羞赧地一笑，略带羞涩地告诉我们最好的结果是他做出来的。
这位教授停留在科大的时间是2014 sprint&2014 fall。如果有幸能上他的课，我还是十分推荐的。
接下来言归正传谈一谈Computational Geometry。这是为数不多的科大CS系的Theory课程，主要介绍这个field里一些非常经典的算法。从凸多边形上的Binary Search，到经典的凸包算法，接着会讲一讲Voronoi Diagram，Linear Programming，最后讲一讲Point-Location。教授非常善于用过去已经用到的一些算法来解决一些新问题，所以讲到Voronoi Diagram时，并没有深入介绍Fortune's Algorithm这样专门解决VD的算法，而是将VD归约成以前已经被我们解决的凸包问题，令人耳目一新。又如，在讲到凸包时，将Jarvis March和Graham Scan巧妙地结合在一起，从而得到一个更好的Output Sensitive的算法(即Chan's Algorithm)，十分具有启发心智的效果。在上这门课之前，我接触的大部分是Deterministic的算法，对Randomized的算法并不怎么了解，通过这门课，我深深地感受到了随机化的强大，仅仅是简单地随机打乱输入，就可以以非常快的期望复杂度解决一个复杂的问题。对于同一个问题，教授会花几节课介绍很多很多不同的算法，涉及了很多不同的way of thinking。我感觉，这门课的意义不单单是介绍Computational Geometry，还在于介绍Theory常用的一些工具(e.g. epsilon-net, fractional cascading)。对于以后要走CS纯Theory的童鞋相信有很大的启发意义。
作业有一些Challenging，不过都是可做的，Midterm比Final出的略难一些，有些题会有让人Aha的感觉。
由于是PG课，龟自然是极好的。
以后应该还会变回郑绍荣版的COMP5713所以本文并不一定具有参考性，这点请注意。
Comments
Write a comment
請登錄後再評論
請登錄後再評論
