Linear lists, stacks, queues, sparse matrices, binary trees, threaded binary trees, Huffman coding, heaps, and sorting algorithms.
The note discusses data structures and algorithms. It mentions:
Chapter 1. Introduction
1.1 Data Abstraction and Binary Relations
$$ A \times B = \{(a, b) \mid a \in A \text{ and } b \in B\} $$
- Extension Concept: n Sets Cartesian Product
- Binary Relations:
- A subset of A × B. A = B is called a binary relation R.
- A × A ⊃ R = {(a, b) | a ∈ A and b ∈ A and satisfy certain conditions}
- Reflexivity: ∀a ∈ A, (a, a) ∈ R; Anti-reflexivity: ∀a ∈ A, (a, a) ∉ R.
- Symmetry: (a, b) ∈ R then (b, a) ∈ R; Anti-symmetry: (a, b) ∈ R and a ≠ b, then (b, a) ∉ R.
- Transitivity: (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R. The relation R is transitive.
- Note: Reflexivity and symmetry + anti-symmetry → anti-symmetry: Counterexample.
- Equivalence Relation: Reflexivity, symmetry, transitivity → equivalence class → partition of the set.
- Partial Order Relation: Reflexivity, anti-symmetry, transitivity: cannot determine whether any element (a, b) ∈ R (ordering)
- Total Order Relation: ∀a, b ∈ A, either (a, b) ∈ R or (b, a) ∈ R, where R is a partial order relation → total order.
- Strict Partial Order Relation (Total Order Relation): Reflexivity, anti-symmetry, transitivity: e.g., ∈.
1.2 Data Structure Basic Concepts
- Data Logical Structure:
- B = (D, R) where D is a set and R is a relation on D. Linear: list; Non-linear: tree, graph.
- Data Storage Structure:
- Sequential, Linked, Index, Array.
1.3 Algorithm Description and Analysis
Brute Force Method: Find the maximum element in A,Knapsack, string matching...
Divide and Conquer Method: Find the maximum element in A,Merge Sort, Quick Sort, Shell Sort...
Greedy Method: Find the maximum element in A,Knapsack, Binary Search, B-tree search...
Backtracking Method: Maze, Knapsack...
Dynamic Programming Method: Floyd、Worshall...
Time Complexity and Space Complexity:
Time: Best/Worst, addition/multiplication;loop/recursion
Chapter 2: Linear List Storage and Operations
2.1 Linear List Concepts
2.2 Linear List Operations
2.3 Stack
if (P is small enough) // Directly solve P;
else
for (i=1; i<=k; i++) y_i = Divide(P_i) // Solve sub-problems
Stack Work: Push: push; Pop: pop; Save local variables, actual parameters, return address.
2.4 Queue
Linear Queue:
$$a_1, a_2, \ldots, a_n \rightarrow i$$
Circular Queue:
$$0 \text{ element at } m-1 \text{ element after. Clear: delete } front = rear = 0$$
Queue Empty:
$$front = rear$$
Queue Full:
$$(rear + 1) \% m = front$$
Priority Queue:
$$\{ \text{New element in queue tail, dequeue highest priority element.} \}$$
2.5 Arrays and Matrix Representation
1. Array Sequential Allocation
Row Major:
$$AD(a_{ij}) = AD(a_{11}) + [(i-1)n + j-1] \cdot unit; AD(a_{ij}) = AD(a_{11}) + (in + j) \cdot unit$$
Column Major:
$$AD(a_{ij}) = AD(a_{11}) + [(j-1)n + i-1] \cdot unit;$$
2. Rule of Matrix Storage
Lower Triangle:
$$\text{Row: } k = \frac{1}{2} i(i-1) + j$$
$$\text{Column: } k = \frac{(2n-i-j)}{2} + i - (j-1)$$
Triangular Matrix:
$$\text{Row: } k = i(i-1)/2 + j, i > j$$
$$\text{Column: } k = (j-1)/2 + i, i < j$$
Triangular Matrix:
$$\text{Row: } eg: \text{Triangular } k = 5(i-1) - 3 + [j - (i-3)], a_{ij} =$$
$$k = \left\{ \begin{array}{ll}
1 & \text{if } i < j \text{ or } i > j \text{ and } i \leq j + \frac{1}{2} \\
0 & \text{else}
\end{array} \right.$$
3. Sparse Matrix in 3D Array Representation - 3D Array Sequential Table B(row, col, value)
$$\{ pos[i,j]: \text{Sparse matrix first non-zero element in B, } pos[i,j] = pos[i-1] + num[i-1]$$
$$num[i,j]: \text{Sparse matrix non-zero element count. } num[B[i,j]] = num[B[i,j]] + 1$$
Chapter 3: Linked Lists
3.1 Linear List's Linked Storage
The reason for using a linked list structure: the length is greater than the continuous space; the length cannot be determined in advance; the length changes frequently.
Insertion special cases: empty list; insert at the first position; cannot find the insertion position.
Deletion special cases: empty list; delete the first element; cannot find the deletion position.
Merge operation: select basic link. O(m+n)
Split operation (based on odd/even): O(n).
3.2 Linked Stack and Linked Queue
top -> [] -> [] -> ... -> []
Empty stack using linked stack storage (static)
[] -> [] -> ... -> []
front -> rear
Empty queue similarly stored (static)
3.3 Circular Linked List
H -> [] -> [a1] -> [a2] -> [a3] -> ... -> [an] -> H
Empty: H -> []
Advantages: empty list does not need special handling; determine the tail node condition: p->next == head.
Merge operation: not considering empty list; when one chain is complete and the other chain still has elements, find the tail node of the other chain and connect it to the new chain.
Split operation: new split head and tail points, based on odd/even, choose basic chain.
3.4. Multilink List
3.5. Generalized Table
Proof: Total node number n, degree 1 node number n1
n = n0 + n1 + n2.
Except the root node, each node has one branch connected:
n - 1 = 2n2 + n1
Solve:
n0 = n2 + 1.
2. Complete Binary Tree: Left -> Right Full; Ideal Balanced Binary Tree: Random Full; Full Binary Tree: Complete
n nodes, depth [log₂n]+1
Depth h, maximum nodes 2^h - 1
3. i's Left: 2i+1, Right: 2i+2, Parent: [i-1]/2
$$2i$$
$$2i+1$$
$$[i/2]$$
Three. Binary Tree Storage
Binary Linked List; Complete Binary Trees can use sequential storage, like heaps.
Four. Binary Tree Operations
Preorder Traversal: Visit -> Left -> Right
Time: O(n); Space: O(log₂n) ~ O(n)
Inorder Traversal: Left -> Visit -> Right
Non-recursive algorithm: Book P165; Supplement P46
Postorder Traversal: Left -> Right -> Visit
Layer Traversal: Left Enqueue -> Right Enqueue -> Dequeue: Loop while (!EmptyQueue())
Five. Binary Tree Counting
Inorder + Preorder or Inorder + Postorder or Inorder + Postorder => Element Counting!
Number of nodes in the corresponding inorder sequence: $$\frac{1}{n+1} C_{n}^{n}$$ (Inorder corresponding to the preorder sequence).
From preorder and inorder to determine the binary tree method: Preorder determines the root, inorder determines the left and right subtrees.
Six. Threaded Binary Trees
Left tag: Lkid: data: Right tag. tag=0: Original; tag=1: Threaded
Preorder Threaded: Current node and preorder predecessor add thread -> Left -> Right.
Inorder Threaded: Left -> Current node and inorder predecessor add thread -> Right.
Postorder Threaded: Left -> Right -> Current node and postorder predecessor add thread.
4.3 Binary Tree Applications
- Convert Ordered Trees to Binary Trees
Ordered Tree -> Binary Linked -> Binary Tree: Tree's child-sibling representation; Single branch ordered tree does not distinguish left and right
- Huffman Binary Tree (Huffman). Height h: 2h-1 ≤ n ≤ 2^h - 1. {n_0 = n_2 + 1} → {n_0 = n/2}
Weight: $$\sum_{i}^{n} weight(i) \cdot length(i) = min$$
{n_0 + n_2 = n} {n_2 = n/2}
Method: Each time from the forest select weight smallest two trees to form a binary tree, root weight = weight + 1
Application: Huffman Encoding (Prefix Encoding): Left 0 Right 1.
III. Binary Search Tree (BST) Height h: h < n < 2^n - 1
Left < Right: In-order sequence, insert in in-order sequence. Time O(log n) ~ O(n), space: same
Delete:
IV. Heap (heap). Height h: 2^(n-1) ≤ n ≤ 2^n - 1
Parent: Up > Down; Child: Up < Down => Complete binary tree stored in order. Level order numbering
Recursion: Left child 2i+1, right child 2i+2, parent [(i-1)/2]
Insert: Insert at tail (right end); for this element siftup: O(log n)
Delete: Delete from tail; direct delete; delete from top; swap with tail element; sift down; clear
Build: Each element execute insert (siftup): O(n log n)
Build after insert (right to left) siftdown: from ⌊n/2⌋ - 1 starting layer by layer upwards O(n)
4.4 Tree Operations
4.5 Tree Applications
$$ G = (V, E) $$
Where \( V \) is the set of vertices and \( E \) is the set of edges. \( G' \subseteq G \) represents a subgraph of \( G \).
- Degree of a Vertex:
- Undirected Graph: The degree of a vertex is the number of edges connected to it.
- Directed Graph: The degree of a vertex is the sum of its in-degree and out-degree. The total degree of a graph is twice the number of edges.
- Path and Connectivity:
- Undirected Graph: A connected graph is one where there is a path between every pair of vertices. A connected component is a maximal connected subgraph.
- Directed Graph: A strongly connected graph is one where there is a directed path between every pair of vertices. A strongly connected component is a maximal strongly connected subgraph.
#### Section 3.2: Forests and Tree Traversal
- Forest to Binary Tree Conversion:
- Left child-right sibling
- Binary tree to forest conversion: Left child-right sibling
- Tree Traversal:
- Preorder Traversal: Root-left-right
- Postorder Traversal: Left-right-root
- Inorder Traversal: Left-root-right
#### Section 3.3: Graph Traversal
- Breadth-First Search (BFS):
- Level-by-level traversal
- Queue-based implementation
- Depth-First Search (DFS):
- Recursive implementation
- Stack-based implementation
#### Section 3.4: Graph Traversal Algorithms
- BFS:
- Queue-based implementation
- Time complexity: O(V + E)
- Space complexity: O(V)
- DFS:
- Recursive implementation
- Stack-based implementation
- Time complexity: O(V + E)
- Space complexity: O(V)
#### Section 3.5: Graph Traversal Applications
- BFS:
- Used for finding the shortest path in an unweighted graph.
- Time complexity: O(V + E)
- Space complexity: O(V)
- DFS:
- Used for finding cycles in a graph.
- Time complexity: O(V + E)
- Space complexity: O(V)
#### Section 3.6: Graph Traversal Variations
- BFS Variations:
- Level-by-level traversal
- Queue-based implementation
- DFS Variations:
- Recursive implementation
- Stack-based implementation
#### Section 3.7: Graph Traversal Optimization
- BFS Optimization:
- Use of a queue to manage nodes to be visited.
- Time complexity: O(V + E)
- Space complexity: O(V)
- DFS Optimization:
- Use of a stack to manage nodes to be visited.
- Time complexity: O(V + E)
- Space complexity: O(V)
#### Section 3.8: Graph Traversal Applications
- BFS Applications:
- Finding the shortest path in an unweighted graph.
- Time complexity: O(V + E)
- Space complexity: O(V)
- DFS Applications:
- Finding cycles in a graph.
- Time complexity: O(V + E)
- Space complexity: O(V)
#### Section 3.9: Graph Traversal Challenges
- BFS Challenges:
- Time complexity: O(V + E)
- Space complexity: O(V)
- DFS Challenges:
- Time complexity: O(V + E)
- Space complexity: O(V)
#### Section 3.10: Graph Traversal Conclusion
- BFS Conclusion:
- Used for finding the shortest path in an unweighted graph.
- Time complexity: O(V + E)
- Space complexity: O(V)
- DFS Conclusion:
- Used for finding cycles in a graph.
- Time complexity: O(V + E)
- Space complexity: O(V)
#### Section 3.11: Graph Traversal Summary
- BFS Summary:
- Time complexity: O(V + E)
- Space complexity: O(V)
- DFS Summary:
- Time complexity: O(V + E)
- Space complexity: O(V)
#### Section 3.12: Graph Traversal Exercises
- BFS Exercises:
- Finding the shortest path in an unweighted graph.
- Time complexity: O(V + E)
- Space complexity: O(V)
- DFS Exercises:
- Finding cycles in a graph.
- Time complexity: O(V + E)
- Space complexity: O(V)
#### Section 3.13: Graph Traversal Conclusion
- BFS Conclusion:
- Used for finding the shortest path in an unweighted graph.
- Time complexity: O(V + E)
- Space complexity: O(V)
- DFS Conclusion:
- Used for finding cycles in a graph.
- Time complexity: O(V + E)
- Space complexity: O(V)
#### Section 3.14: Graph Traversal Challenges
- BFS Challenges:
- Time complexity: O(V + E)
- Space complexity: O(V)
- DFS Challenges:
- Time complexity: O(V + E)
- Space complexity: O(V)
#### Section 3.15: Graph Traversal Summary
- BFS Summary:
- Time complexity: O(V + E)
- Space complexity: O(V)
- DFS Summary:
- Time complexity: O(V + E)
- Space complexity: O(V)
#### Section 3.16: Graph Traversal Exercises
- BFS Exercises:
- Finding the shortest path in an unweighted graph.
- Time complexity: O(V + E)
- Space complexity: O(V)
- DFS Exercises:
- Finding cycles in a graph.
- Time complexity: O(V + E)
- Space complexity: O(V)
#### Section 3.17: Graph Traversal Conclusion
- BFS Conclusion:
- Used for finding the shortest path in an unweighted graph.
- Time complexity: O(V + E)
- Space complexity: O(V)
- DFS Conclusion:
- Used for finding cycles in a graph.
- Time complexity: O(V + E)
- Space complexity: O(V)
#### Section 3.18: Graph Traversal Challenges
- BFS Challenges:
- Time complexity: O(V + E)
- Space complexity: O(V)
- DFS Challenges:
- Time complexity: O(V + E)
- Space complexity: O(V)
#### Section 3.19: Graph Traversal Summary
- BFS Summary:
- Time complexity: O
5.2 Graph Storage Representation
5.3 Graph Traversal
5.4 Minimum Spanning Tree (MST)
5.5 Shortest Path Problem
Section 2: Shortest Path Algorithm (Floyd Algorithm): O(n³) Space: O(n²)
Initially, the distance matrix values represent the direct distance between vertices (not passing through other points). After adding each vertex V_k, if A[i][k] + A[k][j] < A[i][j], then update V_i -> V_j's shortest path. Continue until all vertices are considered. The distance matrix now shows the shortest paths.
5.6 Critical Path
Chapter 6: Searching
6.1 Sequential Search
6.2 Index Search
Delete operation:
Insertion and deletion operations are performed by rotating the tree.
III. B-Tree
A B-tree of order $m$ is a self-balancing search tree that satisfies the following properties:
Chapter 7 Sorting
7.1 Sorting by Exchange
7.2 Insertion Sort
7.3 Selection Sort
Two. Heap Sort
Tree Selection Sort:
Heap Sort:
Heap Sort:
7.4. Merge Sort
1. Merge Sort Concept:
Merge (Merge):
Merge Sort:
Two. Merge of Adjacent Ordered Subarrays:
Three. Merge Sort Implementation:
7.5. External Sorting
1. External Sorting Basic Steps:
Two. External Sorting Time Complexity:
void thread(BT)
{
static Node *pre = NULL;
if (BT != NULL)
{
thread(BT->lchild);
if (pre != NULL && pre->rtag == 1) // current thread's left child needs a thread
pre->rchild = BT;
if (BT->lchild == NULL) // current thread's left child is null
BT->ltag = 1; BT->lchild = pre;
if (BT->rchild == NULL) // current thread's right child is null
BT->rtag = 1;
pre = BT; // current thread is the parent
thread(BT->rchild);
}
}
2. Utilize threads in a binary tree for inorder traversal
Node *p = BT; // initial pointer to root
if (p != NULL)
{
while (p->ltag == 0) p = p->lchild; // find the inorder predecessor
do
{
if (p->rtag == 1) p = p->rchild; // is a thread, move to the inorder successor
else
{
p = p->lchild; // is a child, move to the inorder predecessor
}
} while (p->ltag == 0) p = p->lchild; // find the inorder predecessor
}
The provided code snippet is a C++ function `thread` that threads a binary tree. It traverses the tree and threads it in such a way that each node has a thread to its inorder predecessor. The second part of the code snippet is a pseudocode for inorder traversal using threads. It starts at the root and moves left until it finds a node with a left thread, then it moves right until it finds a node without a right thread, then it moves left again until it finds a node with a left thread, and so on.
int kmp_match(text T, pattern P)
{
int n = strlen(T), m = strlen(P);
int i = 0, j = 0, nxt[MaxSize];
Next(P, nxt);
while (i < n)
{
if (T[i] == P[j])
{
if (j == m - 1) return i - j; // match success
else { i++; j++; }
}
else
{
if (j > 0) j = nxt[j - 1]; // move to partial match point
else { i++; }
}
}
return -1;
}
VI. Sorting Algorithms
1. Bubble Sort
void bubble(a left right)
{
for (int i = left; i < right; i++)
for (int j = right; j > i; j--)
if (a[j] < a[j - 1]) swap(a[j], a[j - 1]);
}
Improvement: flag records the position of the last exchange in a pass of comparison
Partition Function:
int Partition(a, left, right)
{
int k = left;
int i = left, j = right;
while (i != j) // when i and j meet, this pass of partitioning is complete
{
while (a[j] >= a[k] && i < j) j--; // move j left until a[j] < a[k]
if (i < j) // a[j] < a[k]
{
a[i] = a[j]; i++;
// a[i] and a[j] swap
}
while (a[i] <= a[k] && i < j) i++; // move i right until a[i] > a[k]
if (i < j) // a[i] > a[k]
{
a[i] = a[j]; j--;
// a[i] and a[j] swap
}
}
a[i] = a[k]; // insert a[k] at partitioning point i
return i; // return this pass's partitioning point i
}
Quick Sort:
void QuickSort(a, left, right)
{
int i;
if (right > left) // table length is not less than 2
{
i = Partition(a, left, right); // sequence partitioning operation
QuickSort(a, left, i - 1); // quicksort left side
QuickSort(a, i + 1, right); // quicksort right side
}
}
void Insert(...) // Direct Insertion
{
for (int j = 1; j < len; j++) // Need len-1 insertions
{
int temp = a[j]; int i = j - 1; // Store the first element of the sorted part (to be inserted element)
while (i >= 0 && a[i] > temp) // i points to the last position of the sorted part
{
a[i + 1] = a[i]; i--;
} // Move temp to its insertion position
a[i + 1] = temp; // Insert the element to be inserted into the sorted part.
}
}
void BInsert(...) // Binary Insertion
{
for (int j = 1; j < len; j++)
{
int temp = a[j]; int low = 0, high = j - 1;
while (low <= high) // Binary search for the insertion element in the sorted part
{
int mid = (low + high) / 2;
if (a[mid] > temp) high = mid - 1;
else low = mid + 1;
}
for (int i = j - 1; i <= high + 1; i--) // Shift elements from high+1 to j-1 positions
{
a[i + 1] = a[i];
}
a[high + 1] = temp;
}
}
void Shell(a, times, d[]){ // times: sort intervals, d[]: gap between intervals
for(int k = times; k > 1; k--) {
for(int j = k; j < len; j++) {
int h = d[k];
for(int i = j - h; i >= 0; i -= h) {
int temp = a[i];
a[i] = a[i + h];
a[i + h] = temp;
}
}
}
}
void MergeSort(a) {
int *work = new int[len];
int length = 1; // initial subarray length
while(length < len) {
int cur = 2 * length; // cur: current merged subarray length
for(int t = 0; t < len; t += cur) {
int low = t, high = t + cur - 1, mid = t + length - 1;
if(high > len - 1) high = len - 1; // special handling for the last group
if(high > mid) merge(a, low, mid, high, work); // merge subarrays
length = cur;
}
}
delete[] work;
}
for(int m = 1; m <= n / 2; m = 2 * m)
merge_sort(a, left, (left + right) / 2);
for(int i = left; i <= right - m; i += m)
merge_sort(a, i, i + m, min(i + 2 * m - 1, right));
void SelectSort(a) {
for (int i = 0; i < len - 1; i++) {
int pos = i;
for (int j = i + 1; j < len; j++) {
if (a[j] < a[pos]) {
pos = j;
}
}
if (pos != i) {
swap(a[i], a[pos]);
}
}
}
void heapSort(a--) {
int len = right - left; int *p = a + left;
for (int k = (len - 1) / 2; k >= 0; k--) {
SiftDown(p, k, len);
}
while (len > 0) {
exchange(p[0], p[len]);
len--;
SiftDown(p, 0, len);
}
}
The code provided is for implementing selection sort and heap sort algorithms in C.
void merge(int *c, int *a, int n, int *b, int m) {
long i, j, k;
for (i = 0, j = 0, k = 0; k < n + m; k++) {
if (i == n) { c[k] = a[j]; j++; continue; }
if (j == m) { c[k] = b[i]; i++; continue; }
c[k] = (a[i] < b[j]) ? a[i++] : b[j++];
}
}
Bottom-Up Merge Sort:
void merge_sort(int *a, int left, int right) {
for (int i = 1; i <= right - left; i = 2 * i) {
for (int j = left; j <= right - i; j += 2 * i) {
merge(a, j, j + i, min(j + 2 * i - 1, right), a[j]);
}
}
}
Top-Down Merge Sort:
void merge_sort(int *a, int left, int right) {
if (right <= left) return;
int mid = (left + right) / 2;
merge_sort(a, left, mid);
merge_sort(a, mid + 1, right);
merge(a, left, mid + 1, right);
}
Time complexity: O(n log n)
Space complexity: O(n)
Graph storage, DFS, BFS traversals, topological sorting, shortest path algorithms (Dijkstra, Floyd), and minimum spanning trees.
linear non-linear
linear list tree graph logical structure
ordered list linked list index hash memory structure
1.1 data abstraction & binary relation
a. data abstraction
element + relation → directed, weakly connected graph
b. Cartesian product
A × B = {(a, b) | a ∈ A & b ∈ B}
A1 × ... × An = {(a1, ..., an) | ai ∈ Ai}
c. binary relation
R is a subset of A × B, called an endorelation over A
when A = B.
reflexivity: (a, a) ∈ R, symmetry: (a, b) ∈ R ⇒ (b, a) ∈ R
1.2 Basics of data structure
a. Logical structure of data
B = (D, R) D: data, R: endorelation
b. Memory structure of data
see page 1
c. Abstract data type
data structure + operations
1.3 Algorithms
a. Brute force:
b. Divide and conquer: merge sort, quick sort, shell sort.
c. Decrease and conquer: binary search, b-tree search.
d. Backtracking: maze
e. Greedy: KMP, Prim, Kruskal, Dijkstra, Huffman
f. Dynamic programming: Floyd-Warshall
B = (D, R) D = {a_i | i = 1, ..., n}, R = {(a_i, a_{i+1}) | i = 1, ..., n-1}
2.1 Ordered list
2.2 Stack
double stack:
e.g. recursion + divide & conquer
T(n) = aT(n/b) + f(n)
if (P solvable) solve P directly
else for (i = 1: k) y_i = Divide(P_i) // solve subproblems
2.3 Queue
a. sequential
$$\uparrow a_1 a_2 \cdots a_n \rightarrow \vec{v}$$
front rear
b. circular
delete: front = rear = 0
enqueue: (rear + 1) % ms
dequeue: (front + 1) % ms
empty: front == rear
full: (rear + 1) % ms == front
c. priority: heap
2.4 Array and matrix
a. row-based array: AD(a_{ij}) = AD(a_{11}) + [(i-1)n + j-1] unit;
column-based array: AD(a_{ij}) = AD(a_{11}) + [(j-1)n + i-1] unit
b. compressed matrix
- lower-triangular:
row: k = $\frac{1}{2} i(i-1) + j$
col: k = $\frac{[2n-(i-1)]j}{2} + i - (j-1)$
- symmetric
- lower-triangular:
row: k = $\begin{cases} \frac{1}{2} i(i-1) + j & i \geq j \\ \frac{1}{2} j(j-1) + i & i < j \end{cases}$
- diagonal:
row: k = $\begin{cases} (\lfloor \frac{m}{2} \rfloor + 1) \cdot i + j - \lfloor \frac{m}{2} \rfloor + 1 & else \\ 0 & if not (i \leq j \&\& j \leq i + \lfloor \frac{m}{2} \rfloor) \&\& (i \leq j) \end{cases}$
c. sparse matrix: B(row, col, val)
- POS[k]: first non-zero element in row k - POS[i] = POS[i-1] + NUM[i-1]
- NUM[k]: number of non-zero elements in row k: NUM[B[i, 1]] = NUM[B[i-1]] + 1
3. linked list
3.1 regular linked list
*insertion: empty list; insert to the 1st node; can't find where to insert
deletion: empty list; delete the 1st node; can't find where to delete
merge: choose a base list, O(n+m)
split: odd pos/even pos = O(n)
3.2 linked stack, linked queue
a. linked stack
top -> [ ] -> [ ] -> ... -> [ ]
b. linked queue
[ ] -> [ ] -> ... -> [ ]
front rear
3.3 circular linked list
H -> [ ] -> [a1] -> ... -> [an] -> H
empty: H -> [ ] : no need to single out the empty case (vs 3.1)
check rear: p->next == head
merge: p1->next = head2, p2->next = head1
split: create new head, consider odd pos/even pos, choose base
3.4 multi-linked list
3.5 lists
linear; recursive definition; depth = # of layers of recursion
length = # of "next"
e.g. head:
| flag=0 | sublist | next |
|-------|---------|------|
| flag=1 | data | next |
4.1 Basics of Tree
n: number of nodes, degree of node i: di => n = Σ di + 1
k: branches of a node (maximum) = least depth = ⌊log₂[n(k-1)+1]⌋
4.2 Binary Tree
a. Basic Properties
proof: let n be # of nodes, n1 be # of nodes with degree 1
n = n0 + n1 + n2
every node has a parent except the root:
n - 1 = 2n2 + n1
n0 = n2 + 1
n nodes => depth = ⌊log₂n⌋ + 1
depth h => n ≤ 2^h - 1
parent: ⌊(i-1)/2⌋
left child of i: 2i, right child of i: 2i + 1
parent: ⌊i/2⌋
4.3 Memory Structure of Binary Tree
linked list; complete binary trees can be stored using a heap
4.4 DFS, time: O(n), space: O(log₂n) ~ O(n)
can also be implemented in a non-recursive way
DFS: visit -> l -> r
DFS: visit -> r -> l
DFS: l -> r -> visit
DFS: visit -> l -> r
DFS: visit -> r -> l
DFS: l -> r -> visit
DFS: visit -> l -> r
DFS: visit -> r -> l
DFS: l -> r -> visit
4.5 BFS binary tree time: O(n) space: k^(h-1), k: degree, h: depth
Level order tree traversal: for getting depth, deletion, getting # of nodes while (!EmptyQueue()) { enqueue left child; enqueue right child; dequeue; }
4.6 threaded binary tree for O(1) space traversal:
l_tag: l_kid: data: r_kid: r_tag
threaded preorder: thread cur_node & preorder predecessor -> l->r
threaded in order: l->thread cur_node & in order predecessor -> r
threaded post order: l->r->thread cur_node & postorder predecessor predecessor -> l_kid->r_kid.
4.7 counting in binary trees
number of in order traversals corresponding to a preorder: $\frac{1}{n+1} C^n_2$
to specify a binary tree: using preorder to determine root, in order kids.
4.8 applications of binary trees
a. ordered tree -> binary linked list -> binary tree
b. optimal binary tree (Huffman tree)
depth h: 2h-1 ≤ n ≤ 2^h-1
{ n_0 = n_2 + 1 } { n_0 = $\frac{n+1}{2}$ }
{ n_0 + n_2 = n } { n_2 = $\frac{n-1}{2}$ }
minimize: $\sum_{i=1}^{n}$ weight(i) * length(i)
algorithm: select the two trees from the forest with minimum weights to form a binary tree; greedy
root weight = l_weight + r_weight
C. Binary search tree BST
depth h: h < n < 2^h - 1
degree 1 node: delete following child
degree 2 nodes: replace with in order predecessor -> delete in order predecessor { leaf ... degree 1 ...
d. Heap (binary sort) findmin/findmax in O(1)
depth h: 2^(h-1) ≤ n ≤ 2^h - 1
{ max-heap: parent > kid } list, complete binary tree
{ min-heap: parent < kid } index by layer
swap top & rear, sift down the top: O(logn) if at top
(sorting) sift down each element from lower right to upper left: O(n)
e. Solution space tree
backtracking: pre-order traversal of the solution space tree
4.9. Equivalence class and union-find (disjoint-set)
memory structure: multi-branch linked list-based tree
{ make set: rank=0, parent=x
{ find: x.parent = find (x.parent) : recursive
union: make the higher-ranked parent as parent.
5.1 representation
$$G = (V, E)$$
$$G' \subseteq G$$ if $$G'$$ is a subgraph of $$G$$
undirected: degree = edges connected
directed: degree = inbound edges + outbound edges
$$\sum_{v \in V} \text{deg}(v) = 2|E|$$
$$n - 1 \leq |E| \leq C_n^2$$ for undirected graphs
$$n \leq |E| \leq 2C_n^2$$ for directed graphs
5.2 memory
a. adjacency matrix for dense graphs
inbound degree = $$\sum_{i=0}^{n-1} \text{col}_i = \sum_{i=0}^{n-1} A[i][j]$$
outbound degree = $$\sum_{j=0}^{n-1} \text{row}_j = \sum_{j=0}^{n-1} A[i][j]$$
b. linked list for sparse graphs
triplet representation: (row, column, value)
linked representation: (row, column, value, next node)
5.3 traversal
a. DFS (DFT): adjacency matrix: $$O(n^2)$$, linked list: $$O(n + e)$$, space: $$O(n)$$
≈ pre-order traversal of a tree
b. BFS (BFT): adjacency matrix: $$O(n^2)$$, linked list: $$O(n + e)$$, space: $$O(n)$$
≈ level order traversal of a tree (single source single sink shortest path in an unweighted graph)
5.4 MST minimum spanning tree (min $$\sum_{i \in E} e_i$$, $$E \in MST$$)
$$V(G') = V(G)$$, n vertices, n-1 edges.
a. Prim: $$O(n^2)$$: greedy, use heap
b. Kruskal: $$O(e \log e)$$: greedy, use union-find structure
5.5 Single source shortest path (all sinks)
a. w/o negative weights: Dijkstra, based on priority queue O((V + E) log V) faster than iterative DFS's
b. w/ negative weights: Bellman-Ford, slower than Dijkstra O(V * E)
c. SPFA: Shortest path faster algorithm w/ negative weights O(k * E), k << V
5.6 acyclic shortest path, DAGs
O(V + E)
5.7 topological sorting, DAGs
O(V + E), using DFS
5.8 all-source shortest path (all sinks), w/ negative weights
O(V^3), Floyd-Warshall, dynamic programming
6.1 binary search tree. see 4.8, C, worst case O(n) for search, insert, delete and space.
6.2 self-balancing binary search tree
a. AVL tree { worst case O(log n) for }
b. red-black tree search, insert, delete.
6.3 high fan-out self-balancing tree
b. Knuth-Morris-Pratt: preprocessing: O(m), matching: O(n), space: O(m)
6.4. string searching algorithm
string: n > pattern: m
a. straightforward: O(m * n)
7.1 Exchange sort: swap
a. bubble sort -> bidirectional bubble sort $O(n^2)$
b. quick sort: Choose the median of R[m], R[m+n], R[n], divide and conquer, recursion $O(\log n) \rightarrow O(n^2)$
7.2 Insertion sort: insert to sorted list
a. naive $O(n^2)$
b. binary search the sorted list $O(n \log n) \rightarrow O(n^2)$ or swaps
c. shell $O(n^{1.5})$
7.3 Selection sort: select from unsorted list
a. naive $O(n^2)$
b. heap sort: time $O(n) - O(n \log n)$, space: $O(1)$
see 4.8 d, divide and conquer
7.4 Merge sort: divide and conquer, $O(n \log n)$
{ top-down $O(n)$ space: external sort
bottom-up easy to parallelize, can be used on disk
7.5 Distribution sort (non-comparison sort) integers
a. bucket sort time: $O(n + k) - O(n^2)$, space: $O(n \cdot k)$
b. counting sort time: $O(n + k)$, space: $O(n + k)$
c. radix sort time: $O(wn)$, space: $O(w + N)$
Dynamic programming, longest common subsequence, matrix chain multiplication, network flow, bipartite matching, NP-completeness, and SAT problem reductions.
Dynamic Programming
DP: overlapping sub-problems
Design the recurrence using subproblems, then write the program
Algorithms for sequencing related problems, edit distance, knapsack, weighted interval scheduling, and max weight subset of mutually compatible jobs.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d + OPT(i-1,j-1) otherwise.
OPT(i,j) = ∑j=0^i d
Network Flows
Linear Programming
Weak: $$c^T x \leq y^T A x \leq y^T b$$
$$c^T x = y^T A x = y^T b$$
Minimax Theorems
Duality
Strong Duality Theorem
$$\max c^T x$$
$$\text{s.t. } Ax \leq b$$
$$x \geq 0$$
$$\min y^T b$$
$$\text{s.t. } y^T A x \geq c$$
$$y \geq 0$$
It doesn't matter whether the row-player or the column-player has to commit to a strategy first.
$$\max c^T x$$
$$\text{s.t. } Ax \leq b$$
$$x \geq 0$$
$$\min y^T b$$
$$\text{s.t. } y^T A x \geq c$$
$$y \geq 0$$
$$B = c^T$$
$$A = -A^T$$
Randomized Algorithms
\(\text{cldet}(B) = \sum_{\sigma: \{n\} \rightarrow [n]} \prod_{i=1}^{n} A_{\sigma(i), i}\)
\(\text{Linearity of Expectation} \quad E\left(\sum_{i=1}^{n} X_i\right) = \sum_{i=1}^{n} E(X_i)\)
\(\text{Algorithms for Min-Cut, Dominating Set, Flows, Testing when a polynomial is 0.}\)
\(\text{Hot edges that cross from A to B is minimized.}\)
\(\text{Let } p(x_1, \ldots, x_n) \text{ be a polynomial of degree d. Let } S \text{ be a finite set of numbers.}\)
\(\text{The probability that } k \text{ edges of the polynomial are never picked is at least }\)
\(\left(1 - \frac{2}{n}\right) \cdots \left(1 - \frac{2}{n}\right) = \frac{2^k}{n(n-1)}\)
\(\text{If } x_1, \ldots, x_n \text{ are sampled uniformly from } S,\)
\(\text{Then if } x_1, \ldots, x_n \text{ are sampled uniformly from } S,\)
\(\text{cldet}(B) = \sum_{\sigma: \{n\} \rightarrow [n]} \prod_{i=1}^{n} A_{\sigma(i), i}\)
\(\text{Linearity of Expectation} \quad E\left(\sum_{i=1}^{n} X_i\right) = \sum_{i=1}^{n} E(X_i)\)
\(\text{Algorithms for Min-Cut, Dominating Set, Flows, Testing when a polynomial is 0.}\)
\(\text{Hot edges that cross from A to B is minimized.}\)
\(\text{Let } p(x_1, \ldots, x_n) \text{ be a polynomial of degree d. Let } S \text{ be a finite set of numbers.}\)
\(\text{The probability that } k \text{ edges of the polynomial are never picked is at least }\)
\(\left(1 - \frac{2}{n}\right) \cdots \left(1 - \frac{2}{n}\right) = \frac{2^k}{n(n-1)}\)
\(\text{If } x_1, \ldots, x_n \text{ are sampled uniformly from } S,\)
\(\text{Then if } x_1, \ldots, x_n \text{ are sampled uniformly from } S,\)
\(\text{cldet}(B) = \sum_{\sigma: \{n\} \rightarrow [n]} \prod_{i=1}^{n} A_{\sigma(i), i}\)
\(\text{Linearity of Expectation} \quad E\left(\sum_{i=1}^{n} X_i\right) = \sum_{i=1}^{n} E(X_i)\)
\(\text{Algorithms for Min-Cut, Dominating Set, Flows, Testing when a polynomial is 0.}\)
\(\text{Hot edges that cross from A to B is minimized.}\)
\(\text{Let } p(x_1, \ldots, x_n) \text{ be a polynomial of degree d. Let } S \text{ be a finite set of numbers.}\)
\(\text{The probability that } k \text{ edges of the polynomial are never picked is at least }\)
\(\left(1 - \frac{2}{n}\right) \cdots \left(1 - \frac{2}{n}\right) = \frac{2^k}{n(n-1)}\)
\(\text{If } x_1, \ldots, x_n \text{ are sampled uniformly from } S,\)
\(\text{Then if } x_1, \ldots, x_n \text{ are sampled uniformly from } S,\)
\(\text{cldet}(B) = \sum_{\sigma: \{n\} \rightarrow [n]} \prod_{i=1}^{n} A_{\sigma(i), i}\)
\(\text{Linearity of Expectation} \quad E\left(\sum_{i=1}^{n} X_i\right) = \sum_{i=1}^{n} E(X_i)\)
\(\text{Algorithms for Min-Cut, Dominating Set, Flows, Testing when a polynomial is 0.}\)
\(\text{Hot edges that cross from A to B is minimized.}\)
\(\text{Let } p(x_1, \ldots, x_n) \text{ be a polynomial of degree d. Let } S \text{ be a finite set of numbers.}\)
\(\text{The probability that } k \text{ edges of the polynomial are never picked is at least }\)
\(\left(1 - \frac{2}{n}\right) \cdots \left(1 - \frac{2}{n}\right) = \frac{2^k}{n(n-1)}\)
\(\text{If } x_1, \ldots, x_n \text{ are sampled uniformly from } S,\)
\(\text{Then if } x_1, \ldots, x_n \text{ are sampled uniformly from } S,\)
\(\text{cldet}(B) = \sum_{\sigma: \{n\} \rightarrow [n]} \prod_{i=1}^{n} A_{\sigma(i), i}\)
\(\text{Linearity of Expectation} \quad E\left(\sum_{i=1}^{n} X_i\right) = \sum_{i=1}^{n} E(X_i)\)
\(\text{Algorithms for Min-Cut, Dominating Set, Flows, Testing when a polynomial is 0.}\)
\(\text{Hot edges that cross from A to B is minimized.}\)
\(\text{Let } p(x_1, \ldots, x_n) \text{ be a polynomial of degree d. Let } S \text{ be a finite set of numbers.}\)
\(\text{The probability that } k \text{ edges of the polynomial are never picked is at least }\)
\(\left(1 - \frac{2}{n}\right) \cdots \left(1 - \frac{2}{n}\right) = \frac{2^k}{n(n-1)}\)
\(\text{If } x_1, \ldots, x_n \text{ are sampled uniformly from } S,\
decision problems:
problems with "yes" or "no" answers
NP: Nondeterministic Polynomial-time
where P() is some poly.
poly-time: P(x) ≤ poly steps
Definition of NP: decision problems for which there exists a poly-time algorithm.
P: P() algo.
NP: P() certifier (checker)
NP-completeness: NP-complete problems for which there exists a poly-time algorithm.
EXP: EXP() algo.
P ⊆ NP ⊆ EXP
NP = EXP?: is the decision problem as easy as the certification problem?
NP-Complete: a problem y is NP-complete
if for every problem X in NP, X ≤ P y
(Problem X polynomial reduces to problem y)
if any instance of problem X can be solved using a polynomial number of standard computational steps, then y is NP-complete.