LECTURE OUTLINE Data Structures and Algorithms

281-record Lab 1 Lab 流程关于 CAEN Mac mission control Makefile Perf Valgrind vector::reserve 一个冷知识: C++并不支持 int x,y = 1 的 initialization syntax getopt_long Lec 2 heap vector/deque + make_heap 实现Priority Queue 使用 stl built-in 的 PQ Lec 3 Amortized complexity Lec 5 - Recursion Fourth Condition of Master Thm Algorithm Problem: 2D table search Lec 6 - Arrays & Containers 2D dynamic array with double ptr Pros and Cons of fixed/dymc array C++11 range-based for loop Algorithm Problem: Finding the majority element Containers 使用 double ptr instead of random access to traversal What to Store/Get in a container Use dynamic array in C++ Best deep copy 方法：copy-swap method C++11: Move ctor for r-value Move syntax 的好处 Array class operation: [] 和 insert Lab 2 Algorithm Problem: Find 1/k ^th element of Linked List Algorithm Problem: Sort a Stack Algorithm Problem: 用两个 stack 写一个 queue Lec 7 - STL Types of Iterators STL: 每个容器都支持的 iterators Memory overhead simple syntax for 3 dim vector Functor Lambda 使用 lambda 表达式起到 functor 一样的作用 captures list 的用例 Algorithm problem: functor std::random Lec 8 - Heap & PQ & Heapsort tree Complete Binary tree: 可以用 array 表示 Heap-ordered tree Heap Alter element: fixup(), fixdown() 以保持 Heap 结构 Priority Queue Heapify Algorithm: Heapsort Lec 9 - ordered & sorted containers Types of Containers Complexities of array/list based Binary Search Binary Search on array Speed up BS lower_bound(), upper_bound() Representing sets Complexity of set operations Representing disjoint set: Union-Find naive union-find set path compression && rank: 优化 union-find set 复杂度分析 Lec 10 Elementary Sorting Size 如何影响 sorting 策略 Exercise: swap Stability Adaptivity 自适应性 Bubble Sort adaptive Bubble Sort Analysis Selection Sort adaptive Selection Sort Analysis Insertion Sort imprved adaptive Insertion Sort Analysis Elementary Sorting 对比分析 Lec 11: Quicksort partition middle-partition quicksort recursion Analysis time memory a little improvement: 先 sort smaller part a little improvement on Partition: median sampling 混合其他 sort 来提高 heapsort 效率 Lec 12: Mergesort Ternary Operator Merge Modified: merge into itself Top-down merge sort Analysis Lec 13 strings and seqs std::equal Algorithm Problem: equal() with customizable operator==() example using equal(): palindreme Lexicographic Comparison Algorithm Problem: remove duplicate Lab 5 (Sorting) Algorithm Problem: sort 一个 0,1,2 组成的 vector, O(n) time, O(1) space Lab 6 (Maps and sets) Algorithm Problem: two pair sum Algorithm Problem: find first non-repeated integer Lec 15: hashing dictionary ADT Ideas to build a dict hash function translate floatng pts translate int translate string Compression Lec 16: Hash Collision Resolution Lab 7 Hashing Lec 17 (Trees) Def && Property of trees Types: Simple(Undirected) / Rooted(Directed) Binary Tree 的 array implementation Binary Tree 的 pointer-based implementation Thinking: add parent ? Transfrom a tree into Binary tree Binary Tree Traversal DFS (Preorder, Inorder, postorder) BFS (levelorder) Lec 18 (BST & AVL tree) binary search on BST insert in BST exercise: find min remove in BST when v has both children AVL tree AVL: insert compute balance rotation how to keep balance in AVL Four cases of balance = 2 problem Lec 19 (Graphs) Complete / Dense / Sparse graph Representing a graph: Adjacency matrix 在 C++ 中表示 infty Representing a graph: Adjacency list Adajacency list 表示 directed, weighted graph 常见的 Complexity Analysis DFS 找最短路: 只适用于 tree 性质的图 BFS 找最短路: 只适用于 unweighted graph Dijkstra 找最短路 Proof: Invariant Hypothesis of Dijkstra Naive Dijkstra Dijkstra with PQ Backtracking Dijkstra finding path Lec 20 (MST) Cut Property Corollary: shortest edge for one vertex must be in all MST; in some if unstrict Prim's Algorithm: Using Cut Property Correctness 分析不使用 heap 的朴素 prim 使用 heap 的 Prim Complexity 分析 Minimum-cost egde property Corollary: sorting property Kruskal's Algorithm: Using sorting property 如何检测是否有 cycle: union-find set Lab 09 (Graphs) algorithm problem: decide graph has a cycle Lec 21 (Algorithm Family) Brute-Force && Greedy Algorithm Lec 22 (Backtracking && branch and bound) Backtracking: idea n-queens: 经典 backtracking problem Branch and Bound: Backtracking with optimization Solve TSP with Branch and Bound Approximation Algorithms nearest neighbor + 2opt 优化 insertion Lec 23 (DP) Memoization Fibo: naive and DP Binomial Coefficent DP Knight Moves DP Solve TSP with DP Difference between DP and Divide-and-Conquer Lec 24 (Knapsack and Floyd's algorithm) 0-1 knapsack Floyd's algorithm Lab 10 (DP) Algorithm Problem: Discount DP

cs / data-structures-algorithms

index

知识图谱源文件 ↗

Notes

notes 01 08
notes 09 16
notes 17 25

© 2026 Qiulin. All Rights Reserved. / RSS / Sitemap
Powered by Astro & Fuwari

© 2026 Qiulin. All Rights Reserved. / RSS / Sitemap
Powered by Astro & Fuwari