Skip to content

Jiale's notes

概览

Initializing search

首页
计算机基础
AI 与系统工程
开发与实践
生活记录

Jiale's notes

首页
计算机基础
计算机基础
- 概览
- 计算机系统
  计算机系统
  - 概览
  - CSAPP
    CSAPP
    
    CSAPP Lab Ref
- 算法与数据结构
  算法与数据结构
  - 概览
  - I Foundations
    I Foundations
    
    1 The Role of Algorithms in Computing
    1 The Role of Algorithms in Computing
    
    1.1 Algorithms
    
    1.2 Algorithms as a technology
    
    Chap 1 Problems
    Chap 1 Problems
    
    Problem 1-1
    
    2 Getting Started
    2 Getting Started
    
    2.1 Insertion sort
    
    2.2 Analyzing algorithms
    
    2.3 Designing algorithms
    
    Chap 2 Problems
    Chap 2 Problems
    
    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 Growth of Functions
    3 Growth of Functions
    
    3.1 Asymptotic notation
    
    3.2 Standard notations and common functions
    
    Chap 3 Problems
    Chap 3 Problems
    
    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 Divide-and-Conquer
    4 Divide-and-Conquer
    
    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
    
    Chap 4 Problems
    Chap 4 Problems
    
    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 Probabilistic Analysis and Randomized Algorithms
    5 Probabilistic Analysis and Randomized Algorithms
    
    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
    
    Chap 5 Problems
    Chap 5 Problems
    
    5-1 Probabilstic counting
    
    5-2 Searching an unsorted array
  - II Sorting and Order Statistics
    II Sorting and Order Statistics
    
    6 Heapsort
    6 Heapsort
    
    6.1 Heaps
    
    6.2 Maintaining the heap property
    
    6.3 Building a heap
    
    6.4 The heapsort algorithm
    
    6.5 Priority queues
    
    Chap 6 Problems
    Chap 6 Problems
    
    6-1 Building a heap using insertion
    
    6-2 Analysis of $d$-ary heaps
    
    6-3 Young tableaus
    
    7 Quicksort
    7 Quicksort
    
    7.1 Description of quicksort
    
    7.2 Performance of quicksort
    
    7.3 A randomized version of quicksort
    
    7.4 Analysis of quicksort
    
    Chap 7 Problems
    Chap 7 Problems
    
    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 Sorting in Linear Time
    8 Sorting in Linear Time
    
    8.1 Lower bounds for sorting
    
    8.2 Counting sort
    
    8.3 Radix sort
    
    8.4 Bucket sort
    
    Chap 8 Problems
    Chap 8 Problems
    
    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 Medians and Order Statistics
    9 Medians and Order Statistics
    
    9.1 Minimum and maximum
    
    9.2 Selection in expected linear time
    
    9.3 Selection in worst-case linear time
    
    Chap 9 Problems
    Chap 9 Problems
    
    9-1 Largest $i$ numbers in sorted order
    
    9-2 Weighted median
    
    9-3 Small order statistics
    
    9-4 Alternative analysis of randomized selection
  - III Data Structures
    III Data Structures
    
    10 Elementary Data Structures
    10 Elementary Data Structures
    
    10.1 Stacks and queues
    
    10.2 Linked lists
    
    10.3 Implementing pointers and objects
    
    10.4 Representing rooted trees
    
    Chap 10 Problems
    Chap 10 Problems
    
    10-1 Comparisons among lists
    
    10-2 Mergeable heaps using linked lists
    
    10-3 Searching a sorted compact list
    
    11 Hash Tables
    11 Hash Tables
    
    11.1 Direct-address tables
    
    11.2 Hash tables
    
    11.3 Hash functions
    
    11.4 Open addressing
    
    11.5 Perfect hashing
    
    Chap 11 Problems
    Chap 11 Problems
    
    11-1 Longest-probe bound for hashing
    
    11-2 Slot-size bound for chaining
    
    11-3 Quadratic probing
    
    11-4 Hashing and authentication
    
    12 Binary Search Trees
    12 Binary Search Trees
    
    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
    
    Chap 12 Problems
    Chap 12 Problems
    
    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 Red-Black Trees
    13 Red-Black Trees
    
    13.1 Properties of red-black trees
    
    13.2 Rotations
    
    13.3 Insertion
    
    13.4 Deletion
    
    Chap 13 Problems
    Chap 13 Problems
    
    13-1 Persistent dynamic sets
    
    13-2 Join operation on red-black trees
    
    13-3 AVL trees
    
    13-4 Treaps
    
    14 Augmenting Data Structures
    14 Augmenting Data Structures
    
    14.1 Dynamic order statistics
    
    14.2 How to augment a data structure
    
    14.3 Interval trees
    
    Chap 14 Problems
    Chap 14 Problems
    
    14-1 Point of maximum overlap
    
    14-2 Josephus permutation
  - IV Advanced Design and Analysis Techniques
    IV Advanced Design and Analysis Techniques
    
    15 Dynamic Programming
    15 Dynamic Programming
    
    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
    
    Chap 15 Problems
    Chap 15 Problems
    
    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 Greedy Algorithms
    16 Greedy Algorithms
    
    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
    
    Chap 16 Problems
    Chap 16 Problems
    
    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 Amortized Analysis
    17 Amortized Analysis
    
    17.1 Aggregate analysis
    
    17.2 The accounting method
    
    17.3 The potential method
    
    17.4 Dynamic tables
    
    Chap 17 Problems
    Chap 17 Problems
    
    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
  - V Advanced Data Structures
    V Advanced Data Structures
    
    18 B-Trees
    18 B-Trees
    
    18.1 Definition of B-trees
    
    18.2 Basic operations on B-trees
    
    18.3 Deleting a key from a B-tree
    
    Chap 18 Problems
    Chap 18 Problems
    
    18-1 Stacks on secondary storage
    
    18-2 Joining and splitting 2-3-4 trees
    
    19 Fibonacci Heaps
    19 Fibonacci Heaps
    
    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
    
    Chap 19 Problems
    Chap 19 Problems
    
    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 van Emde Boas Trees
    20 van Emde Boas Trees
    
    20.1 Preliminary approaches
    
    20.2 A recursive structure
    
    20.3 The van Emde Boas tree
    
    Chap 20 Problems
    Chap 20 Problems
    
    20-1 Space requirements for van Emde Boas trees
    
    20-2 $y$-fast tries
    
    21 Data Structures for Disjoint Sets
    21 Data Structures for Disjoint Sets
    
    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
    
    Chap 21 Problems
    Chap 21 Problems
    
    21-1 Off-line minimum
    
    21-2 Depth determination
    
    21-3 Tarjan's off-line least-common-ancestors algorithm
  - VI Graph Algorithms
    VI Graph Algorithms
    
    22 Elementary Graph Algorithms
    22 Elementary Graph Algorithms
    
    22.1 Representations of graphs
    
    22.2 Breadth-first search
    
    22.3 Depth-first search
    
    22.4 Topological sort
    
    22.5 Strongly connected components
    
    Chap 22 Problems
    Chap 22 Problems
    
    22-1 Classifying edges by breadth-first search
    
    22-2 Articulation points, bridges, and biconnected components
    
    22-3 Euler tour
    
    22-4 Reachability
    
    23 Minimum Spanning Trees
    23 Minimum Spanning Trees
    
    23.1 Growing a minimum spanning tree
    
    23.2 The algorithms of Kruskal and Prim
    
    Chap 23 Problems
    Chap 23 Problems
    
    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 Single-Source Shortest Paths
    24 Single-Source Shortest Paths
    
    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
    
    Chap 24 Problems
    Chap 24 Problems
    
    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 All-Pairs Shortest Paths
    25 All-Pairs Shortest Paths
    
    25.1 Shortest paths and matrix multiplication
    
    25.2 The Floyd-Warshall algorithm
    
    25.3 Johnson's algorithm for sparse graphs
    
    Chap 25 Problems
    Chap 25 Problems
    
    25-1 Transitive closure of a dynamic graph
    
    25-2 Shortest paths in epsilon-dense graphs
    
    26 Maximum Flow
    26 Maximum Flow
    
    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
    
    Chap 26 Problems
    Chap 26 Problems
    
    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
  - VII Selected Topics
    VII Selected Topics
    
    27 Multithreaded Algorithms
    27 Multithreaded Algorithms
    
    27.1 The basics of dynamic multithreading
    
    27.2 Multithreaded matrix multiplication
    
    27.3 Multithreaded merge sort
    
    Chap 27 Problems
    Chap 27 Problems
    
    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 Matrix Operations
    28 Matrix Operations
    
    28.1 Solving systems of linear equations
    
    28.2 Inverting matrices
    
    28.3 Symmetric positive-definite matrices and least-squares approximation
    
    Chap 28 Problems
    Chap 28 Problems
    
    28-1 Tridiagonal systems of linear equations
    
    28-2 Splines
    
    29 Linear Programming
    29 Linear Programming
    
    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
    
    Chap 29 Problems
    Chap 29 Problems
    
    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 Polynomials and the FFT
    30 Polynomials and the FFT
    
    30.1 Representing polynomials
    
    30.2 The DFT and FFT
    
    30.3 Efficient FFT implementations
    
    Chap 30 Problems
    Chap 30 Problems
    
    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 Number-Theoretic Algorithms
    31 Number-Theoretic Algorithms
    
    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
    
    Chap 31 Problems
    Chap 31 Problems
    
    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 String Matching
    32 String Matching
    
    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
    
    Chap 32 Problems
    Chap 32 Problems
    
    32-1 String matching based on repetition factors
    
    33 Computational Geometry
    33 Computational Geometry
    
    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
    
    Chap 33 Problems
    Chap 33 Problems
    
    33-1 Convex layers
    
    33-2 Maximal layers
    
    33-3 Ghostbusters and ghosts
    
    33-4 Picking up sticks
    
    33-5 Sparse-hulled distributions
    
    34 NP-Completeness
    34 NP-Completeness
    
    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
    
    Chap 34 Problems
    Chap 34 Problems
    
    34-1 Independent set
    
    34-2 Bonnie and Clyde
    
    34-3 Graph coloring
    
    34-4 Scheduling with profits and deadlines
    
    35 Approximation Algorithms
    35 Approximation Algorithms
    
    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
    
    Chap 35 Problems
    Chap 35 Problems
    
    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
