8000 Merge pull request #1128 from hieplpvip/fix-typos · cp-algorithms/cp-algorithms@35d2a26 · GitHub
[go: up one dir, main page]
Skip to content

Commit 35d2a26

Browse files
jakobkoglerjakobkogler
authored
Merge pull request #1128 from hieplpvip/fix-typos
Fix typos
2 parents 4cb485b + d9aba33 commit 35d2a26

File tree

8 files changed

+17
-17
lines changed

8 files changed

+17
-17
lines changed

‎src/algebra/bit-manipulation.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -170,7 +170,7 @@ int countSetBits(int n)
170170
}
171171
```
172172

173-
### Addtional tricks
173+
### Additional tricks
174174

175175
- $n ~\&~ (n + 1)$ clears all trailing ones: $0011~0111_2 \rightarrow 0011~0000_2$.
176176
- $n ~|~ (n + 1)$ sets the last cleared bit: $0011~0101_2 \rightarrow 0011~0111_2$.

‎src/algebra/discrete-log.md

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -47,7 +47,7 @@ This problem can be solved using the meet-in-the-middle method as follows:
4747

4848
## Complexity
4949

50-
We can calculate $f_1(p)$ in $O(\log m)$ using the [binary exponentation algorithm](binary-exp.md). Similarly for $f_2(q)$.
50+
We can calculate $f_1(p)$ in $O(\log m)$ using the [binary exponentiation algorithm](binary-exp.md). Similarly for $f_2(q)$.
5151

5252
In the first step of the algorithm, we need to calculate $f_1$ for every possible argument $p$ and then sort the values. Thus, this step has complexity:
5353

@@ -107,7 +107,7 @@ Internally, `map` uses a red-black tree to store values.
107107
Thus this code is a little bit slower than if we had used an array and binary searched, but is much easier to write.
108108
109109
Notice that our code assumes $0^0 = 1$, i.e. the code will compute $0$ as solution for the equation $0^x \equiv 1 \pmod m$ and also as solution for $0^x \equiv 0 \pmod 1$.
110-
This is an often used convention in algebra, but it's also not univerally accepted in all areas.
110+
This is an often used convention in algebra, but it's also not universally accepted in all areas.
111111
Sometimes $0^0$ is simply undefined.
112112
If you don't like our convention, then you need to handle the case $a=0$ separately:
113113

‎src/algebra/garners-algorithm.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -19,7 +19,7 @@ A mixed radix representation is a positional numeral system, that's a generaliza
1919
For instance the decimal numeral system is a positional numeral system with the radix (or base) 10.
2020
Every a number is represented as a string of digits $d_1 d_2 d_3 \dots d_n$ between $0$ and $9$, and
2121
E.g. the string $415$ represents the number $4 \cdot 10^2 + 1 \cdot 10^1 + 5 \cdot 10^0$.
22-
In general the string of digits $d_1 d_2 d_3 \dots d_n$ represents the number $d_1 b^{n-1} + d_2 b^{n-2} + \cdots + d_n b^0$ in the positional numberal system with radix $b$.
22+
In general the string of digits $d_1 d_2 d_3 \dots d_n$ represents the number $d_1 b^{n-1} + d_2 b^{n-2} + \cdots + d_n b^0$ in the positional numeral system with radix $b$.
2323

2424
In a mixed radix system, we don't have one radix any more. The base varies from position to position.
2525

‎src/algebra/polynomial.md

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -16,7 +16,7 @@ In this section, we focus more on the definitions and "intuitive" properties of
1616
### Polynomial multiplication
1717

1818
!!! info "Definition"
19-
**Univariate polynomial** is an expresion of form $A(x) = a_0 + a_1 x + \dots + a_n x^n$.
19+
**Univariate polynomial** is an expression of form $A(x) = a_0 + a_1 x + \dots + a_n x^n$.
2020

2121
The values $a_0, \dots, a_n$ are polynomial coefficients, typically taken from some set of numbers or number-like structures. In this article, we assume that the coefficients are taken from some [field](https://en.wikipedia.org/wiki/Field_(mathematics)), meaning that operations of addition, subtraction, multiplication and division are well-defined for them (except for division by $0$) and they generally behave in a similar way to real numbers.
2222

@@ -25,7 +25,7 @@ Typical example of such field is the field of remainders modulo prime number $p$
2525
For simplicity we will drop the term _univariate_, as this is the only kind of polynomials we consider in this article. We will also write $A$ instead of $A(x)$ wherever possible, which will be understandable from the context. It is assumed that either $a_n \neq 0$ or $A(x)=0$.
2626

2727
!!! info "Definition"
28-
The **product** of two polynomials is defined by expanding it as an arythmetic expression:
28+
The **product** of two polynomials is defined by expanding it as an arithmetic expression:
2929

3030
$$
3131
A(x) B(x) = \left(\sum\limits_{i=0}^n a_i x^i \right)\left(\sum\limits_{j=0}^m b_j x^j\right) = \sum\limits_{i,j} a_i b_j x^{i+j} = \sum\limits_{k=0}^{n+m} c_k x^k = C(x).
@@ -69,12 +69,12 @@ The coefficient near $x^k$ in the polynomial $A(x)$ is denoted shortly as $[x^k]
6969
### Formal power series
7070

7171
!!! info "Definition"
72-
A **formal power series** is an infite sum $A(x) = a_0 + a_1 x + a_2 x^2 + \dots$, considered regardless of its convergence properties.
72+
A **formal power series** is an infinite sum $A(x) = a_0 + a_1 x + a_2 x^2 + \dots$, considered regardless of its convergence properties.
7373

7474
In other words, when we consider e.g. a sum $1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\dots=2$, we imply that it _converges_ to $2$ when the number of summands approach infinity. However, formal series are only considered in terms of sequences that make them.
7575

7676
!!! info "Definition"
77-
The **product** of formal power series $A(x)$ and $B(x)$, is also defined by expanding it as an arythmetic expression:
77+
The **product** of formal power series $A(x)$ and $B(x)$, is also defined by expanding it as an arithmetic expression:
7878

7979

8080
$$

‎src/graph/bridge-searching-online.md

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -259,13 +259,13 @@ This function is used many times in the rest of the code, since after the compre
259259
The DSU for the connected components is stored in the vector `dsu_cc`, and there is also an additional vector `dsu_cc_size` to store the component sizes.
260260
The function `find_cc(v)` returns the leader of the connectivity component (which is actually the root of the tree).
261261
262-
The re-rooting of a tree `make_root(v)` works as descibed above:
262+
The re-rooting of a tree `make_root(v)` works as described above:
263263
if traverses from the vertex $v$ via the ancestors to the root vertex, each time redirecting the ancestor `par` in the opposite direction.
264264
The link to the representative of the connected component `dsu_cc` is also updated, so that it points to the new root vertex.
265265
After re-rooting we have to assign the new root the correct size of the connected component.
266266
Also we have to be careful that we call `find_2ecc()` to get the representatives of the 2-edge-connected component, rather than some other vertex that have already been compressed.
267267
268-
The cycle finding and compression function `merge_path(a, b)` is also implemented as descibed above.
268+
The cycle finding and compression function `merge_path(a, b)` is also implemented as described above.
269269
It searches for the LCA of $a$ and $b$ be rising these nodes in parallel, until we meet a vertex for the second time.
270270
For efficiency purposes we choose a unique identifier for each LCA finding call, and mark the traversed vertices with it.
271271
This works in $O(1)$, while other approaches like using $set$ perform worse.

‎src/graph/lca_farachcoltonbender.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -118,7 +118,7 @@ int min_by_h(int i, int j) {
118118
}
119119

120120
void precompute_lca(int root) {
121-
// get euler tour & indices of first occurences
121+
// get euler tour & indices of first occurrences
122122
first_visit.assign(n, -1);
123123
height.assign(n, 0);
124124
euler_tour.reserve(2 * n);

‎src/graph/min_cost_flow.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -17,7 +17,7 @@ Sometimes the task is given a little differently:
1717
you want to find the maximum flow, and among all maximal flows we want to find the one with the least cost.
1818
This is called the **minimum-cost maximum-flow problem**.
1919

20-
Both these problems can be solved effectively with the algorithm of sucessive shortest paths.
20+
Both these problems can be solved effectively with the algorithm of successive shortest paths.
2121

2222
## Algorithm
2323

‎src/string/rabin-karp.md

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -37,13 +37,13 @@ vector<int> rabin_karp(string const& s, string const& t) {
3737
for (int i = 0; i < S; i++)
3838
h_s = (h_s + (s[i] - 'a' + 1) * p_pow[i]) % m;
3939

40-
vector<int> occurences;
41-
for (int i = 0; i + S - 1 < T; i++) {
42-
long long cur_h = (h[i+S] + m - h[i]) % m;
40+
vector<int> occurrences;
41+
for (int i = 0; i + S - 1 < T; i++) {
42+
long long cur_h = (h[i+S] + m - h[i]) % m;
4343
if (cur_h == h_s * p_pow[i] % m)
44-
occurences.push_back(i);
44+
occurrences.push_back(i);
4545
}
46-
return occurences;
46+
return occurrences;
4747
}
4848
```
4949

0 commit comments

Comments
 (0)
0