返回課程列表
[COMP5713]一个TA毁所有
課程時間：2021年S季
授課教授：Siu-Wing
我覺得教授：讲课不错
評分標準：不重要
這門課的Grade：不重要
如果有一门课， 你看到TA是WONG, Man Ting，请立刻考虑跑路。
一学期下来，课上学到不少，课后从作业里我只学会了：
"-1 minor error in 1(a)"
"-1 missing some points"
"-1 explanation not clearly"
"-2"(without any other comment)
换句话说，你并不会知道你哪里有问题，当然很可能是没有问题就是TA想扣分，某巨佬和我说：“只要你写得够多，TA就不怎么扣分。”，注：只是不怎么扣分。
2021/06/07 update:补一下syllabus：
- 2D Convex Hull
- Plane-sweep
- multidimensional range trees
- kd-trees
- arrangement and duality
- planar point location
- Voronoi diagram
- Delaunay triangulation
- 3D Convex hull
- Approximate nearest neighbor search
- Well separated pair decomposition
- Approximate shortest path
- Minimum enclosing ball
- Frank-Wolfe greedy approximation
- Distribution-sensitive point location
- Self-improving algorithm
个人感觉课程速度略微有点快，一个topic 1~2节课讲完，经常走个神就跟不上了，所以前几周之后就基本上是看recording了。
[COMP5713]横看成岭侧成峰，远近高低各不同
课程时间：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所以本文并不一定具有参考性，这点请注意。
