CS61B临时专题
请将所有代码仓库保持在 Private 状态。
CS 61B Spring 2024
先介绍一下官网的各个栏目是干什么的
- Home：日程表
- Calendar：没什么用。
- Course Info：课程背景信息、以及校内的考核标准之类的。
- Staff：讲师和助教。
- Labs：10个实验。
- Homeworks：3个家庭作业。
- Projects：6个项目。
- Resources：所用工具的说明，一般为课外文档。
- Troubleshooting
计划表
| 周次 | 日期 | 讲座 (Lecture) | 阅读 (Readings) | 讨论 (Discussion) | 实验 (Lab) | 作业 (Homework) | 项目 (Project) |
|---|---|---|---|---|---|---|---|
| 1 | 1/17 (三) | Lec 1: Intro (课程介绍，实例变量) | Ch 1 | 无 | Lab 1: Setup (due 1/19) | HW 0A: Java Syntax (due 1/19) | Project 0: 2048 (due 1/29) |
| 1/19 (五) | Lec 2: Defining and Using Classes (定义与使用类) | Ch 2 | 无 | HW 0B: Data Structures (due 1/22) | |||
| 2 | 1/22 (一) | Lec 3: Lists I: References, Recursion, and Lists (列表 I: 引用、递归和列表) | Ch 3 | Disc 1: Intro to Java | Lab 2: Debugging I (due 1/26) | ||
| 1/24 (三) | Lec 4: Lists II: SLLists (列表 II: 单链表) | Ch 4 | 无 | HW 1 (due 1/26) | |||
| 1/26 (五) | Lec 5: Lists III: DLLists and Arrays (列表 III: 双链表与数组) | Ch 5, Ch 6 | 无 | ||||
| 3 | 1/29 (一) | Lec 6: Testing (测试) | Ch 7, TDD is dead, … | Disc 2: Scope, Static, Linked Lists, Arrays | Lab 3: Debugging II (due 2/2) | ||
| 1/31 (三) | Lec 7: Lists IV: Arrays and Lists (列表 IV: 数组与列表) | Ch 8 | 无 | Project 1A: LinkedListDeque61B (due 2/5) | |||
| 2/2 (五) | Lec 8: Inheritance I: Interface and Implementation Inheritance (继承 I: 接口与实现继承) | Ch 9 | 无 | ||||
| 4 | 2/5 (一) | Lec 9: Inheritance II: Extends, Casting, Higher Order Functions (继承 II: 扩展、类型转换、高阶函数) | Ch 10 | Disc 3: Inheritance | Project 1 Workday | ||
| 2/7 (三) | Lec 10: Inheritance III: Subtype Polymorphism, Comparators, Comparable (继承 III: 子类型多态、比较器) | Ch 11 | 无 | Project 1B: ArrayDeque61B (due 2/12) | |||
| 2/9 (五) | Lec 11: Inheritance IV: Iterators, Object Methods (继承 IV: 迭代器、对象方法) | Ch 12 | 无 | ||||
| 5 | 2/12 (一) | Lec 12: Asymptotics I (算法复杂度分析 I) | Ch 13 | Disc 4: Comparators, Iterators | Lab 4: Git (due 2/20) | ||
| 2/14 (三) | Lec 13: Ask Anything: Midterm 1 (期中1答疑) | (复习) | 无 | Project 1C: Deque61B Enhancements (due 2/20) | |||
| 2/16 (五) | Lec 14: Disjoint Sets (并查集) | Ch 14 | 无 | HW 2: Percolation (due 2/26) | |||
| 2/15 (四) | Midterm 1 (晚上7-9点) | ||||||
| 6 | 2/19 (一) | 无讲座 (学术假日) | Disc 5: Asymptotics, Disjoint Sets | Lab 5: Disjoint Sets (due 2/26) | |||
| 2/21 (三) | Lec 15: Asymptotics II (算法复杂度分析 II) | Ch 15 | 无 | Project 2A: NGrams (due 3/6) | |||
| 2/23 (五) | Lec 16: ADTs, Sets, Maps, BSTs (抽象数据类型、集合、映射、二叉搜索树) | Ch 16 | 无 | ||||
| 7 | 2/26 (一) | Lec 17: B-Trees (2-3, 2-3-4 Trees) (B树) | Ch 17 | Disc 6: ADTs, Asymptotics II, BSTs | Lab 6: BSTMap (due 3/1) | ||
| 2/28 (三) | Lec 18: Red Black Trees (红黑树) | Ch 18 | 无 | ||||
| 3/1 (五) | Lec 19: Hashing (哈希) | Ch 19 | 极 | ||||
| 8 | 3/4 (一) | Lec 20: Hashing II (哈希 II) | Ch 20 | Disc 7: B-Trees, LLRBs, Hashing | Lab 7: LLRBs (due 3/8) | ||
| 3/6 (三) | Lec 21: Heaps and Priority Queues (堆与优先队列) | Ch 极 | 无 | ||||
| 3/8 (五) | Lec 22: Tree and Graph Traversals (树与图的遍历) | Ch 22 | 无 | Project 2B/2C Checkpoint (due 3/15) | |||
| 9 | 3/11 (一) | Lec 23: Graph Traversals and Implementations (图的遍历与实现) | Ch 23 | Disc 8: Graphs, Heaps | Lab 8: HashMaps (due 3/15) | HW 3 (due 3/18) | |
| 3/13 (三) | Lec 24: Shortest Paths (最短路径) | Ch 24 | 无 | ||||
| 3/15 (五) | Lec 25: Minimum Spanning Trees (最小生成树) | Ch 25 | 无 | ||||
| 10 | 3/18 (一) | Lec 26: Directed Acyclic Graphs (有向无环图) | Ch 28 | Disc 9: Shortest Paths, MSTs | Project 2 Workday | Project 2B: Wordnet & 2C: Enhancements (due 4/1) | |
| 3/20 (三) | Lec 27: Software Engineering I (软件工程 I) | Ch 27 | 无 | ||||
| 3/22 (五) | Lec 28: Prefix Operations and Tries (前缀操作与字典树) | Ch 26 | 无 | ||||
| 3/21 (四) | Midterm 2 (晚上7-9点) | ||||||
| 11 | 3/25 (一) | 无讲座 (春假) | 无讨论 | 无实验 | |||
| 3/27 (三) | 无讲座 (春假) | ||||||
| 3/29 (五) | 无讲座 (春假) | ||||||
| 12 | 4/1 (一) | Lec 29: Sorting I: Selection Sort, Heapsort (排序 I: 选择排序、堆排序) | Ch 29 | Disc 10: Graphs II, Tries | Lab 9: Getting Started on Project 3 (due 4/5) | ||
| 4/3 (三)极 | Lec 30: Sorting II: Mergesort and Insertion Sort (排序 II: 归并排序与插入排序) | Ch 30 | 无 | Project 3A: World Generation (due 4/15) | |||
| 4/5 (五) | Lec 31: Software Engineering II (软件工程 II) | Ch 31 | 无 | ||||
| 13 | 4/8 (一) | Lec 32: Sorting III: Quicksort (排序 III: 快速排序) | Ch 32 | Disc 11: Sorting | Lab 10: Tetris (due 4/12) | ||
| 4/10 (三) | Lec 33: Sorting IV: Sorting and Algorithmic Bounds (排序 IV: 排序与算法边界) | Ch 34 | 无 | ||||
| 4/12 (五) | Lec 34: Software Engineering III (软件工程 III) | Ch 33 | 无 | ||||
| 14 | 4/15 (一) | Lec 35: Sorting V: More Quicksort, Radix Sorts (排序 V: 深入快排、基数排序) | Ch 35 | Disc 12: More Sorting | Project 3 Workday | Project 3B/C: Interactivity + Ambition (due 4/22) | |
| 4/17 (三) | Lec 36: Sorting VI: Radix vs. Comparison Sorting (排序 VI: 基数排序 vs. 比较排序) | Ch 36 | 无 | ||||
| 4/19 (五) | Lec 37: Software Engineering IV (软件工程 IV) | Ch 37 | 无 | ||||
| 15 | 4/22 (一) | Lec 38: Compression (数据压缩) | Ch 38 | Disc 13: Goodbye | Project 3 Checkoffs | HW 4 (due 4/28, 可延至5/3) | |
| 4/24 (三) | Lec 39: Complexity and P=NP? (复杂度与P=NP?问题) | Ch 39 | 无 | ||||
| 4/26 (五) | Lec 40: Summary, Fun (总结与趣谈) | (无) | 无 | ||||
| 16 | 4/29 (一) | 无讲座 (RRR周) | 无讨论 | 无实验 | |||
| 5/1 (三) | 无讲座 (RRR周) | ||||||
| 5/3 (五) | 极讲座 (RRR周) | ||||||
| 17 | 5/7 (二) | Final Exam (上午8-11点) |
学习策略建议：
- 理论与实践结合： 每周看完Lecture和Reading后，立即动手完成对应的Lab和HW，这是巩固知识的关键。
- 项目前置： 大型项目（如Project 2, 3）耗时很长，务必在发布后尽早阅读说明并开始规划，不要拖延到最后。
- 善用资源： Discussion材料和考试复习资料（Exam Prep）是理解难点和备考的宝贵资源，请充分利用。
- 标记关键日期： 将考试和主要项目截止日期在日历中高亮，合理分配时间，避免冲突。
如何使用skeleton和Gradescope
配置
安装插件：Java Visualizer和CS61B。
进入 文件->项目结构 -> 项目设置 -> 项目，配置 SDK。
在 库 选项卡中，添加 library-sp24 目录，对整个skeleton-sp24生效。
Lab 03: Debugging (Part 2)
这是一个以实践为核心的调试实验，你将通过修复一个名为“Adventure”的游戏中的一系列bug，来深入学习高级调试技巧。
实验核心任务
你需要扮演“调试侦探”，依次修复该游戏中的四个关卡（Stage），每个关卡都包含一个特定的bug：
- BeeCountingStage: 修复一个
NullPointerException和一个IndexOutOfBoundsException。 - SpeciesListStage: 修复逻辑错误，需要处理边界情况。
- PalindromeStage: 修复两个bug，包括一个可能导致无限循环的错误。
- MachineStage: 修复两个隐藏在“神秘函数”中的bug，要求你不去阅读这些函数的实现，而是通过观察其输入输出来判断它们是否正确，从而理解“抽象”的重要性。
你需要掌握的调试技能
完成本实验需要你运用以下技能：
- 阅读堆栈跟踪（Stack Trace）：学会从错误信息中快速定位问题根源。
- 使用IntelliJ调试器：熟练使用断点、单步执行、条件断点等功能。
- 观察与推理：像侦探一样，通过观察程序状态和行为来推断bug成因，而不是盲目修改代码。
- 可选高级技能：实验还介绍了如何设置异常断点（当特定异常抛出时自动暂停）以及如何使用表达式评估和监视（Expressions and Watches） 功能来动态查看变量值。
实验流程
- 运行游戏与测试：首先运行主程序
AdventureGame来了解游戏本应如何工作，然后运行测试AdventureGameTests来发现所有失败的地方。 - 逐个修复：按照顺序（BeeCounting -> SpeciesList -> Palindrome -> Machine）修复每个关卡的bug。修复一个关卡后，相应的测试便会通过。
- 提交：完成所有关卡后，将代码提交到GitHub并上传至Gradescope进行评分。
总之，Lab 03 是一个大型的调试实战练习，旨在通过有趣的游戏化场景，让你摆脱对
System.out.println的依赖，真正掌握使用专业调试工具（如IntelliJ Debugger）来高效定位和修复复杂程序错误的能力。- BeeCountingStage: 修复一个