ICS 46 is UCI's data structures course, focused on implementing classic data structures in C++ and analyzing their running time and memory use.
This page collects lecture-by-lecture notes for classmates who want a structured review of templates, pointers and ownership, algorithm analysis, and data structures such as lists, stacks, and queues.
ICS 46 是 UCI 的数据结构课程,重点在于用 C++ 实现经典数据结构,并分析它们的运行时间与内存开销。
这个页面汇总按讲整理的课程笔记,方便同学回顾模板、指针与所有权、算法分析,以及链表、栈、队列等数据结构。
What ICS 46 is about, C++ unit testing with Google Test, why templates exist, function templates and compile-time instantiation, .hpp/.tpp layout, implicit type constraints, and class templates (the Box example).
Last edited on October 16, 2026
Random number generation in C++, references, raw pointers, and an introduction to smart pointers and ownership.
Last edited on October 16, 2026
Finishing smart-pointer ownership, 1D array review, multidimensional arrays, why we analyze algorithms, empirical timing of running time, and mathematical cost models.
Last edited on October 16, 2026
Counting operations in 2-Sum, Big-O / Big-Ω / Big-Θ, common orders of growth, space complexity, and building an ArrayList (dynamic array) with resizing and amortized analysis.
Last edited on October 16, 2026
Singly linked list API, implementation and analysis, doubly linked lists, ArrayList vs. linked lists, and the Stack ADT.
Last edited on October 16, 2026
Stacks on linked lists, the Queue ADT and its implementations, expression evaluation with stacks, and queue applications.
Last edited on October 16, 2026
ADTs vs. data structures, setting up recurrences, the recursion-tree method, and the Master Theorem.
Last edited on October 22, 2026
Circular array queues and deques, sorting basics (cost model, memory, stability), selection sort vs. insertion sort.
Last edited on October 22, 2026
Merging sorted halves, top-down merge sort and its N log N analysis, stability and improvements, plus quick sort's background (continued in Lecture 9).
Last edited on October 29, 2026
Quick sort: Hoare/Sedgewick 2-pointer partitioning, full traces, worst/best/average analysis, stability and in-place properties, comparison of all sorts so far, and pivot/cutoff improvements.
Last edited on October 29, 2026
Tree terminology (depth, height, degree), full vs complete binary trees, node-count and height bounds, the BinaryTree skeleton, level/pre/in/post-order traversals, and binary heaps: heap order, array representation, swim, insert and sink.
Last edited on November 3, 2026
ICS 46 课程概览、用 Google Test 写 C++ 单元测试、为什么需要模板、函数模板与编译期实例化、.hpp/.tpp 文件组织、类型参数的隐式约束，以及类模板（Box 示例）。
最后编辑于 2026 年 10 月 16 日
C++ 随机数生成、引用、裸指针，以及智能指针与所有权（ownership）入门。
最后编辑于 2026 年 10 月 16 日
智能指针所有权收尾、一维数组复习、多维数组、为什么要分析算法、运行时间的经验测量，以及运行时间的数学模型。
最后编辑于 2026 年 10 月 16 日
2-Sum 问题的操作计数、Big-O / Big-Ω / Big-Θ、常见增长阶、空间复杂度，以及实现 ArrayList（动态数组）的扩容与均摊分析。
最后编辑于 2026 年 10 月 16 日
单向链表的接口、实现与分析，双向链表，ArrayList 与链表的对比，以及栈（Stack）ADT。
最后编辑于 2026 年 10 月 16 日
基于链表的栈、队列（Queue）ADT 及其实现、用栈求值表达式，以及队列的应用。
最后编辑于 2026 年 10 月 16 日
ADT 与数据结构的区别、建立递推式、递归树方法，以及主定理（Master Theorem）。
最后编辑于 2026 年 10 月 22 日
循环数组队列与双端队列、排序基础（代价模型、内存、稳定性），以及选择排序与插入排序的对比。
最后编辑于 2026 年 10 月 22 日
合并两个有序半段、自顶向下归并排序及其 N log N 分析、稳定性与改进，以及快速排序的背景（在 Lecture 9 中继续）。
最后编辑于 2026 年 10 月 29 日
快速排序：Hoare/Sedgewick 双指针划分、完整排序过程追踪、最坏/最好/平均情况分析、稳定性与原地性、目前各排序算法对比，以及选主元与小数组截断等改进。
最后编辑于 2026 年 10 月 29 日
树的术语（深度、高度、度）、满二叉树与完全二叉树、节点数与高度界、BinaryTree 骨架、层序/前序/中序/后序遍历，以及二叉堆：堆序、数组表示、swim、insert 与 sink。
最后编辑于 2026 年 11 月 3 日