算法与数据结构

默认只展示每周独有的知识重点；节奏、考核、Tutorial 和避坑信息按需展开。

1. 1

   Introduction & Algorithm Analysis

   ### 📖 核心知识点：算法分析基础 本周是课程入门，建立对算法效率分析的基本框架。Joel Mackenzie 会介绍课程结构、编程语言要求（Java），以及 Big-O / Big-Ω / Big-Θ 渐进分析的数学基础。 - **核心概念**: Big-O notation, Big-Omega, Big-Theta, worst-case / average-case analysis, growth rates (O(1), O(log n), O(n), O(n log n), O(n²)) ⏰ **本周节奏**: 难度 ⭐⭐ | 预计投入 8h（Lecture 2h + Applied Class 1h + 自学 3h + Problem Set 准备 2h） 🎯 **考试关联**: Final Exam 50%（hurdle）必考渐进分析，常见题型：给定代码片段判断时间复杂度、证明 Big-O bound 🧪 **Applied Class**: 练习分析简单循环和递归函数的时间复杂度，使用 Master Theorem 📌 **作业关联**: Problem Set 1（Week 3 due）会涉及复杂度分析题 ⚠️ **易错点**: 混淆 Big-O 和 Big-Θ（Big-O 是上界，Big-Θ 是紧界）；忽略常数因子在实际性能中的影响

   Big-O
2. 2

   Abstract Data Types, Arrays & Linked Lists

   ### 📖 核心知识点：ADT 与线性数据结构 本周介绍抽象数据类型（ADT）的概念，以及最基础的两种实现方式：数组（Array）和链表（Linked List）。理解 ADT 接口与具体实现的分离是后续所有数据结构学习的基础。 - **核心概念**: ADT (Abstract Data Type) 定义, Array vs Linked List 的时间复杂度对比, Singly/Doubly Linked List, sentinel nodes, iterator pattern ⏰ **本周节奏**: 难度 ⭐⭐ | 预计投入 9h（Lecture 2h + Applied Class 1h + 自学 3h + 编程练习 3h） 🎯 **考试关联**: 数组 vs 链表的操作复杂度对比是常考选择题；链表的指针操作是编程题基础 🧪 **Applied Class**: 实现 Singly Linked List 的 insert/delete/search，分析各操作时间复杂度 📌 **作业关联**: Assignment 1（due Week 6）需要实现自定义 ADT，本周是基础 ⚠️ **易错点**: 链表删除节点时忘记处理 head/tail 边界情况；数组动态扩容的 amortized analysis 容易算错

   ADT (Abstract Data Type) 定义Array vs Li
