返回課程列表
[COMP5712]上课好评 考试拉跨
課程時間：2021年S季
授課教授：Sunil Arya
我覺得教授：上课好评
評分標準：assignment 20% + midterm 35% + final 45%
這門課的Grade：較好/一般
思来想去感觉自己的烂龟好像不太配评价这门课，各位就当看个笑话好了。
内容就是基于linear programming讲了一些经典的NP-hard/complete问题的近似解，参考了Stanford cs261的notes（不是tim roughgarden那版，并删去了和LP不太相关的内容），加上从Williamson&Shmoys选的几节内容。难度从一开始的很简单慢慢增加，不过到最后也不算难，把notation和想法搞清也比较简单。
考试今年sunil应该是放了大水（可能是因为online），比past paper简单了很多，然而我忘记了两年前Sunil是如何在2711H上扣爆我过程分的，本以为都pg课了，写随意一点也无所谓，于是midterm和final考完都觉得自己稳了，一出分发现GG了。所以如果这课考得很简单的话，得好好写过程，尤其是“you can use any fact discussed in lecture"，这个的意思并不是允许你可以直接assume课上内容可以不写，直接写和课上不同的部分……
给龟方面应该还行，但是这课Sunil只管最后划A/B range，至于评分标准、appeal都是TA定，所以就……感觉扣分还是挺狠的，也基本不能appeal。
推荐对算法（不是指那个算法）有兴趣的同学一上，或者对博弈论有兴趣的也可以听一听，毕竟Nash equilibrium就是LP+一些奇奇怪怪的分析。
[COMP5712]默而识之
課程時間：2017年Spring季
授課教授：
我覺得教授还是蛮好的
這門課的Grade：和其他PG课一样的
如题。概括了这门课的精髓。
然而这个复制粘贴有点奇怪不想改了。
找不到syllabus在哪里了。凭印象回忆一下这门课的内容：
1. 简单复习P和NP。
2. 用一个月的时间DFS一棵minimum spanning tree
3. 用一个月的时间讲各种Linear programming应用到算法的例子。然而由于这部分没什么好讲的，所以不会给你一个overview或者让你考虑一下，（1）这是怎么想到的，（2）这有什么用，（3）他们彼此之间有什么区别。给你个眼神自己体会。
4. 讲讲semi-definite 和 vector programming。不过放心这个好像是太难了（设计这种考题太烦了）所以即使不太会能记住个形式，考试可以混一混。
虽然Arya口音稍微有点重，不得不说他上课还是挺认真的。总是尽力在把一个算法讲透，加上一些生动的例子。这些例子有一部分的确很生动，有一部分不算生动，听起来有点难受，这个时候我就想找左右聊聊天，当然是聊跟现在讲的东西有关的内容，然而左右都是聚精会神记笔记，让我不忍心打扰。
后来才发现笔记是这个课的精髓。因为考试的时候，内容是绝对不会超出（1）笔记（2）作业题目换一个数（3）Arya自己认为自己（可能是在3711？）讲的比较好的内容。比如：
State Konig’s theorem （？）就是说二分图的maximum matching和minimum vertex cover size是一样的。我考了midterm才知道这原来是个theorem。上课的时候我听到这个了，想一下是这么回事就没记在notes里。然而我太懒记下来也不会写是什么名字的。令我吃惊的是这么难的题居然大家都能写出来，好像我就知道我和一个小伙伴不会。果然是藏龙卧虎。
据说Arya考midterm的时候上午开始出题晚上考试。期末估计多不了多少时间吧。但是final题目至少作出改变力求抬我们一手：期中是看不懂这题有什么好问的。期末至少看上去还是那么回事。不过final的一个教训是问他clarify的时候要举个例子，否则他虽然也明白了你要问什么 其实他不明白。
总体来说这课不算难，但是就是有点难受；Arya人比较nice，只是喜欢把你问他的问题的emailCC全体让大家知道你勤学好问这一点我不是特别理解，但是这也体现他有求必应了。考试嘛不能太当真，大家上课疯狂记笔记是有道理的。如果没记其实也没事，想想这课疯狂记笔记的场面，大概就知道考试是什么套路了。
P.S. 我明白为什么大家都喜欢用PG课去count elective了，因为龟真的迷之好。UG课还要担心会不会遇到明星选手老王者，PG课多好，给成绩很宽松，写在成绩单上还显得很advanced。我之前居然还嫌某PG课和某大家极力吹捧的PG课无聊drop了两次。感觉白放了两个至少是A走，真的是太年轻了。后面的朋友们为了多探索自己的interest（为了自己的前shen途qing着想）一定多去上PG课啊。
[COMP5712]approximate一个人生最优解-tan90
課程時間：2017 Spring
授課教授：Sunil Arya
我覺得教授: 人很好教得还行
這門課的Grade：Grade神/較好
【感想】闲的没事来写一发cwiki, 顺便介绍这门课, 之前有某阿姨写过,毕竟大一就上的巨巨, 对于巨巨们来说有一定的参考性0-0....像我这个之后才学算法的人估计这时候有另外一种参考性
【介绍】这大概是PG要修的theory部分的一门核心课，讲的是approximation algorithm。 主要内容包括（让我loading一下）:...
1. (metric) Steiner Tree and Travelling sales man(TSP)
2. Linear Programming and Duality
3. Weighted Vertex Cover: Deterministic Rounding and Primal-Dual Algorithm
4. Algorithms for Set Cover
5. Max Flow, algorithms and liner
6. Algorithms in Bipartite Graphs
7. Steiner Forest
8. Multiway cut problem (哇这一章我是真没学懂那几个算法...复习到最后还是一脸懵逼
9. max cut
10. max-sat, max-2sat, well-characterized problems and vector programming...
大概的内容就是对于一些NP-Hard, NP-Complete的问题找不到exact的polynomial的解的时候，采取了“一般人”很难在一时想出来的“奇技淫巧”去得到approximate的算法，让大家可以在polynomial的时间内得到最优解。
大概的思想呢，大概就是告诉你 有很多的情况下我们是找不到最优解的 但是你要知道我们不要死磕 我们可以换个思路去近似一个最优解（...um...我是这么理解的
我觉得课程本身挺有意思的，对于我这种启蒙渣大概就是好像看上去我是学懂了qwq 对 大概就是这种思想qwq 利用这种技巧qwq 但是一个回头QAQ 他当时是怎么想出来的QAQ 想出来之后为什么这么证明QAQ 这种证明为什么是正确的...我是一脸懵逼的???? 当然 对于知识当然要抱以不求甚解的态度...但是我也是意识到 在一定时间内智力是有局限的...所以弄不懂也没办法 但是我们要产出不是...掌握了这种思想就好了不是( 强行自我安慰一波
【教授授课】
上过3711或者3711h的人应该或多或少上过sunil的课( 我没上过... sunil喜欢板书 然后我就在下面写写抄抄日后复习 当然我也见过大神不计笔记... 各有各的好没有优劣 自己看着办好了 他说的东西我抄完发现 哇 看不懂了 很伤 所以就去看reference【如下各课本】相对应的部分 看了之后发现 sunil是把对应notes的部分自己理解之后表达出来方便大家理解 所以 你如果不是对他的口音感觉有小小迷的话 那就看notes好了... 我midterm之后的每堂课都没听懂过.... 当时感觉是天书... 日后翻reference理解的吧 嗯大概就这样
reference: 1. Luca Trevisan, Lecture Notes, 2011 (stanford cs261 lecture notes
2. Vijay Vazirani, Approximation algorithms, Springer, 2001.
3. David P. Williamson and David B. Shmoys, The design of approximation algorithms, Cambridge University Press, 2011
【grade】
homework 20% (4次)， midterm (35%), final (45%)。
workload看上去其实不是很大,但考虑到我智商有限就很大了
我觉得作业难度挺大的...每次作业我得做好几个小时...做个一两天的样子qwq 虽然网上可能存在答案 但是不自己做的话...你真的不知道每道题到底是怎么一种思想和解法... 虽然做完了我也不知道 每次大概4道题 但只抽2道改 你也不知道要抽哪道 所以都得做（x sunil允许相互讨论 但不允许抄作业（第一次作业就钓鱼了
midterm和final 难度适中吧 因为可能会出一些作业做过的类似的题（这时候你就知道做作业的重要性了 ） 会让你陈述某些学过的theorem 会有一些题的变形之类的 考的迷 因为我也不知道自己做的对不对 就按照思路和approximation的思想瞎写 学着上课做作业的思路瞎写 对于我这种渣渣当然是不会做很多题而且是做不完的QAQ 这里也就不多说了 （final sunil有道题解释错了....延误了很多学生的做题时间...所以大家好好听...那道题我本来就不会做留下最后15分钟瞎写了..gg
midterm和final的mean 大概在65左右 sd大概是15-20左右吧
就像之前几个post说的 因为是PG课本身给grade就还比较好 hw几乎满分(犯了一些微小的错误 midterm 刚到mean final差不多1个sd 拿的grade还行
如果你对algorithm有一点点想法的话 建议你可以上一上这门课感受一下
如果你对好grade有想法的话 上完3711还不错的话可以发一下request 问下sunil给不给你上
如果你像我一样对好grade弃疗无所谓并且想多学一点algorithm的话 你就大胆地上吧 毕竟历史的进程不可预料 万一这门课对你的grade做出了微小的贡献呢
个人主观评价，大家当故事看吧...反正大家都懂cwiki的作用...别信全 就酱
[COMP5712]Introduction to Combinatorial Optimization & 安利神龟prof
课程时间：2015年春季
授课教授：ARYA Sunil
我觉得教授：上课进度慢，考试比上课/作业简单，给龟好。TUT
这门课的Grade：母鸡（主要是prof是Grade神。
【关于这门课】
这门课有3711/3711H的pre-req，然而并没有太大关系（刚刚查了一下似乎硬性貌似没有 这个是request的时候prof提出来的
然后又因为这门课叫做Introduction to XXX 所以会从比较基础的开始讲起...（而且是通过经典open problem入手.. 哪怕第一节课会十分严肃地恐吓大家不懂blahblah的这个课不适合你，但是回头看他都有从最基础的定义，已经熟知的各种算法的复杂度，变形，之类的手把手教给你。
所以真正pre-req的知识大概只有基本搜索（DFS,BFS之类），线性规划（高中水平就好），基本矩阵计算（也就加减乘逆就好= =）基本图论（就是概念），嗯最好还知道生成树steiner tree是什么，知道网络流（大概怎么一回事，知道怎么求，都不用详细知道具体算法，因为课堂很多很多很多能够polynomial time完美解决的算法都给你提供blackbox直接用。。。
于是这门课【简要】大概介绍了几个大的问题
P NP NPC之类的的概念; Max cut; Linear Program and duality; Vertex/Edge/Set Cover Problem; Network Flow/Bipartite Graph... ; Multiway Cut Problem; Steiner Tree/Forest Problem; ....
和平时习惯的精确求解答案不同的是这里是一些NPhard NPC问题没法在多项式时间内解决，提出一些approximation的办法在多项式时间内求出一个离最优值不是太远的解。。
【关于prof】
这是一位出名的上课基础然后给龟好的prof，(参考大罗神2711Hcwiki
以及「由于是PG课，龟自然是极好的。」(来自谭神的5711cwiki
风格还是上课先讲清楚之后就开始从头用文字描述地往白板上写 讲的写的十分细致 然后如果不小心走神就可能各种听不懂只能不断以落后一两列板书的进度跟着他在白板上写的抄啊抄（哭。应付考试的话上课内容清楚了就好（再次参考罗神cwiki。担心有困难课前看一下notes不过可能上课就更容易走神了... 没去的话补笔记就好笔记是本体=。=
这个prof所有课grading应该都是20+35+45。
作业20% 一般四五道题，有基础理解听了课就会的，偶尔有需要自己开脑洞创新的，这个时候就需要敏锐的instinct，google和大腿（看了答案也不懂TUT。。。
midterm和final个体差距十分大。。一般是60~70的mean...SD十来分.....
注重基础的sunil可能会有大量小题简要回答课堂上的知识点（哎上课一定要听啊虽然听到时候会觉得为啥这么啰嗦最后可能会因为理解真的不透彻被打脸） 然后就来大题考运用创新（有一些觉得很基础的「common sense」或是知识也可能要认真写怎么得来的= =！但是考试可以举手问他这个要不要证....（啊不确定的一定要问或者写上去T T
【再次关于这门课】
刚开始学的时候真的每次都想报警:) 觉得真尼玛是「计算机理论科学家们」为了得到一个研究成果坐在lab然后发呆然后开脑洞然后强行想出来的:)
后来看到一段话和大家共勉TUT
「理科的东西比如数学物理，如果完全不知道这玩意是干嘛的那当然是没学懂；如果有一天突然发现自己能看懂了，觉得“哇好神奇啊好有趣啊好精彩啊！！”那其实依然没学懂；直到有一天发现，自己学过的东西怎么这么trivial这么显然，那才算是真正学懂了可以看下一本书了。」
另外觉得上课讲的还是太浅... 可是毕竟是Introduction，有很多方面要涉及所以深度可能照顾不周。 如果能就一个问题多一些变形更加深入理解问题就好了。（大神们都是听了几次就觉得没意思直接全翘来考试or不上这课了... 这个应该要prof背锅。
总而言之想要轻松课+好龟来enroll这个prof的课是好的选择，但是具体来不来上这个课就看个人惹... 这样也算是安利吧！
以上是作为一个新手的视角来写的，
最后
...大赌伤身啊旁友们! -w -
以上
