比特运算（Bitwise operations）是直接对整数的二进制位进行操作的运算。在Python中，比特运算符可以用来执行按位与（AND）、按位或（OR）、按位异或（XOR）、按位非（NOT）、左移（左移位）和右移（右移位）等操作。
Brian Kernighan算法是一种用于高效计算一个整数中二进制表示下1的个数的算法。这个算法的核心思想是利用位运算来快速减少计数的过程。算法基于这样一个观察：对于任意一个非零整数n，n和n-1进行按位与操作（n & (n - 1)）的结果会将n的二进制表示中最右边的一个1变为0。
通过与1进行按位与操作可以取得最右位并且判断一个数是奇数还是偶数。通过与(n-1)进行按位与操作可以清零最低位的1。对于十进制整数 x，我们可以用 x & (1 << k) 来判断 x 二进制表示的第 k 位（最低位为第 0 位）是否为 1。
前缀树（Trie树），也称为字典树或单词查找树，是一种树形数据结构，专门用于高效存储和检索字符串集合中的词项。
前缀树是一种多叉树结构，其中每个节点代表一个字符串前缀，从根节点到任一节点的路径上的字符序列构成该节点对应的前缀。
搜索引擎使用前缀树来快速检索和匹配用户输入的查询词。当用户输入一个查询词时，搜索引擎可以从前缀树的根节点开始，根据查询词中的字符逐个向下遍历节点，直到找到匹配的单词或其前缀。
搜索引擎可以利用前缀树提供自动补全建议和拼写检查。由于前缀树存储了大量的单词和它们的前缀，搜索引擎可以快速地根据用户已经输入的部分单词（前缀）给出完整的单词建议，或者指出拼写错误并提供正确的拼写。
1 | class Trie: |
堆是一种特殊的树形数据结构，通常使用数组来实现。堆具有以下特性：堆是一棵完全二叉树（Complete Binary Tree），即除了最后一层外，每一层都被填满，最后一层的节点都靠左排列。
最大堆（Max Heap）：父节点的值总是大于或等于其子节点的值。
最小堆（Min Heap）：父节点的值总是小于或等于其子节点的值。
优先级队列（Priority Queue）是一种特殊的队列，其中每个元素都有一个优先级。元素的出队顺序取决于其优先级，而不是进入队列的先后顺序。
二叉树（Binary Tree）是一种常用的数据结构，在计算机科学中有广泛的应用。它是一种非线性数据结构，每个节点最多有两个子节点，通常这两个子节点被称为左子节点（left child）和右子节点（right child）。
有一些特别的二叉树，满二叉树就是每一层节点都是满的，除了叶子节点外，每个节点都有两个子节点。假设深度为 h，那么总节点数就是$2^h - 1$。 完全二叉树是指，二叉树的每一层的节点都紧凑靠左排列，且除了最后一层，其他每层都必须是满的，完全二叉树的特点：由于它的节点紧凑排列，如果从左到右从上到下对它的每个节点编号，那么父子节点的索引存在明显的规律。平衡二叉树中任何两个叶子节点的高度差不大于 1，二叉搜索树（Binary Search Tree，简称 BST）是一种很常见的二叉树，它的定义是：对于树中的每个节点，其左子树的每个节点的值都要小于这个节点的值，右子树的每个节点的值都要大于这个节点的值。
二叉树的递归遍历是一种常用的遍历方式，它利用递归来访问树中的所有节点。二叉树的递归遍历主要有三种方式：前序遍历（Preorder）、中序遍历（Inorder）和后序遍历（Postorder）。前序遍历的顺序是：先访问根节点，然后递归地遍历左子树，最后递归地遍历右子树。中序遍历的顺序是：递归地遍历左子树，然后访问根节点，最后递归地遍历右子树。后序遍历的顺序是：递归地遍历左子树，然后递归地遍历右子树，最后访问根节点。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class TreeNode:
def __init__(self, value=0, left=None, right=None):
self.value = value
self.left = left
self.right = right
def preorder_traversal(root):
if root is None:
return []
result = []
_preorder_helper(root, result)
return result
def _preorder_helper(node, result):
if node:
result.append(node.value) # 访问节点
_preorder_helper(node.left, result) # 遍历左子树
_preorder_helper(node.right, result) # 遍历右子树
二叉树的层序遍历，顾名思义，就是一层一层地遍历二叉树。这个遍历方式需要借助队列来实现。
Big O notation measures the asymptotic growth of a function. f (n) = O(g(n)) if for all sufficiently large n, f (n) is at most a constant factor larger than g(n).
We say f (n) = Ω(g(n)) if g(n) = O(f (n)).
We say f (n) = Θ(g(n)) if f (n) = O(g(n)) and g(n) = O(f (n)).
Worst-case complexity: what is the largest possible running time on any input of size n?
Average-case complexity: what is the average running time on a random input of size n?
Best-case complexity: what is the smallest possible running time on any input of size n?
For graph with n vertices this is an n × n matrix A, where $A{ij}$ = 1 if there is an edge from node i to node j, $A{ij}$ = 0 otherwise.
If the graph is undirected, the matrix is symmetric
For each vertex, keep a list of its neighbors.
The incidence matrix of an undirected graph with n vertices and m edges is an n × m matrix B where $B{ij}$ = 1 if the i’th vertex is part of the j’th edge, $B{ij}$ = 0 otherwise.
For the BFS tree, this gives the shortest (fewest number of steps) paths from s to all other nodes
Greedy algorithms are algorithms that build a solution step by step by always choosing the currently best option.
Input: A list of intervals
Output: Maximum number of these intervals that can be chosen without getting any overlaps.
Solution:Pick the one that ends first.
Prove correctness of such an algorithm: Common strategy for analyzing greedy algorithms: prove that the algorithm always “stays ahead” of the optimal solution.
Input: A list of jobs, each job has a deadline di
, and a duration ti
(how long it takes to finish the job)
Output: Smallest possible maximum lateness in a schedule for doing
all jobs.
Solution: Pick the job with smallest di.
It is helpful to instead consider a more general problem. Let us try
to find the shortest paths from s to all other vertices: Dijkstra’s algorithm: we have some set D of vertices we have found
the shortest path to, and each step we add a new vertex to D. add the vertex outside D which is closest to
s when using only vertices in D as intermediate vertices.
Algorithms that split the input into significantly smaller parts, recursively solves each part, and then combines the subresults (somehow).
O(n log n).
$T(n) = O(n^{1.59})$.
Using FFT, get time O(n log n) for Polynomial Multiplication
Unit cost model: assume all numbers fit in machine registers so that basic arithmetic operations take constant time.
Bit cost model: account for size of numbers and the time it takes to manipulate them.
Karatsuba’s algorithm: $T(n) = O(n^{1.59})$.
Split a problem into smaller subproblems such that results from one
subproblem can be reused when solving others
The Fibonacci numbers are a classic number sequence in
mathematics, defined by the linear recurrence
f0 = 0; f1 = 1; and fn = fn−1 + fn−2 for n ≥ 2
Input: A list of intervals [s1; t1]; [s2; t2]; : : : ; [sn; tn], each interval
[si
; ti
] has a weight wi
Output: What is the maximum total weight of these intervals that
can be chosen without getting any overlaps
Input: A capacity C and a list of objects, each object has a value vi
and weight wi
Output: Subset S of objects such that
$\sum{i∈S} wi ≤ C$ and $\sum{i∈S} vi$ is maximized.
top-down fashion: we start at the end result and
recursively compute results for relevant subproblems.
bottom-up fashion: we iteratively compute results for larger and larger subproblems.
A problem is amenable to dynamic program if we can define a set
of subproblems such that:
Input: Strings x and y of lengths m and n, parameters ‹ and ¸
Output: Minimum cost of an alignment of x and y with parameters $\sigma$ and $\alpha$.
$\alpha is the cost of aligning two different characters with each other
$\sigma$ is the cost of not aligning a character
Input: Flow network G.
Output: Flow f maximizing the value v(f ).
Solution: The Ford-Fulkerson Algorithm O(C(m + n))
or the scaling algorithm with O(m2
log(C)) or Edmonds-Karp algorithm with O(nm(n + m)) .
An edge cut of a graph is a set of edges such that their removal would disconnect the graph.
Input: A flow network G with source s and sink t.
Output: An s-t cut A; B of G minimizing the capacity c(A; B).
For every flow network G, the maximum flow from s to t equals the
minimum capacity of an s-t cut in G.
A vertex cut in a graph is a set of vertices such that if we remove
them, the graph splits into more than one connected component.
A matching in a graph is a set M of edges such that no vertex appears in more than one edge of M.Of particular interest to us will be bipartite graphs.
Input: A bipartite graph G
Output: A matching M in G of maximum possible size.
Given a directed graph with source and sink, what is maximum
number of edge-disjoint paths from s to t?
(edge-disjoint = no edge used by more than one path)
Turing Machines and Undecidability
Turing machines are primarily a mathematical construction. A Turing machine (TM) consists of:A finite set of states: initial state(when the TM starts, it is in this state) and accepting states(if the TM ends in one of these states, it says yes); Transition rules that determine what to do based on current state and content of memory tape at current position; An alphabet, the set of symbols that can be stored on the memory tape.
Anything which can be computed by any automatic method, can also be computed by a Turing machine.
If a model can also do everything that a Turing machine can, then it is called a Turing-complete model of computation.
Models the way modern computers operate, with registers and memory cells that can be immediately accessed.
We will prove that any such algorithm must make Ω(n log n)
comparisons (and thus take Ω(n log n) time)
The answer is just a single bit of information,“yes” or “no”.A decision problem is decidable if there exists an algorithm for solving the problem without any efficiency considerations.
Turing machine M, and input x to M. Does M halt when run on the input x?
The Halting Problem is undecidable.
It is undecidable.
It is undecidable.
There exists an “algorithm” which terminates whenever the answer is
“yes” but does not terminate on “no” instances.Problems which have algorithms like this are called recursively enumerable.
A Turing reduction (also called Cook reduction) from a problem
X to a problem Y is an efficient algorithm for problem X which is
allowed to assume an algorithm for Y as a black box.
X ≤p Y if given any instance A of problem X, we can in
polynomial time construct an instance f (A) of problem Y such that
the answer to A is the same as the answer to f (A).
Turing reduction is a type of reduction that is stronger than Karp reduction. A problem A is Turing-reducible to problem B if there exists a Turing machine that can solve problem A by making a polynomial number of calls to a black-box subroutine for problem B. In other words, if we can use an algorithm for problem B to solve problem A, then A is Turing-reducible to B. Turing reduction preserves the complexity class of a problem, meaning that if A is Turing-reducible to B and B is in a certain complexity class, then A is also in that complexity class.
Karp reduction, also known as polynomial-time reduction, is a weaker form of reduction than Turing reduction. A problem A is Karp-reducible to problem B if there exists a polynomial-time algorithm that can transform any instance of problem A into an instance of problem B such that the answer to the transformed instance is the same as the answer to the original instance of problem A. In other words, if we can use an algorithm for problem B to solve a transformed version of problem A in polynomial time, then A is Karp-reducible to B. Karp reduction preserves the complexity class up to polynomial factors, meaning that if A is Karp-reducible to B and B is in a certain complexity class, then A is also in that complexity class up to polynomial factors.
https://www.cs.rochester.edu/u/nelson/courses/csc_173/computability/undecidable.html
http://www2.lawrence.edu/fast/GREGGJ/CMSC515/chapt05/Reducibility.html
https://www.cs.princeton.edu/courses/archive/spring05/cos423/lectures.php
A randomized algorithm is an algorithm that uses randomness to
make some of its choices.
A Las Vegas algorithm is a randomized algorithm that always finds
the correct answer, but the running time of the algorithm might
vary significantly depending on the random choices made.
A Monte Carlo algorithm is a randomized algorithm where the
output of the algorithm may be incorrect, but we have a guarantee
that this only happens with small probability.
True RNG: gets randomness from measuring physical phenomena
(e.g. background radiation) that we believe is sufficiently random
Pseudo-RNG: starting from a small random seed, new numbers are
generated in a completely deterministic way.
while G has more than 2 vertices:Pick a uniformly random edge of G and contract it.
the total runtime is $O(n^2m)$. However this algorithm can be refined and running time improved to $O(n^2log(n))$ (relatively simple algorithm) or
$O(m log^3(n))$ (more complicated algorithm).
Partition of vertices of G into two non-empty sets A and B such that number of edges between A and B is maximized. It is a NP-hard problem. Let us lower the ambition and try to find a fast algorithm that finds a “reasonably good” cut: Random algorithm:Put each vertex in either A or B independently with probability 1/2.The random assignment algorithm cuts (in expectation) at least half of all the edges in the graph.This is an example of an approximation algorithm.
Work well in some or even many cases, but with no guarantees
about how well they perform.
Algorithms with provable guarantee that the solution found is relatively good compared to the optimum solution, for all instances.
For a minimization problem, an algorithm has approximation ratio $\alpha ≥ 1$ if for every instance it holds that $ Alg ≤ \alpha Opt$.
For a maximization problem, the inequality goes the other way: we have approximation ratio $\alpha ≤ 1$ if $ Alg ≥ \alpha Opt$.
approximation ratio: $\alpha$.
NP-hard problem.
Given Lengths t1; : : : ; tn of n jobs to be run on m machines, to find Minimum possible makespan of a schedule for the n jobs.
Approximation Algorithm for Load Balancing:Assign job i to the machine j with the smallest load.
The main difficulty in analyzing approximation
algorithms is to get some handle on the Opt value. We need to find Opt, but finding Opt is NP-hard, so we find lower bounds on Opt.
A vertex cover in a graph G is a set of vertices that “touches” every edge of G.What is the size of a minimum vertex cover of G? Approximation Algorithm for Minimum Vertex Cover:while there exists an edge e = (u; v) such that u /∈ S and v /∈ S, add (u,v) into S. The algorithm is a 2-approximation algorithm.
“Unique Games Conjecture”: it is known that Vertex Cover cannot be approximated better than
within a factor 2.
A collection of sets S1; : : : ; Sm ⊆ U over some universe U, What is minimum number of Si’s whose union equals U?
选择排序的思路是找到数组中最小的数和第一个元素交换位置，然后在剩下的元素中找到最小的元素和第二个元素交换位置，
直到最后只剩一个元素，这样就是一个从小到大排好序的数组。选择排序的复杂度为O(n^2)。
插入排序的思路是将元素插入一个已经排好序的子列表中，直到整个列表都排序完成。插入排序的复杂度为O(n^2)。
冒泡排序的思路是每次对连续的邻居元素进行比较，两个元素是逆序排序就交换位置，否则保持不变，直到所有元素都被排序好。每次进行完一轮比较，就能将最大或者最小的元素移到其最终的位置上，当不再发生交换的时候，就说明元素已经被排好序了，冒泡排序的复杂度是O(n^2)。
归并排序的思路是利用递归的方法，将数组分为两半，各自进行归并排序的过程。其关键是如何将排好序的两个子数组也排好序，鉴于两个子数组是已经排好序了的，只需要将两个子数组依次比较。归并排序的复杂度是O(nlogn）。
快速排序的思路是挑出一个中心点，把数组分为两半，其中一半所有元素都小于这个中心点，另一半大于这个中心点，再对这两半进行递归处理，所以快速排序的关键在于这个中心点的选择了。快速排序的复杂度是O(nlogn）。
堆排序用了二叉堆，将一个数组中的所有元素添加到堆中，然后将堆中最大的元素连续移除以获得一个排好序的数组。一个二叉堆具有如下性质：是一个完全二叉树；每个节点都大于或等于它的子节点，二叉堆通常是用数组实现的，父母节点和子节点的位置满足一定的关系，假如一个在位置i的节点，它的左子节点就在位置2i+1上，右子节点在位置2i+2上。所以堆排序的关键在于二叉堆的建立和维护。堆排序的复杂度是O(nlogn)。
桶排序和基数排序用于排序整数非常有效。
桶排序的思路是加入数组中的元素在0到t的范围内，则把这些元素放入对应的标记上0到t的桶当中，每个桶中的元素值都是相同的。
基数排序
在桶排序中，如果元素范围过大的话，就会需要很多桶，此时就可以用基数排序。基数排序基于桶排序，只是基数排序只会用到十个桶，基于基数位置进行桶排序。
当数据量大到无法一次性载入内存时，使用外排序。外排序的思路就是将大量数据拆分成小块数据，小块数据进行内排序之后，再分别合并排序。
数组一旦创建了，大小就是固定的。
java中声明数组变量的语法是’elementType[] arrayRefVar;’，声明数组只是创造了一个数组引用的存储位置，并没有为这个数组分配内存，创建一个数组可以使用new操作符，
例如’array RefVar = new elementType[arraySize];’。