- 数据库
  数据库
  - 概览
  - CMU IntroToDatabaseSystems(2021)
    CMU IntroToDatabaseSystems(2021)
    
    L1 Relational Model & Relational Algebra
    
    L2 Intermediate SQL
    
    Homework1 SQL
    
    L3 Database Storage (Part I)
    
    L4 Database Storage (Part II)
    
    L5 Buffer Pools
AI 与系统工程
AI 与系统工程
- 概览
- 系统学习大纲
- Transformer 从原理到推理系统
  Transformer 从原理到推理系统
- 高性能计算
- 开源项目调研
  开源项目调研
  - 概览概览
    Table of contents
    
    内容导航
    
    向量检索
    
    推理服务
  - 向量检索
    向量检索
    
    Faiss 项目调研
    
    Faiss 源码与 API 导读
  - 推理服务
    推理服务
    
    SGLang 项目调研
    
    SGLang 源码与 API 导读
开发与实践
开发与实践
- 概览
- 编程语言
  编程语言
  - Python 环境
  - SQL
    SQL
    
    SQL 工作原理
    
    SQL 基础
- 开发工具
  开发工具
  - Makefile 入门
  - tmux
  - Vim
  - QM Server
- 编程练习
  编程练习
  - 算法笔记
  - 链表、栈与队列
    链表、栈与队列
    
    单链表
    
    反转链表
    
    相交链表
    
    合并两个有序列表
- 项目实践
  项目实践
  - 概览
  - CSE 160
生活记录
生活记录
- 概览
- 音乐
  音乐
  - JoJo

Table of contents

内容导航
- 向量检索
- 推理服务

开源项目调研

阅读 Faiss、SGLang 的架构、源码与 API，理解工程实现。

内容导航

向量检索

Faiss 项目调研
Faiss 源码与 API 导读

推理服务

SGLang 项目调研
SGLang 源码与 API 导读

返回AI 与系统工程 · 返回首页

Previous 高性能计算

Next Faiss 项目调研

Made with Material for MkDocs