3. 3

   Stacks, Queues & Deques

   ### 📖 核心知识点：栈、队列与双端队列 本周学习三种受限线性 ADT：Stack（LIFO）、Queue（FIFO）、Deque（双端操作）。重点在于理解它们的接口约束以及不同底层实现（Array-based vs Linked List-based）的权衡。 - **核心概念**: Stack (push/pop/peek), Queue (enqueue/dequeue), Deque, circular array implementation, java.util.ArrayDeque, amortized O(1) operations ⏰ **本周节奏**: 难度 ⭐⭐⭐ | 预计投入 10h（Lecture 2h + Applied Class 1h + 自学 3h + Problem Set 1 完成 4h）🔥 Problem Set 1 Due 🎯 **考试关联**: Stack/Queue 的应用场景题（如括号匹配、BFS/DFS 选择）占 Final 约 8-10 分 🧪 **Applied Class**: 用 Stack 实现表达式求值（postfix evaluation）；用 Queue 实现 BFS 模拟 📌 **作业关联**: Problem Set 1 截止（15/08），包含 Stack/Queue 应用题 ⚠️ **易错点**: Circular Array 实现 Queue 时 index 计算 `(front + size) % capacity` 容易出错；Stack overflow 未处理

   Stack (push/pop/peek)Queue (e
4. 4

   Sorting Algorithms (Part I)

   ### 📖 核心知识点：基础排序算法 本周开始排序专题，覆盖 O(n²) 级别的简单排序和 O(n log n) 的 Merge Sort。排序是算法课的核心模块，也是 Final Exam 的高频考点。 - **核心概念**: Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, divide-and-conquer paradigm, stability (稳定性), in-place vs out-of-place ⏰ **本周节奏**: 难度 ⭐⭐⭐ | 预计投入 10h（Lecture 2h + Applied Class 1h + 自学 4h + 编程练习 3h） 🎯 **考试关联**: 排序算法的比较（时间/空间/稳定性）几乎必考；手动模拟排序过程是常见题型 🧪 **Applied Class**: 手动 trace Merge Sort 的 divide/merge 过程；比较 Insertion Sort 在近乎有序数据上的优势 📌 **作业关联**: Assignment 1 可能要求实现高效排序，本周打好基础 ⚠️ **易错点**: Merge Sort 的 merge 步骤中剩余元素处理容易遗漏；混淆 stable 和 in-place 的概念

   Bubble SortSelectio
5. 5

   Sorting Algorithms (Part II) & Selection

   ### 📖 核心知识点：高级排序与选择算法 本周继续排序专题，介绍 Quick Sort（最常用的实际排序算法）和 Heap Sort，以及基于排序的 Selection 问题（找第 k 小元素）。 - **核心概念**: Quick Sort (Lomuto/Hoare partition), pivot selection strategies, Heap Sort, Quick Select, lower bound Ω(n log n) for comparison-based sorting, Counting Sort / Radix Sort (non-comparison) ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐ | 预计投入 11h（Lecture 2h + Applied Class 1h + 自学 4h + Problem Set 2 4h）🔥 Problem Set 2 Due 🎯 **考试关联**: Quick Sort 的 worst-case 分析和 pivot 选择策略是 Final 高频考点；比较排序下界证明可能出证明题 🧪 **Applied Class**: 手动 trace Quick Sort partition 过程；分析不同 pivot 策略对性能的影响 📌 **作业关联**: Problem Set 2 截止（29/08），涉及排序算法分析 ⚠️ **易错点**: Quick Sort worst-case O(n²) 出现在已排序输入 + 选取首/尾元素为 pivot 时；Quick Select 的期望 O(n) 与 worst-case O(n²) 混淆

   Quick Sort (Lomuto/Hoare partitio
6. 6

   Trees & Binary Search Trees

   ### 📖 核心知识点：树与二叉搜索树 本周进入非线性数据结构。Tree 和 BST 是后续 AVL/B-Tree/Heap 的基础。掌握递归遍历和 BST 的性质至关重要。 - **核心概念**: Tree terminology (root, leaf, depth, height), Binary Tree, BST property, BST search/insert/delete, tree traversals (inorder, preorder, postorder, level-order) ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐ | 预计投入 12h（Lecture 2h + Applied Class 1h + 自学 4h + Assignment 1 冲刺 5h）🔥 Assignment 1 Due (5 Sep) 🎯 **考试关联**: BST 操作和遍历是 Final 必考，常见题型：给定插入序列画出 BST、手动执行删除操作 🧪 **Applied Class**: 实现 BST 的 insert/search/delete；练习四种遍历方式 📌 **作业关联**: Assignment 1（20%）截止 5 Sep — 本周必须完成最终调试和提交 ⚠️ **易错点**: BST 删除有两个子节点的节点时，找 inorder successor/predecessor 的实现容易出错；递归遍历的 base case 遗漏

   Tree termi
7. 7

   Balanced BSTs: AVL Trees & B-Trees

   ### 📖 核心知识点：平衡二叉搜索树 本周学习如何保持 BST 的平衡性以保证 O(log n) 操作。AVL Tree 通过旋转维持平衡，B-Tree 用于磁盘存储优化。这是数据结构课的核心难点之一。 - **核心概念**: AVL Tree (balance factor, single/double rotations: LL, RR, LR, RL), B-Tree (order, splitting, merging), 2-3 Tree, Red-Black Tree (概念), self-balancing guarantees ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐⭐ | 预计投入 12h（Lecture 2h + Applied Class 1h + 自学 5h + 复习 4h）🔥 高压周 🎯 **考试关联**: AVL 旋转是 Final 必考大题（通常 10-15 分），要求手动画出旋转过程；B-Tree 插入/删除也常考 🧪 **Applied Class**: 手动执行 AVL 插入序列并画出每次旋转后的树；B-Tree 插入/分裂练习 📌 **作业关联**: Assignment 2 可能涉及 balanced tree 实现，从本周开始准备 ⚠️ **易错点**: LR 和 RL 双旋转的方向容易混淆；B-Tree 节点分裂后 parent 的 key 提升规则；AVL 删除后可能需要多次旋转（不同于插入只需一次）

   AVL Tree (bala
8. 8

   Hash Tables & Hashing

   ### 📖 核心知识点：哈希表与哈希函数 本周学习实现 O(1) 平均时间的查找、插入和删除。Hash Table 是最实用的数据结构之一，也是工业界使用最广泛的。 - **核心概念**: Hash function design, collision resolution (separate chaining, open addressing: linear probing, quadratic probing, double hashing), load factor α, rehashing, universal hashing, Java HashMap ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐ | 预计投入 11h（Lecture 2h + Applied Class 1h + 自学 4h + Problem Set 3 4h）🔥 Problem Set 3 Due 🎯 **考试关联**: Hash Table 的冲突处理策略对比是高频考点；给定 hash function 和数据序列，手动填表 🧪 **Applied Class**: 实现 separate chaining 和 linear probing 两种策略；分析不同 load factor 下的性能 📌 **作业关联**: Problem Set 3 截止（19/09），包含 hashing 分析题 ⚠️ **易错点**: Open addressing 删除时不能直接置空（需要 DELETED marker）；load factor 超过阈值不 rehash 导致性能退化；hash function 对负数取模的处理

   Hash fu
9. 9

   Priority Queues & Heaps

   ### 📖 核心知识点：优先队列与堆 本周学习 Priority Queue ADT 及其最高效实现 — Binary Heap。Heap 是 Heap Sort 和图算法（Dijkstra, Prim）的关键组件。 - **核心概念**: Priority Queue ADT (insert, extractMin/Max), Binary Heap (min-heap, max-heap), heap property, array representation, sift-up / sift-down, heapify (bottom-up O(n) construction), java.util.PriorityQueue ⏰ **本周节奏**: 难度 ⭐⭐⭐ | 预计投入 9h（Lecture 2h + Applied Class 1h + 自学 3h + Assignment 2 启动 3h） 🎯 **考试关联**: Heap 的 array 表示和 sift 操作是必考内容；heapify 的 O(n) 时间证明可能出分析题 🧪 **Applied Class**: 手动构建 min-heap 并执行 extractMin；用 bottom-up heapify 从无序数组构建 heap 📌 **作业关联**: Assignment 2（due Week 12）开始，可能需要实现 Priority Queue ⚠️ **易错点**: 数组下标从 0 还是 1 开始会影响 parent/child 计算公式；max-heap 和 min-heap 的 sift 方向容易混淆

   Priority Queue ADT (i
10. 10

    Graphs: Representations, BFS & DFS

    ### 📖 核心知识点：图的基础与遍历 本周进入图论专题。图是建模现实世界关系的最强大工具，BFS 和 DFS 是所有图算法的基础。 - **核心概念**: Graph terminology (vertex, edge, directed/undirected, weighted), adjacency matrix vs adjacency list, BFS (Breadth-First Search), DFS (Depth-First Search), connected components, topological sort ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐ | 预计投入 11h（Lecture 2h + Applied Class 1h + 自学 4h + Problem Set 4 + A2 4h）🔥 Problem Set 4 Due 🎯 **考试关联**: BFS/DFS 手动 trace 是 Final 必考大题（10-15 分），要求写出访问顺序和 discovery/finish time 🧪 **Applied Class**: 在给定图上手动执行 BFS 和 DFS，记录每个节点的距离/时间戳；实现 topological sort 📌 **作业关联**: Problem Set 4 截止（10/10）；Assignment 2 可能涉及图算法 ⚠️ **易错点**: BFS 用 Queue、DFS 用 Stack（或递归）不要混淆；有向图的 topological sort 只对 DAG 有效；adjacency matrix 空间 O(V²) 对稀疏图浪费

    Graph termi
11. 11

    Graph Algorithms: Shortest Paths & MST

    ### 📖 核心知识点：最短路径与最小生成树 本周学习图论中最重要的两类问题：最短路径（Dijkstra, Bellman-Ford）和最小生成树（Prim, Kruskal）。这些算法在网络路由、地图导航等领域广泛应用。 - **核心概念**: Dijkstra's algorithm (non-negative weights, with PQ), Bellman-Ford (negative edges), Prim's MST (greedy, PQ-based), Kruskal's MST (Union-Find), relaxation technique, greedy correctness proofs ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐⭐ | 预计投入 13h（Lecture 2h + Applied Class 1h + 自学 5h + Assignment 2 冲刺 5h）🔥 高压周 🎯 **考试关联**: Dijkstra 手动 trace 几乎每年必考；Prim vs Kruskal 的比较是常见简答题 🧪 **Applied Class**: 在加权图上手动执行 Dijkstra（记录每步的 distance table）和 Prim/Kruskal 📌 **作业关联**: Assignment 2（due Week 12）涉及图算法实现 ⚠️ **易错点**: Dijkstra 不能处理负权边（常考陷阱）；Kruskal 需要 Union-Find 检测环；Prim 从不同起点结果可能不同但总权重相同

    Dijkstra's algorithm (
12. 12

    String Algorithms & Sets

    ### 📖 核心知识点：字符串算法与集合 本周覆盖字符串模式匹配算法和集合/多集合 ADT。字符串算法在文本搜索、生物信息学中至关重要。 - **核心概念**: Naive string matching O(mn), KMP algorithm (failure function), Boyer-Moore (概念), Trie data structure, Set ADT, Multiset, ordered vs unordered sets ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐ | 预计投入 12h（Lecture 2h + Applied Class 1h + 自学 4h + Assignment 2 最终提交 5h）🔥 Assignment 2 Due (29 Oct) 🎯 **考试关联**: KMP 的 failure function 构建和匹配过程是常考题；Trie 的应用场景题 🧪 **Applied Class**: 手动构建 KMP failure function 并执行模式匹配；Trie 的插入和前缀搜索 📌 **作业关联**: Assignment 2（20%）截止 29 Oct — 最后提交机会 ⚠️ **易错点**: KMP failure function 的递推公式容易写错；Trie 中标记单词结束节点的 flag 遗漏导致前缀误判为完整单词

    Naive stri
13. 13

    Review & Exam Preparation

    ### 📝 复习周：全课程回顾与考试准备 本周是考前复习周，系统回顾 12 周内容。Final Exam 占 50% 且是 hurdle（必须 ≥50% 才能通过课程），需要严肃对待。 - **核心概念**: 全课程 ADT 总结（Array, LinkedList, Stack, Queue, BST, AVL, Heap, HashTable, Graph, Trie），各数据结构操作复杂度对比表，排序算法对比表 ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐⭐ | 预计投入 15h+（全力复习）🔥 Problem Set 5 Due + 备考 🎯 **考试关联**: Final Exam 180 分钟，closed book，涵盖全部 12 周内容。题型包括：复杂度分析、手动 trace 算法执行过程、伪代码编写、证明/分析题。Hurdle: 必须 ≥50% 🧪 **Applied Class**: 模拟考题练习，重点练习 AVL 旋转、Dijkstra trace、排序算法 trace 📌 **作业关联**: Problem Set 5 截止（31/10），这是最后一次 Problem Set ⚠️ **易错点**: 时间管理 — 180 分钟内需要完成大量手动 trace 题，建议每题分配好时间；AVL 旋转和 Dijkstra trace 是最耗时的题型，优先练习

    全课程 ADT 总结（ArrayLi