Jiale's notes
CSAPP Lab Ref
Initializing search
    • 首页
    • 计算机基础
    • AI 与系统工程
    • 开发与实践
    • 生活记录
    • 首页
      • 概览
        • 概览
          • CSAPP Lab Ref
        • 概览
            • 1.1 Algorithms
            • 1.2 Algorithms as a technology
              • Problem 1-1
            • 2.1 Insertion sort
            • 2.2 Analyzing algorithms
            • 2.3 Designing algorithms
              • 2-1 Insertion sort on small arrays in merge sort
              • 2-2 Correctness of bubblesort
              • 2-3 Correctness of Horner's rule
              • 2-4 Inversions
            • 3.1 Asymptotic notation
            • 3.2 Standard notations and common functions
              • 3-1 Asymptotic behavior of polynomials
              • 3-2 Relative asymptotic growths
              • 3-3 Ordering by asymptotic growth rates
              • 3-4 Asymptotic notation properties
              • 3-5 Variations on $O$ and $\Omega$
              • 3-6 Iterated functions
            • 4.1 The maximum-subarray problem
            • 4.2 Strassen's algorithm for matrix multiplication
            • 4.3 The substitution method for solving recurrences
            • 4.4 The recursion-tree method for solving recurrences
            • 4.5 The master method for solving recurrences
            • 4.6 Proof of the master theorem
              • 4-1 Recurrence examples
              • 4-2 Parameter-passing costs
              • 4-3 More recurrence examples
              • 4-4 Fibonacci numbers
              • 4-5 Chip testing
              • 4-6 Monge arrays
            • 5.1 The hiring problem
            • 5.2 Indicator random variables
            • 5.3 Randomized algorithms
            • 5.4 Probabilistic analysis and further uses of indicator random variables
              • 5-1 Probabilstic counting
              • 5-2 Searching an unsorted array
            • 6.1 Heaps
            • 6.2 Maintaining the heap property
            • 6.3 Building a heap
            • 6.4 The heapsort algorithm
            • 6.5 Priority queues
              • 6-1 Building a heap using insertion
              • 6-2 Analysis of $d$-ary heaps
              • 6-3 Young tableaus
            • 7.1 Description of quicksort
            • 7.2 Performance of quicksort
            • 7.3 A randomized version of quicksort
            • 7.4 Analysis of quicksort
              • 7-1 Hoare partition correctness
              • 7-2 Quicksort with equal element values
              • 7-3 Alternative quicksort analysis
              • 7-4 Stack depth for quicksort
              • 7-5 Median-of-3 partition
              • 7-6 Fuzzy sorting of intervals
            • 8.1 Lower bounds for sorting
            • 8.2 Counting sort
            • 8.3 Radix sort
            • 8.4 Bucket sort
              • 8-1 Probabilistic lower bounds on comparison sorting
              • 8-2 Sorting in place in linear time
              • 8-3 Sorting variable-length items
              • 8-4 Water jugs
              • 8-5 Average sorting
              • 8-6 Lower bound on merging sorted lists
              • 8-7 The $0$-$1$ sorting lemma and columnsort
            • 9.1 Minimum and maximum
            • 9.2 Selection in expected linear time
            • 9.3 Selection in worst-case linear time
              • 9-1 Largest $i$ numbers in sorted order
              • 9-2 Weighted median
              • 9-3 Small order statistics
              • 9-4 Alternative analysis of randomized selection
            • 10.1 Stacks and queues
            • 10.2 Linked lists
            • 10.3 Implementing pointers and objects
            • 10.4 Representing rooted trees
              • 10-1 Comparisons among lists
              • 10-2 Mergeable heaps using linked lists
              • 10-3 Searching a sorted compact list
            • 11.1 Direct-address tables
            • 11.2 Hash tables
            • 11.3 Hash functions
            • 11.4 Open addressing
            • 11.5 Perfect hashing
              • 11-1 Longest-probe bound for hashing
              • 11-2 Slot-size bound for chaining
              • 11-3 Quadratic probing
              • 11-4 Hashing and authentication
            • 12.1 What is a binary search tree?
            • 12.2 Querying a binary search tree
            • 12.3 Insertion and deletion
            • 12.4 Randomly built binary search trees
              • 12-1 Binary search trees with equal keys
              • 12-2 Radix trees
              • 12-3 Average node depth in a randomly built binary search tree
              • 12-4 Number of different binary trees
            • 13.1 Properties of red-black trees
            • 13.2 Rotations
            • 13.3 Insertion
            • 13.4 Deletion
              • 13-1 Persistent dynamic sets
              • 13-2 Join operation on red-black trees
              • 13-3 AVL trees
              • 13-4 Treaps
            • 14.1 Dynamic order statistics
            • 14.2 How to augment a data structure
            • 14.3 Interval trees
              • 14-1 Point of maximum overlap
              • 14-2 Josephus permutation
            • 15.1 Rod cutting
            • 15.2 Matrix-chain multiplication
            • 15.3 Elements of dynamic programming
            • 15.4 Longest common subsequence
            • 15.5 Optimal binary search trees
              • 15-1 Longest simple path in a directed acyclic graph
              • 15-2 Longest palindrome subsequence
              • 15-3 Bitonic euclidean
              • 15-4 Printing neatly
              • 15-5 Edit distance
              • 15-6 Planning a company party
              • 15-7 Viterbi algorithm
              • 15-8 Image compression by seam carving
              • 15-9 Breaking a string
              • 15-10 Planning an investment strategy
              • 15-11 Inventory planning
              • 15-12 Signing free-agent baseball players
            • 16.1 An activity-selection problem
            • 16.2 Elements of the greedy strategy
            • 16.3 Huffman codes
            • 16.4 Matroids and greedy methods
            • 16.5 A task-scheduling problem as a matroid
              • 16-1 Coin changing
              • 16-2 Scheduling to minimize average completion time
              • 16-3 Acyclic subgraphs
              • 16-4 Scheduling variations
              • 16-5 Off-line caching
            • 17.1 Aggregate analysis
            • 17.2 The accounting method
            • 17.3 The potential method
            • 17.4 Dynamic tables
              • 17-1 Bit-reversed binary counter
              • 17-2 Making binary search dynamic
              • 17-3 Amortized weight-balanced trees
              • 17-4 The cost of restructuring red-black trees
              • 17-5 Competitive analysis of self-organizing lists with move-to-front
            • 18.1 Definition of B-trees
            • 18.2 Basic operations on B-trees
            • 18.3 Deleting a key from a B-tree
              • 18-1 Stacks on secondary storage
              • 18-2 Joining and splitting 2-3-4 trees
            • 19.1 Structure of Fibonacci heaps
            • 19.2 Mergeable-heap operations
            • 19.3 Decreasing a key and deleting a node
            • 19.4 Bounding the maximum degree
              • 19-1 Alternative implementation of deletion
              • 19-2 Binomial trees and binomial heaps
              • 19-3 More Fibonacci-heap operations
              • 19-4 2-3-4 heaps
            • 20.1 Preliminary approaches
            • 20.2 A recursive structure
            • 20.3 The van Emde Boas tree
              • 20-1 Space requirements for van Emde Boas trees
              • 20-2 $y$-fast tries
            • 21.1 Disjoint-set operations
            • 21.2 Linked-list representation of disjoint sets
            • 21.3 Disjoint-set forests
            • 21.4 Analysis of union by rank with path compression
              • 21-1 Off-line minimum
              • 21-2 Depth determination
              • 21-3 Tarjan's off-line least-common-ancestors algorithm
            • 22.1 Representations of graphs
            • 22.2 Breadth-first search
            • 22.3 Depth-first search
            • 22.4 Topological sort
            • 22.5 Strongly connected components
              • 22-1 Classifying edges by breadth-first search
              • 22-2 Articulation points, bridges, and biconnected components
              • 22-3 Euler tour
              • 22-4 Reachability
            • 23.1 Growing a minimum spanning tree
            • 23.2 The algorithms of Kruskal and Prim
              • 23-1 Second-best minimum spanning tree
              • 23-2 Minimum spanning tree in sparse graphs
              • 23-3 Bottleneck spanning tree
              • 23-4 Alternative minimum-spanning-tree algorithms
            • 24.1 The Bellman-Ford algorithm
            • 24.2 Single-source shortest paths in directed acyclic graphs
            • 24.3 Dijkstra's algorithm
            • 24.4 Difference constraints and shortest paths
            • 24.5 Proofs of shortest-paths properties
              • 24-1 Yen's improvement to Bellman-Ford
              • 24-2 Nesting boxes
              • 24-3 Arbitrage
              • 24-4 Gabow's scaling algorithm for single-source shortest paths
              • 24-5 Karp's minimum mean-weight cycle algorithm
              • 24-6 Bitonic shortest paths
            • 25.1 Shortest paths and matrix multiplication
            • 25.2 The Floyd-Warshall algorithm
            • 25.3 Johnson's algorithm for sparse graphs
              • 25-1 Transitive closure of a dynamic graph
              • 25-2 Shortest paths in epsilon-dense graphs
            • 26.1 Flow networks
            • 26.2 The Ford-Fulkerson method
            • 26.3 Maximum bipartite matching
            • 26.4 Push-relabel algorithms
            • 26.5 The relabel-to-front algorithm
              • 26-1 Escape problem
              • 26-2 Minimum path cover
              • 26-3 Algorithmic consulting
              • 26-4 Updating maximum flow
              • 26-5 Maximum flow by scaling
              • 26-6 The Hopcroft-Karp bipartite matching algorithm
            • 27.1 The basics of dynamic multithreading
            • 27.2 Multithreaded matrix multiplication
            • 27.3 Multithreaded merge sort
              • 27-1 Implementing parallel loops using nested parallelism
              • 27-2 Saving temporary space in matrix multiplication
              • 27-3 Multithreaded matrix algorithms
              • 27-4 Multithreading reductions and prefix computations
              • 27-5 Multithreading a simple stencil calculation
              • 27-6 Randomized multithreaded algorithms
            • 28.1 Solving systems of linear equations
            • 28.2 Inverting matrices
            • 28.3 Symmetric positive-definite matrices and least-squares approximation
              • 28-1 Tridiagonal systems of linear equations
              • 28-2 Splines
            • 29.1 Standard and slack forms
            • 29.2 Formulating problems as linear programs
            • 29.3 The simplex algorithm
            • 29.4 Duality
            • 29.5 The initial basic feasible solution
              • 29-1 Linear-inequality feasibility
              • 29-2 Complementary slackness
              • 29-3 Integer linear programming
              • 29-4 Farkas'ss lemma
              • 29-5 Minimum-cost circulation
            • 30.1 Representing polynomials
            • 30.2 The DFT and FFT
            • 30.3 Efficient FFT implementations
              • 30-1 Divide-and-conquer multiplication
              • 30-2 Toeplitz matrices
              • 30-3 Multidimensional fast Fourier transform
              • 30-4 Evaluating all derivatives of a polynomial at a point
              • 30-5 Polynomial evaluation at multiple points
              • 30-6 FFT using modular arithmetic
            • 31.1 Elementary number-theoretic notions
            • 31.2 Greatest common divisor
            • 31.3 Modular arithmetic
            • 31.4 Solving modular linear equations
            • 31.5 The Chinese remainder theorem
            • 31.6 Powers of an element
            • 31.7 The RSA public-key cryptosystem
            • 31.8 Primality testing
            • 31.9 Integer factorization
              • 31-1 Binary gcd algorithm
              • 31-2 Analysis of bit operations in Euclid's algorithm
              • 31-3 Three algorithms for Fibonacci numbers
              • 31-4 Quadratic residues
            • 32.1 The naive string-matching algorithm
            • 32.2 The Rabin-Karp algorithm
            • 32.3 String matching with finite automata
            • 32.4 The Knuth-Morris-Pratt algorithm
              • 32-1 String matching based on repetition factors
            • 33.1 Line-segment properties
            • 33.2 Determining whether any pair of segments intersects
            • 33.3 Finding the convex hull
            • 33.4 Finding the closest pair of points
              • 33-1 Convex layers
              • 33-2 Maximal layers
              • 33-3 Ghostbusters and ghosts
              • 33-4 Picking up sticks
              • 33-5 Sparse-hulled distributions
            • 34.1 Polynomial time
            • 34.2 Polynomial-time verification
            • 34.3 NP-completeness and reducibility
            • 34.4 NP-completeness proofs
            • 34.5 NP-complete problems
              • 34-1 Independent set
              • 34-2 Bonnie and Clyde
              • 34-3 Graph coloring
              • 34-4 Scheduling with profits and deadlines
            • 35.1 The vertex-cover problem
            • 35.2 The traveling-salesman problem
            • 35.3 The set-covering problem
            • 35.4 Randomization and linear programming
            • 35.5 The subset-sum problem
              • 35-1 Bin packing
              • 35-2 Approximating the size of a maximum clique
              • 35-3 Weighted set-covering problem
              • 35-4 Maximum matching
              • 35-5 Parallel machine scheduling
              • 35-6 Approximating a maximum spanning tree
              • 35-7 An approximation algorithm for the 0-1 knapsack problem
        • 概览
          • L1 Relational Model & Relational Algebra
          • L2 Intermediate SQL
          • Homework1 SQL
          • L3 Database Storage (Part I)
          • L4 Database Storage (Part II)
          • L5 Buffer Pools
      • 概览
      • 系统学习大纲
        • 学习入口
        • 一 从序列建模到 Transformer
        • 二 注意力机制的数学推导
        • 三 完整 Transformer 的组成与推导
        • 四 训练目标与自回归生成
        • 五 现代语言模型的结构演进
        • 六 从模型计算图到系统成本
        • 七 模型容量与参数量推导
        • 八 运行时状态与显存
        • 九 Prefill 与 Decode 计算量
        • 十 吞吐与延迟的系统模型
          • 张量形状参考
          • 完整数值案例
          • 练习与答案
        • 学习入口
        • 一 大模型业务与模型位置
        • 二 前向数学与传统卷积对比
        • 三 反向传播的完整推导
        • 四 Dao 接口与源码地图
        • 五 Dao 前向 CUDA 实现
        • 六 Dao 反向 CUDA 实现
        • 七 状态 分块与增量推理
        • 八 MLU 迁移与验证实践
      • 高性能计算
        • 概览
          • Faiss 项目调研
          • Faiss 源码与 API 导读
          • SGLang 项目调研
          • SGLang 源码与 API 导读
      • 概览
        • Python 环境
          • SQL 工作原理
          • SQL 基础
        • Makefile 入门
        • tmux
        • Vim
        • QM Server
        • 算法笔记
          • 单链表
          • 反转链表
          • 相交链表
          • 合并两个有序列表
        • 概览
        • CSE 160
      • 概览
        • JoJo

    CSAPP Lab Ref

    一篇知乎

    Previous 概览
    Next 概览
    Made with Material for MkDocs