※ 本文是否可提供台大同学转作其他非营利用途？（须保留原作者 ID） （是／否／其他条件）：是 哪一学年度修课： 111-1 ψ 授课教师 (若为多人合授请写开课教师，以方便收录) 陈倩瑜 λ 开课系所与授课对象 (是否为必修或通识课 / 内容是否与某些背景相关) 生机系/所选修 and 生机系人工智慧领域专长课程 δ 课程大概内容 具体可以看台大课程网，以下为实际上课进度 Union-Find Analysis of Algorithms Bags, Queues, and Stacks Elementary Sort Merge Sort Quick Sort Priority Queues ──────────期中考到这里──────────────── Symbol Table Binary Search Trees Balanced Search Trees Geometric Applications of BSTs Undirected Graphs Directed Graphs Minimum Spanning Trees Shortest Paths ──────────期末考到这里──────────────── Hash Table和Dynamic Programming都来不及讲了，期末考之後老师在NTU Cool上上传了 两年前的影片作为补充。 课程网上提到的 (optional)String相关的演算法更是完全没时间上到。 Ω 私心推荐指数(以五分计) ★★★★★ ·整体 ★★★★★ 推就一个字！ ·想修甜甜的资料结构与演算法 ★★★★★ ·想修凉凉的资料结构与演算法 ★★★★★ ·想修甜甜凉凉的普通选修课 ☆ 看看隔壁资工的DSA，我觉得不需要别的解释了吧，这已经是最甜凉的资料结构与演算法 相关课程了！ 但是！甜凉只是相对於其他资料结构或者演算法课程而言的。完全不想花时间的话，还是 不要来学资料结构与演算法了。虽然这课很甜，个人也觉得很凉，但开学一开始加签到 120人，退选加停修後只剩下74个同学坚持到最後。毕竟资料结构和演算法本身就不是容 易学的东西。 如果只是想当甜凉选修，请高抬贵手不要来抢加签名额（哭）。 ·留学要刷GPA ★★★★★ ·找工作要刷题 ★★★ 我个人是上半年有选资工的DSA，但因为半路突然发现资工的课给分超级惨烈，於是决定 停修。毕竟要留学的话，刷GPA比啥都重要。 PDSA应该是最容易刷GPA的相关课程了吧。 反正课程描述都差不多，爽爽拿高分不好吗？ 但如果是为了找工作的话，这门课其实并没有资工DSA那麽扎实。不过如果只是想对资料 结构与演算法了解个大概，然後有能力自己刷LeetCode的话，完全是够了。 ·想学习实用资料结构与演算法 ★★★★★ 课程内容最大的特色，应该就是强调资料结构与演算法的实际应用面向了。比如讲 Union-Find时会带出percolation问题，讲Sorting时会提到convex hull问题，讲 Priority Queues时会讲到event-driven simulation。应该很适合想要实际使用程式的工 程科系的同学。 ·想学习基础资料结构与演算法 ★★★★★ ·非电资科系想在未来挑战资工DSA ★★★★★ 个人感觉台大的普通程式课，和遍地IOI电神的资工DSA，是有极大的gap的。 如果是非电资科系，但有一颗想要学程式的心的话， 先修一下PDSA对资料结构与演算法有一个大致的了解，再去资工打Boss， 是一个非常好的过渡。 ·电神 ☆ ·已经在刷LeetCode ☆ 这门课只教基础的资料结构与演算法， 强者还是直接去资工和IOI电神们神仙打架吧。 η 上课用书(影印讲义或是指定教科书) Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne 以及配套网站、投影片 μ 上课方式(投影片、团体讨论、老师教学风格) 实体、远距直播、NTUCool课程影片三种方式任选，出席完全不管，很自由。 课程影片上传得非常及时，一般下午的课，当天晚上就会传上去。 我个人是因为NTUCool可以倍速播放所以都直接看课程影片。 此外，还有一个脸书社团来发各种通知。 老师上课最大的特点，就是会一行一行带着大家看code，讲解非常仔细，且乐於解答同学 的问题。所以不用怕演算法通灵！跟着上课的进度一定可以理解的。 TA hour一般每周两次，主要是作业答疑，会根据当周的作业情况调整，不过我一次都没 去过啦。但平时偶尔问一些问题，可以感觉到助教们都非常认真负责。 σ 评分方式(给分甜吗？是紮实分？) Homework: 50% Midterm: 20% Final: 30% 最後应该有调一点分， 我个人原始分换算A，最後A+，不过怎麽调的就不清楚了。 ρ 考题型式、作业方式 1.作业 说好的作业很硬呢？特甜凉好嘛！ 一共十题，只有程式题，没有手写题，用online judge批改，限定使用Java写，都是与上 课内容直接相关的题目。我个人的话，最前面一些题目坚持手刻，最多花一个工作日就可 以全部AC。有部分比较简单的题目call library的话极快，比如最後一个作业20分钟就AC 了。不过感觉还是手刻的给自己的印象比较深刻。 然後比较让我吐槽的一点是，很多题naive implementation竟然也能拿个60-80分！！！ 蛤？？？这也太凉了吧！！！开学时说好的这课loading挺重的呢？？？ Too young, too simple！！！ 最後应该是有28位同学拿满作业分数，50多位同学拿到90%以上的分数。全班总共才74人 诶！ 唯一一次比较有挑战的是HW7有关Geometric Search的competition，速度前10%的同学总 成绩额外加3分（7人）。好像最後似乎只有一位最快的同学刻出了KD Tree……我反正没 刻出来，最後连普通的RB Tree都来不及补了（哭）。 此外，还有选6道LeetCode的题目（4道Easy和2道Medium），让有兴趣的同学可以自己练 ，不过不强求。 总体而言感觉这个作业量对於想要简单了解一下各种资料结构与演算法来说是够了，但是 想要比较熟悉的话，最好还是自己再找点题去做。 想想隔壁资工的DSA，一次作业手写满分300分，一道LeetCode Hard难度的题目也就20分 ；再想想资工的程式题，教红黑树，作业出吉如一线段树套treap修改区间值...... 想要甜凉作业的都快来修生机的PDSA吧！ 2.考试 期中考试20%，教到哪里就考哪里，平均分56.89，最高分89。 期末考试30%，名义上是整学期都要考的，但是实际上感觉都是後半学期的内容，平均分 41.9，最高分79。 相比於作业的甜凉，考试就颇有难度了。内容有选择、证明、写pseudo code解题之类的 。有一些在上课时提到过，这个点可能会考。基本上就是投影片细节+一些比较通灵的问 题。 比如说，期末考最後一题考了Graph Coloring。 蛤？？？为什麽考试会出NP Complete的问题？？？！！！ 看到这题我就吓傻了好嘛！ 反正这题没人拿满分，最多也就是greedy解。 大概是作业太甜了所以拿考试来控制一下分数吧。 ω 其它(是否注重出席率？如果为外系选修，需先有什麽基础较好吗？老师个性？ 加签习惯？严禁迟到等…) 1.Prerequisite 只需要会一种程式语言就可以了。不会Java也没关系，因为一开始不会用到generic， inheritance之类的内容，所以开学再学完全来得及。我觉得差不多修过商程设或者非 电资的程式课就够了。 2.加签方式 想要加签的人太多了，所以最後采用抽签方式，高年级与第一堂课到场者有优先权，97抽 40，加上初选凑满120人。但是！HW1大劝退！大概有些同学程式基础不够，加上一上来就 讲Union-Find，其实相比从linked list与stack开始讲，要难理解一些。两周後退选到只 剩90人，到了期末最後只有74人了。 感觉以後加签的时候可能可以设计一个HW0让大家不要误入qwq 毕竟加签抽签实在是太刺激啦。 Ψ 总结 非常幸运能抽中PDSA的加签名额！ 顺利拿到满意的成绩也非常开心！ 推给所有非电资但想要学写程式的同学！ --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 101.12.95.183 (台湾) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/NTUcourse/M.1673449860.A.CE0.html ※ 编辑: JapanSpitz (101.12.95.183 台湾), 01/11/2023 23:21:56 ※ 编辑: JapanSpitz (140.112.25.99 台湾), 01/12/2023 15:52:57 ※ 编辑: JapanSpitz (140.112.25.99 台湾), 01/12/2023 15:53:36