概述

本文将依照张国川老师的授课以及其余材料整理.

资源列表 & 前人经验

一些有意思且非常有用的网站：数据结构可视化:usfca版

Algorithm Design-Princeton

修佬的笔记 \(\quad\) WintermelonC的笔记 \(\quad\) StarStone的笔记 \(\quad\) BruceJqs的笔记

MIT 6.046J, 2015 spring \(\quad\) 点击下载wyh助教的ADS讲义

摘自罹魂梦蝶的经验帖：

学习情况：​我选的是bjj的班，老师本身上课的话可能并没有像myc或者zgc那样花费了很多时间投入，我本人也并没有认真听过几次课。从我个人的学习情况来看，基本就是上完课当天去听陈越老师在MOOC上的课程链接，然后自己整理笔记，整理完之后再看看作业题(ps.bjj老师每年的作业题都基本一样，所以如果平时作业分数想高一点的话……)

​对于project，这学期ads同组有一个非常强的大佬基本carry了代码工作，我和另一个同学就是写写注释、文档之类的活，对于文档，我做了一份报告模板每次展示的PPT是用reveal.js做的，这里附上我做的PPT链接1 链接2，这种方法可以快速产生简洁帅气的PPT，我还是很喜欢的，如果有同学想学的话可以参考xy的笔记链接.

考前补天：借用wrt的一句话，ads如果考前你还在看知识点，已经可以准备明年的考试了。ads适当做一些题目是很重要的，刷刷历年卷能极大的提高自己对题目的熟悉程度，考场上面猜也好猜~还有推荐一下我自己的笔记链接.

摘编自Miracle96的CC98经验帖：

提前学习动态规划等经典算法，做做 leetcode 题。

1.教考分离的情况较为严重。

针对期末复习，一定要把陈越钦定的ppt过一遍(因为这些是考点，而老师课上讲的并不一定是考点)。不懂的地方结合杨洋的智云。最后刷资源中提到的历年卷。从难度来看，前半学期数据结构的部分关键是理解每个操作是怎么实现的，然后能在草稿纸上画出来即可。后半学期开始变得玄学，特别是Local search和近似算法这块的题目变化很多，难度很大，不过很多题目都是算法导论的课后习题改编的的。最后两章并行计算和外排序虽然听起来也很难，但是考的都是固定的模板，如果只想追求分数的话记住每种方法的复杂度即可。

2.相对不重视代码，而重视对时间复杂度的分析

实际上ADS的考点和OI/ACM差别还是挺大的。因此即使以前搞过也不能掉以轻心，需要记忆算法复杂度的结论和理解分析方法（比如势能分析一定要理解）。后半部分的近似算法等也跟OI关系不大，很多纯数学的推导。

先过一遍课本知识，每天看一章，如cyll的PPT、wyy的笔记、笔记: 修佬 (但是后半部分,特别是近似算法,local search,随机算法,并行计算不全)、Zhou Jianjun佬的考前突击

考前跟按考点整理的历年卷习题复习一遍：xyx-1 \(\quad\) xyx-2

一些历年卷

教学大纲 & 评分细则

数据结构：（占\(\dfrac13\)）

  • Balanced Search Trees: AVL Tree, Splay Tree, B+ Tree, Red-Black Tree
  • Leftist Heaps, Skew Heaps, Binomial Queue
  • Inverted File Index（看起来简单实则极易丢分）

算法：

  1. Exact Algorithms

    • Divide and Conquer
    • Backtracking
    • Dynamic Programming

  2. Heuristic Algorithms

    • Greedy Algorithms
    • Local Search (find a solution, then making subtle modification to find an optimal solution)

  3. Approximation Algorithms

    • NP-Completeness
    • Approximation Algorithms
    • Randomized Algorithms

  4. Other Algorithms

    • Parallel Algorithms
    • External Sorting

Grading Policy：（平时分60'，不溢出）

  • 作业10'
  • 讨论10'
  • Project 30' (2-3人，Presentation)
  • MidTerm(10*，可以被Final Term覆盖)
  • Final Term (40*)