TCS Wiki - User contributions [en]

Combinatorics (Fall 2010)/Generating functions

2010-07-14T03:15:02Z

210.28.131.14: /* Catalan Number */

== Stirling's Approximation ==
As we have seen, answers to many counting problems are expressed in terms of factorials. It is important for us to know roughly how large <math>n!</math> is, i.e. the asymptotic order of <math>n!</math>. This is done by the famous [http://en.wikipedia.org/wiki/Stirling's_approximation '''Stirling's approximation'''], also called '''Stirling's formula'''.

{{Theorem|Theorem (Stirling's approximation)|
:<math>n!\sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n</math>.
}}
The symbol <math>\sim\,</math> means that <math>\lim_{n\rightarrow\infty}\frac{n!}{\sqrt{2\pi n}\left(\frac{n}{e}\right)^n}=1</math>.

The proof of the Stirling's approximation is complicated. We will prove the following easier proposition.
{{Theorem|Proposition|
:<math>\ln (n!)=n\ln n-n+O(\ln n)\,</math>
}}
{{Proof|
The logarithm of <math>n!</math> is <math>\ln (n!)=\sum_{k=1}^n\ln k</math>.
Since <math>f(x)=\ln x</math> is an increasing function of <math>x</math> for all positive <math>x</math>, we have
:<math>
\ln (n!)=\sum_{k=1}^n\ln k \le \int_2^{n+1}\ln x\, \mathrm{d}x =(n+1)\ln(n+1)-(n+1)-2\ln 2+2.
</math>
Note that
:<math>\ln(n+1)-\ln n=\int_{n}^{n+1}\frac{1}{x}\,\mathrm{d}x<\frac{1}{n},</math>
thus <math>n\ln (n+1)<n\ln n+1</math>. Combining this with the above upper bound,
:<math>\ln (n!)\le n\ln n-n+O(\ln n).</math>
}}
The full proof of Stirling's approximation involves a more precise estimation of the constant factor in <math>O(\ln n)</math>.

=== Binomial coefficient ===
For binomial coefficient, we can approximate it by the Stirling's approximation of factorial, but we also have an easier (but loose) estimation.
{{Theorem|Proposition|
:<math>\left(\frac{n}{k}\right)^k\le {n\choose k} < \left(\frac{\mathrm{e}n}{k}\right)^k</math>
}}
{{Proof|
The lower bound is easy:
:<math>{n\choose k}=\frac{n}{k}\cdot\frac{n-1}{k-1}\cdots\frac{n-k+1}{1}\ge\frac{n}{k}\cdot\frac{n}{k}\cdots\frac{n}{k}=\left(\frac{n}{k}\right)^k</math>.
For the upper bound,
:<math>
\mathrm{e}^{nx}>(1+x)^n=\sum_{i=1}^n{n\choose i}x^i>{n\choose k}x^k,
</math>
for any <math>0\le k\le n</math>.

Setting <math>x=\frac{k}{n}</math>, we have
:<math>
\mathrm{e}^k>{n\choose k}\left(\frac{k}{n}\right)^k.
</math>
Therefore,
:<math>{n\choose k} < \left(\frac{\mathrm{e}n}{k}\right)^k</math>.
}}

== Generating Functions ==
In Stanley's magnificent book ''Enumerative Combinatorics'', he comments the generating function as "the most useful but most difficult to understand method (for counting)".

The solution to a counting problem is usually represented as some <math>a_n</math> depending a parameter <math>n</math>. Sometimes this <math>a_n</math> is called a ''counting function'' as it is a function of the parameter <math>n</math>. <math>a_n</math> can also be treated as a infinite series:
:<math>a_0,a_1,a_2,\ldots</math>

The '''ordinary generating function (OGF)''' defined by <math>a_n</math> is
:<math>
G(x)=\sum_{n\ge 0} a_nx^n.
</math>

So <math>G(x)=a_0+a_1x+a_2x^2+\cdots</math>. An expression in this form is called a [http://en.wikipedia.org/wiki/Formal_power_series '''formal power series'''], and <math>a_0,a_1,a_2,\ldots</math> is the sequence of '''coefficients'''.

Furthermore, the generating function can be expanded as
:G(x)=<math>(\underbrace{1+\cdots+1}_{a_0})+(\underbrace{x+\cdots+x}_{a_1})+(\underbrace{x^2+\cdots+x^2}_{a_2})+\cdots+(\underbrace{x^n+\cdots+x^n}_{a_n})+\cdots</math>
so it indeed "generates" all the possible instances of the objects we want to count.

Usually, we do not evaluate the generating function <math>GF(x)</math> on any particular value. <math>x</math> remains as a '''formal variable''' without assuming any value. The numbers that we want to count are the coefficients carried by the terms in the formal power series. So far the generating function is just another way to represent the sequence
:<math>(a_0,a_1,a_2,\ldots\ldots)</math>.

The true power of generating functions comes from the various algebraic operations that we can perform on these generating functions. We use an example to demonstrate this.

=== Fibonacci numbers ===
Consider the following counting problems.
* Count the number of ways that the nonnegative integer <math>n</math> can be written as a sum of ones and twos (in order).
: The problem asks for the number of compositions of <math>n</math> with summands from <math>\{1,2\}</math>. Formally, we are counting the number of tuples <math>(x_1,x_2,\ldots,x_k)</math> for some <math>k\le n</math> such that <math>x_i\in\{1,2\}</math> and <math>\sum_{i=1}^k x_i=n</math>.
: Let <math>F_n</math> be the solution. We observe that a composition either starts with a 1, in which case the rest is a composition of <math>n-1</math>; or starts with a 2, in which case the rest is a composition of <math>n-2</math>. So we have the recursion for <math>F_n</math> that
::<math>F_n=F_{n-1}+F_{n-2}</math>.
* Count the ways to completely cover a <math>2\times n</math> rectangle with <math>2\times 1</math> dominos without any overlaps.
: Dominos are identical <math>2\times 1</math> rectangles, so that only their orientations --- vertical or horizontal matter.
: Let <math>F_n</math> be the solution. It also holds that <math>F_n=F_{n-1}+F_{n-2}</math>. The proof is left as an exercise.

In both problems, the solution is given by <math>F_n</math> which satisfies the following recursion.
:<math>F_n=\begin{cases}
0 & \mbox{if }n=0\\
1 & \mbox{if }n=1\\
F_{n-1}+F_{n-2} & \mbox{if}n\ge 2.
\end{cases}</math>

<math>F_n</math> is called the [http://en.wikipedia.org/wiki/Fibonacci_number Fibonacci number].

{{Theorem|Theorem|
::<math>F_n=\frac{1}{\sqrt{5}}\left(\phi^n-\hat{\phi}^n\right)</math>,
:where <math>\phi=\frac{1+\sqrt{5}}{2}</math> and <math>\hat{\phi}=\frac{1-\sqrt{5}}{2}</math>.
}}
The quantity <math>\phi=\frac{1+\sqrt{5}}{2}</math> is the so-called [http://en.wikipedia.org/wiki/Golden_ratio golden ratio], a constant with some significance in mathematics and aesthetics.

We now prove this theorem by using generating functions.

The ordinary generating function for the Fibonacci number <math>F_{n}</math> is
:<math>G(x)=\sum_{n\ge 0}F_n x^n</math>.
We have that <math>F_{n}=F_{n-1}+F_{n-2}</math> for <math>n\ge 2</math>, thus
:<math>\begin{align}
G(x)
&=
\sum_{n\ge 0}F_n x^n
&=
x+\sum_{n\ge 2}(F_{n-1}+F_{n-2})x^n.
\end{align}
</math>
For generating functions, there are general ways to generate <math>F_{n-1}</math> and <math>F_{n-2}</math>, or the coefficients with any smaller indices.
:<math>
\begin{align}
xG(x)
&=\sum_{n\ge 0}F_n x^{n+1}=\sum_{n\ge 1}F_{n-1} x^n=\sum_{n\ge 2}F_{n-1} x^n\\
x^2G(x)
&=\sum_{n\ge 0}F_n x^{n+2}=\sum_{n\ge 2}F_{n-2} x^n.
\end{align}
</math>
So we have
:<math>G(x)=x+(x+x^2)G(x)\,</math>,
hence
:<math>G(x)=\frac{x}{1-x-x^2}</math>.
The value of <math>F_n</math> is the coefficient of <math>x^n</math> in the Taylor series for this formular, which is <math>\frac{G^{(n)}(0)}{n!}=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n</math>. Although this expansion works in principle, the detailed calculus is rather painful.

----
There is an easier way to get this coefficient than directly expanding the Taylor series.

<math>1-x-x^2</math> has two roots <math>\frac{-1\pm\sqrt{5}}{2}</math>.

Denote that <math>\phi=\frac{2}{-1+\sqrt{5}}=\frac{1+\sqrt{5}}{2}</math> and <math>\hat{\phi}=\frac{2}{-1-\sqrt{5}}=\frac{1-\sqrt{5}}{2}</math>. Then <math>(1-x-x^2)=(1-\phi x)(1-\hat{\phi}x)</math>, so we can write
:<math>
\begin{align}
\frac{x}{1-x-x^2}
&=\frac{x}{(1-\phi x)(1-\hat{\phi} x)}\\
&=\frac{\alpha}{(1-\phi x)}+\frac{\beta}{(1-\hat{\phi} x)},
\end{align}
</math>
where <math>\alpha</math> and <math>\beta</math> satisfying that
:<math>\begin{cases}
\alpha+\beta=0\\
\alpha\phi+\beta\hat{\phi}= -1.
\end{cases}</math>
Solving this we have that <math>\alpha=\frac{1}{\sqrt{5}}</math> and <math>\beta=-\frac{1}{\sqrt{5}}</math>. And
:<math>G(x)=\frac{x}{1-x-x^2}=\frac{1}{\sqrt{5}}\cdot\frac{1}{1-\phi x}-\frac{1}{\sqrt{5}}\cdot\frac{1}{1-\hat{\phi} x}</math>
where <math>\phi=\frac{1+\sqrt{5}}{2}</math> and <math>\hat{\phi}=\frac{1-\sqrt{5}}{2}</math>.

Note that the expression <math>\frac{1}{1-z}</math> has a well known expansion:
:<math>\frac{1}{1-z}=\sum_{n\ge 0}z^n</math>.

Therefore, <math>G(x)</math> can be expanded as
:<math>
\begin{align}
G(x)
&=\frac{1}{\sqrt{5}}\cdot\frac{1}{1-\phi x}-\frac{1}{\sqrt{5}}\cdot\frac{1}{1-\hat{\phi} x}\\
&=\frac{1}{\sqrt{5}}\sum_{n\ge 0}(\phi x)^n-\frac{1}{\sqrt{5}}\sum_{n\ge 0}(\hat{\phi} x)^n\\
&=\sum_{n\ge 0}\frac{1}{\sqrt{5}}\left(\phi^n-\hat{\phi}^n\right)x^n.
\end{align}</math>
So the <math>n</math>th Fibonacci number is given by
:<math>F_n=\frac{1}{\sqrt{5}}\left(\phi^n-\hat{\phi}^n\right)=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n</math>.

=== Solving recurrences ===
In the above analysis of Fibonacci numbers, we apply the following general methodology of solving recurrences by generating functions.
:1. Give a recursion that computes <math>a_n</math>; that is, an equation expressing <math>a_n</math> in terms of other elements of the sequence, such as
::<math>a_n=f(a_0,a_1,\ldots,a_{n-1})</math> for some function <math>f</math>.
:2. Multiply both sides of the equation by <math>x^n</math> and sum over all <math>n</math>. This gives the generating function
::<math>G(x)=\sum_{n\ge 0}a_nx^n=\sum_{n\ge 0}f(a_0,a_1,\ldots,a_{n-1})x^n</math>.
:: And manipulate the right hand side of the equation so that it becomes some other expression involving <math>G(x)</math>.
:3. Solve the resulting equation to derive an explicit formula for <math>G(x)</math>.
:4. Expand <math>G(x)</math> into a power series and read off the coefficient of <math>x^n</math>, which is a closed form for <math>a_n</math>.

==== Algebraic operations on generating functions ====
The second step in the above methodology is somehow tricky. It involves first applying the recurrence to the coefficients of <math>G(x)</math>, which is easy; and then manipulating the resulting formal power series to express it in terms of <math>G(x)</math>, which is more difficult (because it works backwards).

We can apply several natural algebraic operations on the formal power series.

{{Theorem|Generating function manipulation|
:Let <math>G(x)=\sum_{n\ge 0}g_nx^n</math> and <math>F(x)=\sum_{n\ge 0}f_nx^n</math>.
----

::<math>
\begin{align}
x^k G(x)
&= \sum_{n\ge k}g_{n-k}x^n, &\qquad (\mbox{integer }k\ge 0)\\
\frac{G(x)-\sum_{i=0}^{k-1}g_iz^i}{x^k}
&=\sum_{n\ge 0}g_{n+k}x^n, &\qquad (\mbox{integer }k\ge 0)\\
\alpha F(x)+\beta G(x)
&= \sum_{n\ge 0} (\alpha f_n+\beta g_n)x^n\\
F(x)G(x)
&= \sum_{n\ge 0}\sum_{k=0}^nf_kg_{n-k}x^n\\
G(cx)
&= \sum_{n\ge 0} c^ng_n x^n\\
G'(x)
&=
\sum_{n\ge 0}(n+1)g_{n+1}x^n\\
\frac{G(x)}{1-x}
&=\sum_{n\ge 0}\left(\sum_{k=0}^ng_k\right)x^n
\end{align}
</math>
}}

When manipulating generating functions, these rules are applied backwards; that is, from the right-hand-side to the left-hand-side.

==== Expanding generating functions ====
The last step of solving recurrences by generating function is expanding the closed form generating function <math>G(x)</math> to evaluate its <math>n</math>-th coefficient. In principle, we can always use the [http://en.wikipedia.org/wiki/Taylor_series Taylor series]
:<math>G(x)=\sum_{n\ge 0}\frac{G^{(n)}(0)}{n!}x^n</math>,
where <math>G^{(n)}(0)</math> is the value of the <math>n</math>-th derivative of <math>G(x)</math> evaluated at <math>x=0</math>.

Some interesting special cases are very useful.

;Geometric sequence
In the example of Fibonacci numbers, we use the well known geometric series:
:<math>\frac{1}{1-x}=\sum_{n\ge 0}x^n</math>.
It is useful when we can express the generating function in the form of <math>G(x)=\frac{a_1}{1-b_1x}+\frac{a_2}{1-b_2x}+\cdots+\frac{a_k}{1-b_kx}</math>. The coefficient of <math>x^n</math> in such <math>G(x)</math> is <math>a_1b_1^n+a_2b_2^n+\cdots+a_kb_k^n</math>.
;Binomial theorem
The <math>n</math>-th derivative of <math>(1+x)^\alpha</math> for some real <math>\alpha</math> is
:<math>\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-n+1)(1+x)^{\alpha-n}</math>.
By Taylor series, we get a generalized version of the binomial theorem known as [http://en.wikipedia.org/wiki/Binomial_coefficient#Newton.27s_binomial_series '''Newton's formula''']:
:<math>(1+x)^\alpha=\sum_{n\ge 0}{\alpha\choose n}x^{n}</math>,
where <math>{\alpha\choose n}</math> is the '''generalized binomial coefficient''' defined by
:<math>{\alpha\choose n}=\frac{\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-n+1)}{n!}</math>.

In the last lecture we gave a combinatorial proof of the number of <math>k</math>-multisets on an <math>n</math>-set. Now we give a generating function approach to the problem.

Let <math>S=\{x_1,x_2,\ldots,x_n\}</math> be an <math>n</math>-element set. We have
:<math>(1+x_1+x_1^2+\cdots)(1+x_2+x_2^2+\cdots)\cdots(1+x_n+x_n^2+\cdots)=\sum_{m:S\rightarrow\mathbb{N}} \prod_{x_i\in S}x_i^{m(x_i)}</math>,
where each <math>m:S\rightarrow\mathbb{N}</math> species a possible multiset on <math>S</math> with multiplicity function <math>m</math>.

Let all <math>x_i=x</math>. Then
:<math>
\begin{align}
(1+x+x^2+\cdots)^n
&=
\sum_{m:S\rightarrow\mathbb{N}}x^{m(x_1)+\cdots+m(x_n)}\\
&=
\sum_{\text{multiset }M\text{ on }S}x^{|M|}\\
&=
\sum_{k\ge 0}\left({n\choose k}\right)x^k.
\end{align}
</math>
The last equation is due to the the definition of <math>\left({n\choose k}\right)</math>. Our task is to evaluate <math>\left({n\choose k}\right)</math>.

Due to the geometric sequence and the Newton's formula
:<math>
(1+x+x^2+\cdots)^n=(1-x)^{-n}=\sum_{k\ge 0}{-n\choose k}(-x)^k.
</math>
So
:<math>
\left({n\choose k}\right)=(-1)^k{-n\choose k}={n+k-1\choose k}.
</math>
The last equation is due to the definition of the generalized binomial coefficient. We use an analytic (generating function) proof to get the same result of <math>\left({n\choose k}\right)</math> as the combinatorial proof.

=== Linear recurrences ===

== Catalan Number ==

== Partitions ==

Combinatorics (Fall 2010)/Generating functions

2010-07-14T03:11:42Z

210.28.131.14: /* Expanding generating functions */

Combinatorics (Fall 2010)/Generating functions

2010-07-14T02:34:49Z

210.28.131.14: /* Binomial coefficient */

Combinatorics (Fall 2010)/Generating functions

2010-07-14T02:27:43Z

210.28.131.14: /* Binomial coefficient */

== Stirling's Approximation ==
As we have seen, answers to many counting problems are expressed in terms of factorials. It is important for us to know roughly how large <math>n!</math> is, i.e. the asymptotic order of <math>n!</math>. This is done by the famous [http://en.wikipedia.org/wiki/Stirling's_approximation '''Stirling's approximation'''], also called '''Stirling's formula'''.

{{Theorem|Theorem (Stirling's approximation)|
:<math>n!\sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n</math>.
}}
The symbol <math>\sim\,</math> means that <math>\lim_{n\rightarrow\infty}\frac{n!}{\sqrt{2\pi n}\left(\frac{n}{e}\right)^n}=1</math>.

The proof of the Stirling's approximation is complicated. We will prove the following easier proposition.
{{Theorem|Proposition|
:<math>\ln (n!)=n\ln n-n+O(\ln n)\,</math>
}}
{{Proof|
The logarithm of <math>n!</math> is <math>\ln (n!)=\sum_{k=1}^n\ln k</math>.
Since <math>f(x)=\ln x</math> is an increasing function of <math>x</math> for all positive <math>x</math>, we have
:<math>
\ln (n!)=\sum_{k=1}^n\ln k \le \int_2^{n+1}\ln x\, \mathrm{d}x =(n+1)\ln(n+1)-(n+1)-2\ln 2+2.
</math>
Note that
:<math>\ln(n+1)-\ln n=\int_{n}^{n+1}\frac{1}{x}\,\mathrm{d}x<\frac{1}{n},</math>
thus <math>n\ln (n+1)<n\ln n+1</math>. Combining this with the above upper bound,
:<math>\ln (n!)\le n\ln n-n+O(\ln n).</math>
}}
The full proof of Stirling's approximation involves a more precise estimation of the constant factor in <math>O(\ln n)</math>.

=== Binomial coefficient ===
{{Theorem|Proposition|
:<math>\left(\frac{n}{k}\right)^k\le {n\choose k} < \left(\frac{\mathrm{e}n}{k}\right)^k</math>
}}
{{Proof|
The lower bound is easy:
:<math>{n\choose k}=\frac{n}{k}\cdot\frac{n-1}{k-1}\cdots\frac{n-k+1}{1}\ge\frac{n}{k}\cdot\frac{n}{k}\cdots\frac{n}{k}=\left(\frac{n}{k}\right)^k</math>.
For the upper bound,
:<math>
\mathrm{e}^{nx}>(1+x)^n=\sum_{i=1}^n{n\choose i}x^i>{n\choose k}x^k,
</math>
for any <math>0\le k\le n</math>.

Setting <math>x=\frac{k}{n}</math>, we have
:<math>
\mathrm{e}^k>{n\choose k}\left(\frac{k}{n}\right)^k.
</math>
Therefore,
:<math>{n\choose k} < \left(\frac{\mathrm{e}n}{k}\right)^k</math>.
}}

== Generating Functions ==
In Stanley's magnificent book ''Enumerative Combinatorics'', he comments the generating function as "the most useful but most difficult to understand method (for counting)".

The solution to a counting problem is usually represented as some <math>a_n</math> depending a parameter <math>n</math>. Sometimes this <math>a_n</math> is called a ''counting function'' as it is a function of the parameter <math>n</math>. <math>a_n</math> can also be treated as a infinite series:
:<math>a_0,a_1,a_2,\ldots</math>

The '''ordinary generating function (OGF)''' defined by <math>a_n</math> is
:<math>
G(x)=\sum_{n\ge 0} a_nx^n.
</math>

So <math>G(x)=a_0+a_1x+a_2x^2+\cdots</math>. An expression in this form is called a [http://en.wikipedia.org/wiki/Formal_power_series '''formal power series'''], and <math>a_0,a_1,a_2,\ldots</math> is the sequence of '''coefficients'''.

Furthermore, the generating function can be expanded as
:G(x)=<math>(\underbrace{1+\cdots+1}_{a_0})+(\underbrace{x+\cdots+x}_{a_1})+(\underbrace{x^2+\cdots+x^2}_{a_2})+\cdots+(\underbrace{x^n+\cdots+x^n}_{a_n})+\cdots</math>
so it indeed "generates" all the possible instances of the objects we want to count.

Usually, we do not evaluate the generating function <math>GF(x)</math> on any particular value. <math>x</math> remains as a '''formal variable''' without assuming any value. The numbers that we want to count are the coefficients carried by the terms in the formal power series. So far the generating function is just another way to represent the sequence
:<math>(a_0,a_1,a_2,\ldots\ldots)</math>.

The true power of generating functions comes from the various algebraic operations that we can perform on these generating functions. We use an example to demonstrate this.

=== Fibonacci numbers ===
Consider the following counting problems.
* Count the number of ways that the nonnegative integer <math>n</math> can be written as a sum of ones and twos (in order).
: The problem asks for the number of compositions of <math>n</math> with summands from <math>\{1,2\}</math>. Formally, we are counting the number of tuples <math>(x_1,x_2,\ldots,x_k)</math> for some <math>k\le n</math> such that <math>x_i\in\{1,2\}</math> and <math>\sum_{i=1}^k x_i=n</math>.
: Let <math>F_n</math> be the solution. We observe that a composition either starts with a 1, in which case the rest is a composition of <math>n-1</math>; or starts with a 2, in which case the rest is a composition of <math>n-2</math>. So we have the recursion for <math>F_n</math> that
::<math>F_n=F_{n-1}+F_{n-2}</math>.
* Count the ways to completely cover a <math>2\times n</math> rectangle with <math>2\times 1</math> dominos without any overlaps.
: Dominos are identical <math>2\times 1</math> rectangles, so that only their orientations --- vertical or horizontal matter.
: Let <math>F_n</math> be the solution. It also holds that <math>F_n=F_{n-1}+F_{n-2}</math>. The proof is left as an exercise.

In both problems, the solution is given by <math>F_n</math> which satisfies the following recursion.
:<math>F_n=\begin{cases}
0 & \mbox{if }n=0\\
1 & \mbox{if }n=1\\
F_{n-1}+F_{n-2} & \mbox{if}n\ge 2.
\end{cases}</math>

<math>F_n</math> is called the [http://en.wikipedia.org/wiki/Fibonacci_number Fibonacci number].

{{Theorem|Theorem|
::<math>F_n=\frac{1}{\sqrt{5}}\left(\phi^n-\hat{\phi}^n\right)</math>,
:where <math>\phi=\frac{1+\sqrt{5}}{2}</math> and <math>\hat{\phi}=\frac{1-\sqrt{5}}{2}</math>.
}}
The quantity <math>\phi=\frac{1+\sqrt{5}}{2}</math> is the so-called [http://en.wikipedia.org/wiki/Golden_ratio golden ratio], a constant with some significance in mathematics and aesthetics.

We now prove this theorem by using generating functions.

The ordinary generating function for the Fibonacci number <math>F_{n}</math> is
:<math>G(x)=\sum_{n\ge 0}F_n x^n</math>.
We have that <math>F_{n}=F_{n-1}+F_{n-2}</math> for <math>n\ge 2</math>, thus
:<math>\begin{align}
G(x)
&=
\sum_{n\ge 0}F_n x^n
&=
x+\sum_{n\ge 2}(F_{n-1}+F_{n-2})x^n.
\end{align}
</math>
For generating functions, there are general ways to generate <math>F_{n-1}</math> and <math>F_{n-2}</math>, or the coefficients with any smaller indices.
:<math>
\begin{align}
xG(x)
&=\sum_{n\ge 0}F_n x^{n+1}=\sum_{n\ge 1}F_{n-1} x^n=\sum_{n\ge 2}F_{n-1} x^n\\
x^2G(x)
&=\sum_{n\ge 0}F_n x^{n+2}=\sum_{n\ge 2}F_{n-2} x^n.
\end{align}
</math>
So we have
:<math>G(x)=x+(x+x^2)G(x)\,</math>,
hence
:<math>G(x)=\frac{x}{1-x-x^2}</math>.
The value of <math>F_n</math> is the coefficient of <math>x^n</math> in the Taylor series for this formular, which is <math>\frac{G^{(n)}(0)}{n!}=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n</math>. Although this expansion works in principle, the detailed calculus is rather painful.

----
There is an easier way to get this coefficient than directly expanding the Taylor series.

<math>1-x-x^2</math> has two roots <math>\frac{-1\pm\sqrt{5}}{2}</math>.

Denote that <math>\phi=\frac{2}{-1+\sqrt{5}}=\frac{1+\sqrt{5}}{2}</math> and <math>\hat{\phi}=\frac{2}{-1-\sqrt{5}}=\frac{1-\sqrt{5}}{2}</math>. Then <math>(1-x-x^2)=(1-\phi x)(1-\hat{\phi}x)</math>, so we can write
:<math>
\begin{align}
\frac{x}{1-x-x^2}
&=\frac{x}{(1-\phi x)(1-\hat{\phi} x)}\\
&=\frac{\alpha}{(1-\phi x)}+\frac{\beta}{(1-\hat{\phi} x)},
\end{align}
</math>
where <math>\alpha</math> and <math>\beta</math> satisfying that
:<math>\begin{cases}
\alpha+\beta=0\\
\alpha\phi+\beta\hat{\phi}= -1.
\end{cases}</math>
Solving this we have that <math>\alpha=\frac{1}{\sqrt{5}}</math> and <math>\beta=-\frac{1}{\sqrt{5}}</math>. And
:<math>G(x)=\frac{x}{1-x-x^2}=\frac{1}{\sqrt{5}}\cdot\frac{1}{1-\phi x}-\frac{1}{\sqrt{5}}\cdot\frac{1}{1-\hat{\phi} x}</math>
where <math>\phi=\frac{1+\sqrt{5}}{2}</math> and <math>\hat{\phi}=\frac{1-\sqrt{5}}{2}</math>.

Note that the expression <math>\frac{1}{1-z}</math> has a well known expansion:
:<math>\frac{1}{1-z}=\sum_{n\ge 0}z^n</math>.

Therefore, <math>G(x)</math> can be expanded as
:<math>
\begin{align}
G(x)
&=\frac{1}{\sqrt{5}}\cdot\frac{1}{1-\phi x}-\frac{1}{\sqrt{5}}\cdot\frac{1}{1-\hat{\phi} x}\\
&=\frac{1}{\sqrt{5}}\sum_{n\ge 0}(\phi x)^n-\frac{1}{\sqrt{5}}\sum_{n\ge 0}(\hat{\phi} x)^n\\
&=\sum_{n\ge 0}\frac{1}{\sqrt{5}}\left(\phi^n-\hat{\phi}^n\right)x^n.
\end{align}</math>
So the <math>n</math>th Fibonacci number is given by
:<math>F_n=\frac{1}{\sqrt{5}}\left(\phi^n-\hat{\phi}^n\right)=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n</math>.

=== Solving recurrences ===
In the above analysis of Fibonacci numbers, we apply the following general methodology of solving recurrences by generating functions.
:1. Give a recursion that computes <math>a_n</math>; that is, an equation expressing <math>a_n</math> in terms of other elements of the sequence, such as
::<math>a_n=f(a_0,a_1,\ldots,a_{n-1})</math> for some function <math>f</math>.
:2. Multiply both sides of the equation by <math>x^n</math> and sum over all <math>n</math>. This gives the generating function
::<math>G(x)=\sum_{n\ge 0}a_nx^n=\sum_{n\ge 0}f(a_0,a_1,\ldots,a_{n-1})x^n</math>.
:: And manipulate the right hand side of the equation so that it becomes some other expression involving <math>G(x)</math>.
:3. Solve the resulting equation to derive an explicit formula for <math>G(x)</math>.
:4. Expand <math>G(x)</math> into a power series and read off the coefficient of <math>x^n</math>, which is a closed form for <math>a_n</math>.

==== Algebraic operations on generating functions ====
The second step in the above methodology is somehow tricky. It involves first applying the recurrence to the coefficients of <math>G(x)</math>, which is easy; and then manipulating the resulting formal power series to express it in terms of <math>G(x)</math>, which is more difficult (because it works backwards).

We can apply several natural algebraic operations on the formal power series.

{{Theorem|Generating function manipulation|
:Let <math>G(x)=\sum_{n\ge 0}g_nx^n</math> and <math>F(x)=\sum_{n\ge 0}f_nx^n</math>.
----

::<math>
\begin{align}
x^k G(x)
&= \sum_{n\ge k}g_{n-k}x^n, &\qquad (\mbox{integer }k\ge 0)\\
\frac{G(x)-\sum_{i=0}^{k-1}g_iz^i}{x^k}
&=\sum_{n\ge 0}g_{n+k}x^n, &\qquad (\mbox{integer }k\ge 0)\\
\alpha F(x)+\beta G(x)
&= \sum_{n\ge 0} (\alpha f_n+\beta g_n)x^n\\
F(x)G(x)
&= \sum_{n\ge 0}\sum_{k=0}^nf_kg_{n-k}x^n\\
G(cx)
&= \sum_{n\ge 0} c^ng_n x^n\\
G'(x)
&=
\sum_{n\ge 0}(n+1)g_{n+1}x^n\\
\frac{G(x)}{1-x}
&=\sum_{n\ge 0}\left(\sum_{k=0}^ng_k\right)x^n
\end{align}
</math>
}}

When manipulating generating functions, these rules are applied backwards; that is, from the right-hand-side to the left-hand-side.

==== Expanding generating functions ====
The last step of solving recurrences by generating function is expanding the closed form generating function <math>G(x)</math> to evaluate its <math>n</math>-th coefficient. In principle, we can always use the [http://en.wikipedia.org/wiki/Taylor_series Taylor series]
:<math>G(x)=\sum_{n\ge 0}\frac{G^{(n)}(0)}{n!}x^n</math>,
where <math>G^{(n)}(0)</math> is the value of the <math>n</math>-th derivative of <math>G(x)</math> evaluated at <math>x=0</math>.

Some interesting special cases are very useful.

;Geometric sequence
In the example of Fibonacci numbers, we use the well known geometric series:
:<math>\frac{1}{1-x}=\sum_{n\ge 0}x^n</math>.
It is useful when we can express the generating function in the form of <math>G(x)=\frac{a_1}{1-b_1x}+\frac{a_2}{1-b_2x}+\cdots+\frac{a_k}{1-b_kx}</math>. The coefficient of <math>x^n</math> in such <math>G(x)</math> is <math>a_1b_1^n+a_2b_2^n+\cdots+a_kb_k^n</math>.
;Binomial theorem
The <math>n</math>-th derivative of <math>(1+x)^\alpha</math> for some real <math>\alpha</math> is
:<math>\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-n+1)(1+x)^{\alpha-n}</math>.
By Taylor series, we get a generalized version of the binomial theorem known as [http://en.wikipedia.org/wiki/Binomial_coefficient#Newton.27s_binomial_series '''Newton's formula''']:
:<math>(1+x)^\alpha=\sum_{n\ge 0}{\alpha\choose n}x^{n}</math>,
where <math>{\alpha\choose n}</math> is the '''generalized binomial coefficient''' defined by
:<math>{\alpha\choose n}=\frac{\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-n+1)}{n!}</math>.

In the last lecture we gave a combinatorial proof of the number of <math>k</math>-multisets on an <math>n</math>-set. Now we give a generating function approach to the problem.

Let <math>S=\{x_1,x_2,\ldots,x_n\}</math> be an <math>n</math>-element set. We have
:<math>(1+x_1+x_1^2+\cdots)(1+x_2+x_2^2+\cdots)\cdots(1+x_n+x_n^2+\cdots)=\sum_{m:S\rightarrow\mathbb{N}} \prod_{x_i\in S}x_i^{m(x_i)}</math>,
where each <math>m:S\rightarrow\mathbb{N}</math> species a possible multiset on <math>S</math> with multiplicity function <math>m</math>.

Let all <math>x_i=x</math>. Then
:<math>
\begin{align}
(1+x+x^2+\cdots)^n
&=
\sum_{m:S\rightarrow\mathbb{N}}x^{m(x_1)+\cdots+m(x_n)}\\
&=
\sum_{\text{multiset }M\text{ on }S}x^{|M|}\\
&=
\sum_{k\ge 0}\left({n\choose k}\right)x^k.
\end{align}
</math>
The last equation is due to the the definition of <math>\left({n\choose k}\right)</math>. Our task is to evaluate <math>\left({n\choose k}\right)</math>.

Due to the geometric sequence and the Newton's formula
:<math>
(1+x+x^2+\cdots)^n=(1-x)^{-n}=\sum_{k\ge 0}{-n\choose k}(-x)^k.
</math>
So
:<math>
\left({n\choose k}\right)=(-1)^k{-n\choose k}={n+k-1\choose k}.
</math>
The last equation is due to the definition of the generalized binomial coefficient. We use an analytic (generating function) proof to get the same result of <math>\left({n\choose k}\right)</math> as the combinatorial proof.

Randomized Algorithms (Spring 2010)/Fingerprinting

2010-06-05T10:13:28Z

210.28.131.14: /* Communication complexity */

== Fingerprinting ==

=== Checking identities ===
==== Example: Checking matrix multiplication ====
Consider the following problem:
* Given as the input three <math>n\times n</math> matrices <math>A,B</math> and <math>C</math>,
* check whether <math>C=AB</math>.

{|border="1"
|'''Algorithm (Freivalds)'''
*pick a vector <math>r \in\{0, 1\}^n</math> uniformly at random;
*if <math>A(Br) = Cr</math> then return "yes" else return "no";
|}

If <math>AB=C</math> then <math>A(Br) = Cr</math> for any <math>r \in\{0, 1\}^n</math>, thus the algorithm always returns "yes".

{|border="1"
|'''Lemma'''
:If <math>AB\neq C</math> then for a uniformly random <math>r \in\{0, 1\}^n</math>,
::<math>\Pr[A(Br) = Cr]\le \frac{1}{2}</math>.
|}

==== Example: Checking polynomial identities ====
Consider the following problem:
* Given as the input two multivariate polynomials <math>P_1(x_1,\ldots,x_n)</math> and <math>P_2(x_1,\ldots,x_n)</math>,
* check whether <math>P_1\equiv P_2</math>.

{|border="1"
|'''Algorithm (Schwartz-Zippel)'''
*pick <math>r_1, \ldots , r_n</math> independently and uniformly at random from a set <math>S</math>;
*if <math>P_1(r_1, \ldots , r_n) = P_2(r_1, \ldots , r_n)</math> then return “yes” else return “no”;
|}

{|border="1"
|'''Theorem (Schwartz-Zippel)'''
: Let <math>Q(x_1,\ldots,x_n)</math> be a multivariate polynomial of degree <math>d</math> defined over a field <math>\mathbb{F}</math>. Fix any finite set <math>S\subset\mathbb{F}</math>, and let <math>r_1,\ldots,r_n</math> be chosen independently and uniformly at random from <math>S</math>. Then
::<math>\Pr[Q(r_1,\ldots,r_n)=0\mid Q\not\equiv 0]\le\frac{d}{|S|}.</math>
|}

==== Fingerprinting ====
Suppose we want to compare two items <math>Z_1</math> and <math>Z_2</math>. Instead of comparing them directly, we compute random '''fingerprints''' <math>\mathrm{FING}(Z_1)</math> and <math>\mathrm{FING}(Z_2)</math> and compare these. The fingerprints has the following properties:
* If <math>Z_1\neq Z_2</math> then <math>\Pr[\mathrm{FING}(Z_1)=\mathrm{FING}(Z_2)]</math> is small.
* It is much more to compute and compare the fingerprints than to compare <math>Z_1</math> and <math>Z_2</math> directly.

For Freivald's algorithm, the items to compare are two <math>n\times n</math> matrices <math>AB</math> and <math>C</math>, and given an <math>n\times n</math> matrix <math>M</math>, its random fingerprint is computed as <math>\mathrm{FING}(M)=Mr</math> for a uniformly random <math>r\in\{0,1\}^n</math>.

For the Schwartz-Zippel algorithm, the items to compare are two polynomials <math>P_1(x_1,\ldots,x_n)</math> and <math>P_2(x_1,\ldots,x_n)</math>, and given a polynomial <math>Q(x_1,\ldots,x_n)</math>, its random fingerprint is computed as <math>\mathrm{FING}(Q)=Q(r_1,\ldots,r_n)</math> for <math>r_i</math> chosen independently and uniformly at random from some fixed set <math>S</math>.

=== Communication complexity ===
Alice and Bob are two entities. Alice has a private input <math>x</math> and Bob has a private input <math>y</math>. Together they want to compute a function <math>f(x,y)</math> by communicating with each other. This is the model of '''communication complexity''' due to Yao.

In the communication complexity model, the local computational costs are ignored. The complexity of algorithms (also called communication protocols here) are measured by the number of bits communicated between Alice and Bob.

One of the basic function is IDENTITY, defined as
:<math>
\mathrm{IDENTITY}(x,y)=
\begin{cases}
1& \mbox{if } x=y,\\
0& \mbox{otherwise.}
\end{cases}</math>

A trivial way to solve IDENTITY is to let Bob send <math>y</math> to Alice. Supposed that <math>x,y\in\{0,1\}^n</math>, this costs <math>n</math> bits of communications.

=== Randomized pattern matching ===

=== Checking distinctness ===

== Probabilistic Checkable Proofs (PCPs) ==

Randomized Algorithms (Spring 2010)/Fingerprinting

2010-06-04T13:44:26Z

210.28.131.14: /* Universal hashing */

== Fingerprinting ==

=== Checking identities ===
==== Example: Checking matrix multiplication ====
Consider the following problem:
* Given as the input three <math>n\times n</math> matrices <math>A,B</math> and <math>C</math>,
* check whether <math>C=AB</math>.

{|border="1"
|'''Algorithm (Freivalds)'''
*pick a vector <math>r \in\{0, 1\}^n</math> uniformly at random;
*if <math>A(Br) = Cr</math> then return "yes" else return "no";
|}

If <math>AB=C</math> then <math>A(Br) = Cr</math> for any <math>r \in\{0, 1\}^n</math>, thus the algorithm always returns "yes".

{|border="1"
|'''Lemma'''
:If <math>AB\neq C</math> then for a uniformly random <math>r \in\{0, 1\}^n</math>,
::<math>\Pr[A(Br) = Cr]\le \frac{1}{2}</math>.
|}

==== Example: Checking polynomial identities ====
Consider the following problem:
* Given as the input two multivariate polynomials <math>P_1(x_1,\ldots,x_n)</math> and <math>P_2(x_1,\ldots,x_n)</math>,
* check whether <math>P_1\equiv P_2</math>.

{|border="1"
|'''Algorithm (Schwartz-Zippel)'''
*pick <math>r_1, \ldots , r_n</math> independently and uniformly at random from a set <math>S</math>;
*if <math>P_1(r_1, \ldots , r_n) = P_2(r_1, \ldots , r_n)</math> then return “yes” else return “no”;
|}

{|border="1"
|'''Theorem (Schwartz-Zippel)'''
: Let <math>Q(x_1,\ldots,x_n)</math> be a multivariate polynomial of degree <math>d</math> defined over a field <math>\mathbb{F}</math>. Fix any finite set <math>S\subset\mathbb{F}</math>, and let <math>r_1,\ldots,r_n</math> be chosen independently and uniformly at random from <math>S</math>. Then
::<math>\Pr[Q(r_1,\ldots,r_n)=0\mid Q\not\equiv 0]\le\frac{d}{|S|}.</math>
|}

==== Fingerprinting ====
Suppose we want to compare two items <math>Z_1</math> and <math>Z_2</math>. Instead of comparing them directly, we compute random '''fingerprints''' <math>\mathrm{FING}(Z_1)</math> and <math>\mathrm{FING}(Z_2)</math> and compare these. The fingerprints has the following properties:
* If <math>Z_1\neq Z_2</math> then <math>\Pr[\mathrm{FING}(Z_1)=\mathrm{FING}(Z_2)]</math> is small.
* It is much more to compute and compare the fingerprints than to compare <math>Z_1</math> and <math>Z_2</math> directly.

For Freivald's algorithm, the items to compare are two <math>n\times n</math> matrices <math>AB</math> and <math>C</math>, and given an <math>n\times n</math> matrix <math>M</math>, its random fingerprint is computed as <math>\mathrm{FING}(M)=Mr</math> for a uniformly random <math>r\in\{0,1\}^n</math>.

For the Schwartz-Zippel algorithm, the items to compare are two polynomials <math>P_1(x_1,\ldots,x_n)</math> and <math>P_2(x_1,\ldots,x_n)</math>, and given a polynomial <math>Q(x_1,\ldots,x_n)</math>, its random fingerprint is computed as <math>\mathrm{FING}(Q)=Q(r_1,\ldots,r_n)</math> for <math>r_i</math> chosen independently and uniformly at random from some fixed set <math>S</math>.

=== Communication complexity ===
Alice and Bob are two entities. Alice has a private input <math>x</math> and Bob has a private input <math>y</math>. Together they want to compute a function <math>f(x,y)</math> by communicating with each other. This is the model of '''communication complexity''' due to Andrew Chi-Chih Yao.

In the communication complexity model, the local computational costs are ignored. The complexity of algorithms (also called communication protocols here) are measured by the number of bits communicated between Alice and Bob.

One of the basic function is IDENTITY, defined as
:<math>
\mathrm{IDENTITY}(x,y)=
\begin{cases}
1& \mbox{if } x=y,\\
0& \mbox{otherwise.}
\end{cases}</math>

A trivial way to solve IDENTITY is to let Bob send <math>y</math> to Alice. Supposed that <math>x,y\in\{0,1\}^n</math>, this costs <math>n</math> bits of communications.

=== Randomized pattern matching ===

=== Checking distinctness ===

== Probabilistic Checkable Proofs (PCPs) ==

Randomized Algorithms (Spring 2010)/Fingerprinting

2010-06-04T13:43:56Z

210.28.131.14: /* Communication complexity */

== Fingerprinting ==

=== Checking identities ===
==== Example: Checking matrix multiplication ====
Consider the following problem:
* Given as the input three <math>n\times n</math> matrices <math>A,B</math> and <math>C</math>,
* check whether <math>C=AB</math>.

{|border="1"
|'''Algorithm (Freivalds)'''
*pick a vector <math>r \in\{0, 1\}^n</math> uniformly at random;
*if <math>A(Br) = Cr</math> then return "yes" else return "no";
|}

If <math>AB=C</math> then <math>A(Br) = Cr</math> for any <math>r \in\{0, 1\}^n</math>, thus the algorithm always returns "yes".

{|border="1"
|'''Lemma'''
:If <math>AB\neq C</math> then for a uniformly random <math>r \in\{0, 1\}^n</math>,
::<math>\Pr[A(Br) = Cr]\le \frac{1}{2}</math>.
|}

==== Example: Checking polynomial identities ====
Consider the following problem:
* Given as the input two multivariate polynomials <math>P_1(x_1,\ldots,x_n)</math> and <math>P_2(x_1,\ldots,x_n)</math>,
* check whether <math>P_1\equiv P_2</math>.

{|border="1"
|'''Algorithm (Schwartz-Zippel)'''
*pick <math>r_1, \ldots , r_n</math> independently and uniformly at random from a set <math>S</math>;
*if <math>P_1(r_1, \ldots , r_n) = P_2(r_1, \ldots , r_n)</math> then return “yes” else return “no”;
|}

{|border="1"
|'''Theorem (Schwartz-Zippel)'''
: Let <math>Q(x_1,\ldots,x_n)</math> be a multivariate polynomial of degree <math>d</math> defined over a field <math>\mathbb{F}</math>. Fix any finite set <math>S\subset\mathbb{F}</math>, and let <math>r_1,\ldots,r_n</math> be chosen independently and uniformly at random from <math>S</math>. Then
::<math>\Pr[Q(r_1,\ldots,r_n)=0\mid Q\not\equiv 0]\le\frac{d}{|S|}.</math>
|}

==== Fingerprinting ====
Suppose we want to compare two items <math>Z_1</math> and <math>Z_2</math>. Instead of comparing them directly, we compute random '''fingerprints''' <math>\mathrm{FING}(Z_1)</math> and <math>\mathrm{FING}(Z_2)</math> and compare these. The fingerprints has the following properties:
* If <math>Z_1\neq Z_2</math> then <math>\Pr[\mathrm{FING}(Z_1)=\mathrm{FING}(Z_2)]</math> is small.
* It is much more to compute and compare the fingerprints than to compare <math>Z_1</math> and <math>Z_2</math> directly.

For Freivald's algorithm, the items to compare are two <math>n\times n</math> matrices <math>AB</math> and <math>C</math>, and given an <math>n\times n</math> matrix <math>M</math>, its random fingerprint is computed as <math>\mathrm{FING}(M)=Mr</math> for a uniformly random <math>r\in\{0,1\}^n</math>.

For the Schwartz-Zippel algorithm, the items to compare are two polynomials <math>P_1(x_1,\ldots,x_n)</math> and <math>P_2(x_1,\ldots,x_n)</math>, and given a polynomial <math>Q(x_1,\ldots,x_n)</math>, its random fingerprint is computed as <math>\mathrm{FING}(Q)=Q(r_1,\ldots,r_n)</math> for <math>r_i</math> chosen independently and uniformly at random from some fixed set <math>S</math>.

=== Communication complexity ===
Alice and Bob are two entities. Alice has a private input <math>x</math> and Bob has a private input <math>y</math>. Together they want to compute a function <math>f(x,y)</math> by communicating with each other. This is the model of '''communication complexity''' due to Andrew Chi-Chih Yao.

In the communication complexity model, the local computational costs are ignored. The complexity of algorithms (also called communication protocols here) are measured by the number of bits communicated between Alice and Bob.

One of the basic function is IDENTITY, defined as
:<math>
\mathrm{IDENTITY}(x,y)=
\begin{cases}
1& \mbox{if } x=y,\\
0& \mbox{otherwise.}
\end{cases}</math>

A trivial way to solve IDENTITY is to let Bob send <math>y</math> to Alice. Supposed that <math>x,y\in\{0,1\}^n</math>, this costs <math>n</math> bits of communications.

=== Randomized pattern matching ===

=== Universal hashing ===

;Example<nowiki>:</nowiki> checking distinctness

== Probabilistic Checkable Proofs (PCPs) ==

Randomized Algorithms (Spring 2010)/Fingerprinting

2010-06-04T11:45:43Z

210.28.131.14: /* Communication complexity */

== Fingerprinting ==

=== Checking identities ===
==== Example: Checking matrix multiplication ====
Consider the following problem:
* Given as the input three <math>n\times n</math> matrices <math>A,B</math> and <math>C</math>,
* check whether <math>C=AB</math>.

{|border="1"
|'''Algorithm (Freivalds)'''
*pick a vector <math>r \in\{0, 1\}^n</math> uniformly at random;
*if <math>A(Br) = Cr</math> then return "yes" else return "no";
|}

If <math>AB=C</math> then <math>A(Br) = Cr</math> for any <math>r \in\{0, 1\}^n</math>, thus the algorithm always returns "yes".

{|border="1"
|'''Lemma'''
:If <math>AB\neq C</math> then for a uniformly random <math>r \in\{0, 1\}^n</math>,
::<math>\Pr[A(Br) = Cr]\le \frac{1}{2}</math>.
|}

==== Example: Checking polynomial identities ====
Consider the following problem:
* Given as the input two multivariate polynomials <math>P_1(x_1,\ldots,x_n)</math> and <math>P_2(x_1,\ldots,x_n)</math>,
* check whether <math>P_1\equiv P_2</math>.

{|border="1"
|'''Algorithm (Schwartz-Zippel)'''
*pick <math>r_1, \ldots , r_n</math> independently and uniformly at random from a set <math>S</math>;
*if <math>P_1(r_1, \ldots , r_n) = P_2(r_1, \ldots , r_n)</math> then return “yes” else return “no”;
|}

{|border="1"
|'''Theorem (Schwartz-Zippel)'''
: Let <math>Q(x_1,\ldots,x_n)</math> be a multivariate polynomial of degree <math>d</math> defined over a field <math>\mathbb{F}</math>. Fix any finite set <math>S\subset\mathbb{F}</math>, and let <math>r_1,\ldots,r_n</math> be chosen independently and uniformly at random from <math>S</math>. Then
::<math>\Pr[Q(r_1,\ldots,r_n)=0\mid Q\not\equiv 0]\le\frac{d}{|S|}.</math>
|}

==== Fingerprinting ====
Suppose we want to compare two items <math>Z_1</math> and <math>Z_2</math>. Instead of comparing them directly, we compute random '''fingerprints''' <math>\mathrm{FING}(Z_1)</math> and <math>\mathrm{FING}(Z_2)</math> and compare these. The fingerprints has the following properties:
* If <math>Z_1\neq Z_2</math> then <math>\Pr[\mathrm{FING}(Z_1)=\mathrm{FING}(Z_2)]</math> is small.
* It is much more to compute and compare the fingerprints than to compare <math>Z_1</math> and <math>Z_2</math> directly.

For Freivald's algorithm, the items to compare are two <math>n\times n</math> matrices <math>AB</math> and <math>C</math>, and given an <math>n\times n</math> matrix <math>M</math>, its random fingerprint is computed as <math>\mathrm{FING}(M)=Mr</math> for a uniformly random <math>r\in\{0,1\}^n</math>.

For the Schwartz-Zippel algorithm, the items to compare are two polynomials <math>P_1(x_1,\ldots,x_n)</math> and <math>P_2(x_1,\ldots,x_n)</math>, and given a polynomial <math>Q(x_1,\ldots,x_n)</math>, its random fingerprint is computed as <math>\mathrm{FING}(Q)=Q(r_1,\ldots,r_n)</math> for <math>r_i</math> chosen independently and uniformly at random from some fixed set <math>S</math>.

=== Communication complexity ===

=== Randomized pattern matching ===

=== Universal hashing ===

;Example<nowiki>:</nowiki> checking distinctness

== Probabilistic Checkable Proofs (PCPs) ==

Randomized Algorithms (Spring 2010)/Fingerprinting

2010-06-04T11:45:30Z

210.28.131.14: /* Example: Randomized pattern matching */

== Fingerprinting ==

=== Checking identities ===
==== Example: Checking matrix multiplication ====
Consider the following problem:
* Given as the input three <math>n\times n</math> matrices <math>A,B</math> and <math>C</math>,
* check whether <math>C=AB</math>.

{|border="1"
|'''Algorithm (Freivalds)'''
*pick a vector <math>r \in\{0, 1\}^n</math> uniformly at random;
*if <math>A(Br) = Cr</math> then return "yes" else return "no";
|}

If <math>AB=C</math> then <math>A(Br) = Cr</math> for any <math>r \in\{0, 1\}^n</math>, thus the algorithm always returns "yes".

{|border="1"
|'''Lemma'''
:If <math>AB\neq C</math> then for a uniformly random <math>r \in\{0, 1\}^n</math>,
::<math>\Pr[A(Br) = Cr]\le \frac{1}{2}</math>.
|}

==== Example: Checking polynomial identities ====
Consider the following problem:
* Given as the input two multivariate polynomials <math>P_1(x_1,\ldots,x_n)</math> and <math>P_2(x_1,\ldots,x_n)</math>,
* check whether <math>P_1\equiv P_2</math>.

{|border="1"
|'''Algorithm (Schwartz-Zippel)'''
*pick <math>r_1, \ldots , r_n</math> independently and uniformly at random from a set <math>S</math>;
*if <math>P_1(r_1, \ldots , r_n) = P_2(r_1, \ldots , r_n)</math> then return “yes” else return “no”;
|}

{|border="1"
|'''Theorem (Schwartz-Zippel)'''
: Let <math>Q(x_1,\ldots,x_n)</math> be a multivariate polynomial of degree <math>d</math> defined over a field <math>\mathbb{F}</math>. Fix any finite set <math>S\subset\mathbb{F}</math>, and let <math>r_1,\ldots,r_n</math> be chosen independently and uniformly at random from <math>S</math>. Then
::<math>\Pr[Q(r_1,\ldots,r_n)=0\mid Q\not\equiv 0]\le\frac{d}{|S|}.</math>
|}

==== Fingerprinting ====
Suppose we want to compare two items <math>Z_1</math> and <math>Z_2</math>. Instead of comparing them directly, we compute random '''fingerprints''' <math>\mathrm{FING}(Z_1)</math> and <math>\mathrm{FING}(Z_2)</math> and compare these. The fingerprints has the following properties:
* If <math>Z_1\neq Z_2</math> then <math>\Pr[\mathrm{FING}(Z_1)=\mathrm{FING}(Z_2)]</math> is small.
* It is much more to compute and compare the fingerprints than to compare <math>Z_1</math> and <math>Z_2</math> directly.

For Freivald's algorithm, the items to compare are two <math>n\times n</math> matrices <math>AB</math> and <math>C</math>, and given an <math>n\times n</math> matrix <math>M</math>, its random fingerprint is computed as <math>\mathrm{FING}(M)=Mr</math> for a uniformly random <math>r\in\{0,1\}^n</math>.

For the Schwartz-Zippel algorithm, the items to compare are two polynomials <math>P_1(x_1,\ldots,x_n)</math> and <math>P_2(x_1,\ldots,x_n)</math>, and given a polynomial <math>Q(x_1,\ldots,x_n)</math>, its random fingerprint is computed as <math>\mathrm{FING}(Q)=Q(r_1,\ldots,r_n)</math> for <math>r_i</math> chosen independently and uniformly at random from some fixed set <math>S</math>.

==== Communication complexity ====

=== Randomized pattern matching ===

=== Universal hashing ===

;Example<nowiki>:</nowiki> checking distinctness

== Probabilistic Checkable Proofs (PCPs) ==

Randomized Algorithms (Spring 2010)/Fingerprinting

2010-06-04T11:45:15Z

210.28.131.14: /* Example: Identity checking */

== Fingerprinting ==

=== Checking identities ===
==== Example: Checking matrix multiplication ====
Consider the following problem:
* Given as the input three <math>n\times n</math> matrices <math>A,B</math> and <math>C</math>,
* check whether <math>C=AB</math>.

{|border="1"
|'''Algorithm (Freivalds)'''
*pick a vector <math>r \in\{0, 1\}^n</math> uniformly at random;
*if <math>A(Br) = Cr</math> then return "yes" else return "no";
|}

If <math>AB=C</math> then <math>A(Br) = Cr</math> for any <math>r \in\{0, 1\}^n</math>, thus the algorithm always returns "yes".

{|border="1"
|'''Lemma'''
:If <math>AB\neq C</math> then for a uniformly random <math>r \in\{0, 1\}^n</math>,
::<math>\Pr[A(Br) = Cr]\le \frac{1}{2}</math>.
|}

==== Example: Checking polynomial identities ====
Consider the following problem:
* Given as the input two multivariate polynomials <math>P_1(x_1,\ldots,x_n)</math> and <math>P_2(x_1,\ldots,x_n)</math>,
* check whether <math>P_1\equiv P_2</math>.

{|border="1"
|'''Algorithm (Schwartz-Zippel)'''
*pick <math>r_1, \ldots , r_n</math> independently and uniformly at random from a set <math>S</math>;
*if <math>P_1(r_1, \ldots , r_n) = P_2(r_1, \ldots , r_n)</math> then return “yes” else return “no”;
|}

{|border="1"
|'''Theorem (Schwartz-Zippel)'''
: Let <math>Q(x_1,\ldots,x_n)</math> be a multivariate polynomial of degree <math>d</math> defined over a field <math>\mathbb{F}</math>. Fix any finite set <math>S\subset\mathbb{F}</math>, and let <math>r_1,\ldots,r_n</math> be chosen independently and uniformly at random from <math>S</math>. Then
::<math>\Pr[Q(r_1,\ldots,r_n)=0\mid Q\not\equiv 0]\le\frac{d}{|S|}.</math>
|}

==== Fingerprinting ====
Suppose we want to compare two items <math>Z_1</math> and <math>Z_2</math>. Instead of comparing them directly, we compute random '''fingerprints''' <math>\mathrm{FING}(Z_1)</math> and <math>\mathrm{FING}(Z_2)</math> and compare these. The fingerprints has the following properties:
* If <math>Z_1\neq Z_2</math> then <math>\Pr[\mathrm{FING}(Z_1)=\mathrm{FING}(Z_2)]</math> is small.
* It is much more to compute and compare the fingerprints than to compare <math>Z_1</math> and <math>Z_2</math> directly.

For Freivald's algorithm, the items to compare are two <math>n\times n</math> matrices <math>AB</math> and <math>C</math>, and given an <math>n\times n</math> matrix <math>M</math>, its random fingerprint is computed as <math>\mathrm{FING}(M)=Mr</math> for a uniformly random <math>r\in\{0,1\}^n</math>.

For the Schwartz-Zippel algorithm, the items to compare are two polynomials <math>P_1(x_1,\ldots,x_n)</math> and <math>P_2(x_1,\ldots,x_n)</math>, and given a polynomial <math>Q(x_1,\ldots,x_n)</math>, its random fingerprint is computed as <math>\mathrm{FING}(Q)=Q(r_1,\ldots,r_n)</math> for <math>r_i</math> chosen independently and uniformly at random from some fixed set <math>S</math>.

==== Communication complexity ====

==== Example: Randomized pattern matching ====

=== Universal hashing ===

;Example<nowiki>:</nowiki> checking distinctness

== Probabilistic Checkable Proofs (PCPs) ==

Randomized Algorithms (Spring 2010)/Fingerprinting

2010-06-04T11:42:53Z

210.28.131.14: /* Fingerprinting */

== Fingerprinting ==

=== Checking identities ===
==== Example: Checking matrix multiplication ====
Consider the following problem:
* Given as the input three <math>n\times n</math> matrices <math>A,B</math> and <math>C</math>,
* check whether <math>C=AB</math>.

{|border="1"
|'''Algorithm (Freivalds)'''
*pick a vector <math>r \in\{0, 1\}^n</math> uniformly at random;
*if <math>A(Br) = Cr</math> then return "yes" else return "no";
|}

If <math>AB=C</math> then <math>A(Br) = Cr</math> for any <math>r \in\{0, 1\}^n</math>, thus the algorithm always returns "yes".

{|border="1"
|'''Lemma'''
:If <math>AB\neq C</math> then for a uniformly random <math>r \in\{0, 1\}^n</math>,
::<math>\Pr[A(Br) = Cr]\le \frac{1}{2}</math>.
|}

==== Example: Checking polynomial identities ====
Consider the following problem:
* Given as the input two multivariate polynomials <math>P_1(x_1,\ldots,x_n)</math> and <math>P_2(x_1,\ldots,x_n)</math>,
* check whether <math>P_1\equiv P_2</math>.

{|border="1"
|'''Algorithm (Schwartz-Zippel)'''
*pick <math>r_1, \ldots , r_n</math> independently and uniformly at random from a set <math>S</math>;
*if <math>P_1(r_1, \ldots , r_n) = P_2(r_1, \ldots , r_n)</math> then return “yes” else return “no”;
|}

{|border="1"
|'''Theorem (Schwartz-Zippel)'''
: Let <math>Q(x_1,\ldots,x_n)</math> be a multivariate polynomial of degree <math>d</math> defined over a field <math>\mathbb{F}</math>. Fix any finite set <math>S\subset\mathbb{F}</math>, and let <math>r_1,\ldots,r_n</math> be chosen independently and uniformly at random from <math>S</math>. Then
::<math>\Pr[Q(r_1,\ldots,r_n)=0\mid Q\not\equiv 0]\le\frac{d}{|S|}.</math>
|}

==== Fingerprinting ====
Suppose we want to compare two items <math>Z_1</math> and <math>Z_2</math>. Instead of comparing them directly, we compute random '''fingerprints''' <math>\mathrm{FING}(Z_1)</math> and <math>\mathrm{FING}(Z_2)</math> and compare these. The fingerprints has the following properties:
* If <math>Z_1\neq Z_2</math> then <math>\Pr[\mathrm{FING}(Z_1)=\mathrm{FING}(Z_2)]</math> is small.
* It is much more to compute and compare the fingerprints than to compare <math>Z_1</math> and <math>Z_2</math> directly.

For Freivald's algorithm, the items to compare are two <math>n\times n</math> matrices <math>AB</math> and <math>C</math>, and given an <math>n\times n</math> matrix <math>M</math>, its random fingerprint is computed as <math>\mathrm{FING}(M)=Mr</math> for a uniformly random <math>r\in\{0,1\}^n</math>.

For the Schwartz-Zippel algorithm, the items to compare are two polynomials <math>P_1(x_1,\ldots,x_n)</math> and <math>P_2(x_1,\ldots,x_n)</math>, and given a polynomial <math>Q(x_1,\ldots,x_n)</math>, its random fingerprint is computed as <math>\mathrm{FING}(Q)=Q(r_1,\ldots,r_n)</math> for <math>r_i</math> chosen independently and uniformly at random from some fixed set <math>S</math>.

==== Example: Identity checking ====

==== Example: Randomized pattern matching ====

=== Universal hashing ===

;Example<nowiki>:</nowiki> checking distinctness

== Probabilistic Checkable Proofs (PCPs) ==

Randomized Algorithms (Spring 2010)/Fingerprinting

2010-06-04T11:39:28Z

210.28.131.14: /* Fingerprinting */

Randomized Algorithms (Spring 2010)/Fingerprinting

2010-06-04T11:29:46Z

210.28.131.14: /* Fingerprinting */

Randomized Algorithms (Spring 2010)/Fingerprinting

2010-06-04T11:29:34Z

210.28.131.14: /* Fingerprinting */

Randomized Algorithms (Spring 2010)/Fingerprinting

2010-06-04T11:28:44Z

210.28.131.14: /* Two examples */

== Fingerprinting ==

==== Example: Checking matrix multiplication ====
Consider the following problem:
* Given as the input three <math>n\times n</math> matrices <math>A,B</math> and <math>C</math>,
* check whether <math>C=AB</math>.

{|border="1"
|'''Algorithm (Freivalds)'''
*pick a vector <math>r \in\{0, 1\}^n</math> uniformly at random;
*if <math>A(Br) = Cr</math> then return "yes" else return "no";
|}

If <math>AB=C</math> then <math>A(Br) = Cr</math> for any <math>r \in\{0, 1\}^n</math>, thus the algorithm always returns "yes".

{|border="1"
|'''Lemma'''
:If <math>AB\neq C</math> then for a uniformly random <math>r \in\{0, 1\}^n</math>,
::<math>\Pr[A(Br) = Cr]\le \frac{1}{2}</math>.
|}

==== Example: Checking polynomial identities ====
Consider the following problem:
* Given as the input two multivariate polynomials <math>P_1(x_1,\ldots,x_n)</math> and <math>P_2(x_1,\ldots,x_n)</math>,
* check whether <math>P_1\equiv P_2</math>.

{|border="1"
|'''Algorithm (Schwartz-Zippel)'''
*pick <math>r_1, \ldots , r_n</math> independently and uniformly at random from a set <math>S</math>;
*if <math>P_1(r_1, \ldots , r_n) = P_2(r_1, \ldots , r_n)</math> then return “yes” else return “no”;
|}

{|border="1"
|'''Theorem (Schwartz-Zippel)'''
: Let <math>Q(x_1,\ldots,x_n)</math> be a multivariate polynomial of degree <math>d</math> defined over a field <math>\mathbb{F}</math>. Fix any finite set <math>S\subset\mathbb{F}</math>, and let <math>r_1,\ldots,r_n</math> be chosen independently and uniformly at random from <math>S</math>. Then
::<math>\Pr[Q(r_1,\ldots,r_n)=0\mid Q\not\equiv 0]\le\frac{d}{|S|}.</math>
|}

===Fingerprinting ===

==== Example: Identity checking ====

==== Example: Randomized pattern matching ====

=== Universal hashing ===

;Example<nowiki>:</nowiki> checking distinctness

== Probabilistic Checkable Proofs (PCPs) ==

Randomized Algorithms (Spring 2010)/Fingerprinting

2010-06-04T11:28:10Z

210.28.131.14: /* Evaluating over a random field */

== Fingerprinting ==

=== Two examples ===

==== Example: Checking matrix multiplication ====
Consider the following problem:
* Given as the input three <math>n\times n</math> matrices <math>A,B</math> and <math>C</math>,
* check whether <math>C=AB</math>.

{|border="1"
|'''Algorithm (Freivalds)'''
*pick a vector <math>r \in\{0, 1\}^n</math> uniformly at random;
*if <math>A(Br) = Cr</math> then return "yes" else return "no";
|}

If <math>AB=C</math> then <math>A(Br) = Cr</math> for any <math>r \in\{0, 1\}^n</math>, thus the algorithm always returns "yes".

{|border="1"
|'''Lemma'''
:If <math>AB\neq C</math> then for a uniformly random <math>r \in\{0, 1\}^n</math>,
::<math>\Pr[A(Br) = Cr]\le \frac{1}{2}</math>.
|}

==== Example: Checking polynomial identities ====
Consider the following problem:
* Given as the input two multivariate polynomials <math>P_1(x_1,\ldots,x_n)</math> and <math>P_2(x_1,\ldots,x_n)</math>,
* check whether <math>P_1\equiv P_2</math>.

{|border="1"
|'''Algorithm (Schwartz-Zippel)'''
*pick <math>r_1, \ldots , r_n</math> independently and uniformly at random from a set <math>S</math>;
*if <math>P_1(r_1, \ldots , r_n) = P_2(r_1, \ldots , r_n)</math> then return “yes” else return “no”;
|}

{|border="1"
|'''Theorem (Schwartz-Zippel)'''
: Let <math>Q(x_1,\ldots,x_n)</math> be a multivariate polynomial of degree <math>d</math> defined over a field <math>\mathbb{F}</math>. Fix any finite set <math>S\subset\mathbb{F}</math>, and let <math>r_1,\ldots,r_n</math> be chosen independently and uniformly at random from <math>S</math>. Then
::<math>\Pr[Q(r_1,\ldots,r_n)=0\mid Q\not\equiv 0]\le\frac{d}{|S|}.</math>
|}

===Fingerprinting ===

==== Example: Identity checking ====

==== Example: Randomized pattern matching ====

=== Universal hashing ===

;Example<nowiki>:</nowiki> checking distinctness

== Probabilistic Checkable Proofs (PCPs) ==

Randomized Algorithms (Spring 2010)/Fingerprinting

2010-06-04T11:27:22Z

210.28.131.14: /* Evaluating at random points */

== Fingerprinting ==

=== Two examples ===

==== Example: Checking matrix multiplication ====
Consider the following problem:
* Given as the input three <math>n\times n</math> matrices <math>A,B</math> and <math>C</math>,
* check whether <math>C=AB</math>.

{|border="1"
|'''Algorithm (Freivalds)'''
*pick a vector <math>r \in\{0, 1\}^n</math> uniformly at random;
*if <math>A(Br) = Cr</math> then return "yes" else return "no";
|}

If <math>AB=C</math> then <math>A(Br) = Cr</math> for any <math>r \in\{0, 1\}^n</math>, thus the algorithm always returns "yes".

{|border="1"
|'''Lemma'''
:If <math>AB\neq C</math> then for a uniformly random <math>r \in\{0, 1\}^n</math>,
::<math>\Pr[A(Br) = Cr]\le \frac{1}{2}</math>.
|}

==== Example: Checking polynomial identities ====
Consider the following problem:
* Given as the input two multivariate polynomials <math>P_1(x_1,\ldots,x_n)</math> and <math>P_2(x_1,\ldots,x_n)</math>,
* check whether <math>P_1\equiv P_2</math>.

{|border="1"
|'''Algorithm (Schwartz-Zippel)'''
*pick <math>r_1, \ldots , r_n</math> independently and uniformly at random from a set <math>S</math>;
*if <math>P_1(r_1, \ldots , r_n) = P_2(r_1, \ldots , r_n)</math> then return “yes” else return “no”;
|}

{|border="1"
|'''Theorem (Schwartz-Zippel)'''
: Let <math>Q(x_1,\ldots,x_n)</math> be a multivariate polynomial of degree <math>d</math> defined over a field <math>\mathbb{F}</math>. Fix any finite set <math>S\subset\mathbb{F}</math>, and let <math>r_1,\ldots,r_n</math> be chosen independently and uniformly at random from <math>S</math>. Then
::<math>\Pr[Q(r_1,\ldots,r_n)=0\mid Q\not\equiv 0]\le\frac{d}{|S|}.</math>
|}

===Evaluating over a random field ===

==== Example: Identity checking ====

==== Example: Randomized pattern matching ====

=== Universal hashing ===

;Example<nowiki>:</nowiki> checking distinctness

== Probabilistic Checkable Proofs (PCPs) ==

Randomized Algorithms (Spring 2010)

2009-12-27T16:44:54Z

210.28.131.14:

{{Infobox
|name = Infobox
|bodystyle =
|title = 随机算法
Randomized Algorithms
|titlestyle =

|image = [[File:MR-randomized-algorithms.png|100px]]
|imagestyle =
|caption = ''Randomized Algorithms'' by Motwani and Raghavan
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = 尹一通
|header3 =
|label3 = Email
|data3 = yitong.yin@gmail.com yinyt@nju.edu.cn yinyt@lamda.nju.edu.cn
|header4 =
|label4= office
|data4= 蒙民伟楼 406
|header5 = Class
|label5 =
|data5 =
|header6 =
|label6 = Class meetings
|data6 = 8 am-10 am, Wednesday
|header7 =
|label7 = Place
|data7 =
|header8 =
|label8 = Office hours
|data8 = 2pm-5pm, Saturday, MMW 406
|header9 = Textbook
|label9 =
|data9 =
|header10 =
|label10 =
|data10 = Motwani and Raghavan, ''Randomized Algorithms''. Cambridge Univ Press, 1995.

|belowstyle = background:#ddf;
|below =
}}

This is the page for the class ''Randomized Algorithms'' for the Spring 2010 semester. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =
There is no announcement yet.

= Syllabus =
随机化（randomization）是现代计算机科学最重要的方法之一，近二十年来被广泛的应用于计算机科学的各个领域。在这些应用的背后，有一些共通的随机化原理。在随机算法这门课程中，我们将用数学的语言描述这些原理，将会讲授以下内容：
* 一些重要的随机算法的设计与分析；
* 概率论工具，其中包括概率分析的工具，也包括数学证明的概率方法 (the probabilistic method);
* 随机算法的概率模型，既包括一些算法模型，例如随机漫游 (random walks)，也包括复杂度模型——概率图灵机。
作为一门理论课程，这门课的内容偏重数学上的分析和证明。这么做的目的不仅仅是为了结果的严格性，而是因为用更聪明的方法去解决问题往往需要对问题本身的数学结构有深刻的认识。

=== 先修课程 Prerequisites ===
必须：离散数学，概率论。
推荐：算法设计与分析。

=== [[Randomized Algorithms (Spring 2010)/Course materials|教材和参考书 Course materials]] ===

=== [[Randomized Algorithms (Spring 2010)/Policies|规则 Policies]] ===

= Assignments =
There is no assignment yet.

= Lecture Notes =

Randomized Algorithms (Spring 2010)

2009-12-27T16:44:04Z

210.28.131.14:

{{Infobox
|name = Infobox
|bodystyle =
|title = 随机算法
Randomized Algorithms
|titlestyle =

|image = [[File:MR-randomized-algorithms.png|100px]]
|imagestyle =
|caption = ''Randomized Algorithms'' by Motwani and Raghavan
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = 尹一通
|header3 =
|label3 = Email
|data3 = yitong.yin@gmail.com yinyt@nju.edu.cn yinyt@lamda.nju.edu.cn
|header4 =
|label4= office
|data4= 蒙民伟楼 406
|header5 = Class
|label5 =
|data5 =
|header6 =
|label6 = Class meetings
|data6 = 8 am-10 am, Wednesday
|header7 =
|label7 = Place
|data7 =
|header8 =
|label8 = Office hours
|data8 = 2pm-5pm, Saturday, MMW 406
|header9 = Textbook
|label9 =
|data9 =
|header10 =
|label10 =
|data10 = Motwani and Raghavan, ''Randomized Algorithms''. Cambridge Univ Press, 1995.

|belowstyle = background:#ddf;
|below =
}}

This is the page for the class ''Randomized Algorithms'' for the Spring 2010 semester. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =
There is no announcement yet.

= Syllabus =
随机化（randomization）是现代计算机科学最重要的方法之一，近二十年来被广泛的应用于计算机科学的各个领域。在这些应用的背后，有一些共通的随机化原理。在随机算法这门课程中，我们将用数学的语言描述这些原理，将会讲授以下内容：
* 一些重要的随机算法的设计与分析；
* 概率论工具，其中包括概率分析的工具，也包括数学证明的概率方法 (the probabilistic method);
* 随机算法的概率模型，既包括一些算法模型，例如随机漫游 (random walks)，也包括复杂度模型——概率图灵机。
作为一门理论课程，这门课的内容偏重数学上的分析和证明。这么做的目的不仅仅是为了结果的严格性，而是因为设计一个聪明的算法通常都需要对问题本身的数学结构有深刻的认识。

=== 先修课程 Prerequisites ===
必须：离散数学，概率论。
推荐：算法设计与分析。

=== [[Randomized Algorithms (Spring 2010)/Course materials|教材和参考书 Course materials]] ===

=== [[Randomized Algorithms (Spring 2010)/Policies|规则 Policies]] ===

= Assignments =
There is no assignment yet.

= Lecture Notes =

Randomized Algorithms (Spring 2010)

2009-12-27T16:43:13Z

210.28.131.14:

{{Infobox
|name = Infobox
|bodystyle =
|title = 随机算法
Randomized Algorithms
|titlestyle =

|image = [[File:MR-randomized-algorithms.png|100px]]
|imagestyle =
|caption = ''Randomized Algorithms'' by Motwani and Raghavan
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = 尹一通
|header3 =
|label3 = Email
|data3 = yitong.yin@gmail.com yinyt@nju.edu.cn yinyt@lamda.nju.edu.cn
|header4 =
|label4= office
|data4= 蒙民伟楼 406
|header5 = Class
|label5 =
|data5 =
|header6 =
|label6 = Class meetings
|data6 = 8 am-10 am, Wednesday
|header7 =
|label7 = Place
|data7 =
|header8 =
|label8 = Office hours
|data8 = 2pm-5pm, Saturday, MMW 406
|header9 = Textbook
|label9 =
|data9 =
|header10 =
|label10 =
|data10 = Motwani and Raghavan, ''Randomized Algorithms''. Cambridge Univ Press, 1995.

|belowstyle = background:#ddf;
|below =
}}

This is the page for the class ''Randomized Algorithms'' for the Spring 2010 semester. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =
There is no announcement yet.

= Syllabus =
随机化（randomization）是现代计算机科学最重要的方法之一，近二十年来被广泛的应用于计算机科学的各个领域。在这些应用的背后，有一些共通的随机化原理。在随机算法这门课程中，我们将用数学的语言描述这些原理，将会讲授以下内容：
* 一些重要的随机算法的设计与分析；
* 概率论工具，其中包括概率分析的工具，也包括数学证明的概率方法 (the probabilistic method);
* 随机算法的概率模型，既包括一些算法模型，例如随机漫游 (random walks)，也包括复杂度模型——概率图灵机。
作为一门理论课程，这门课的内容将着重于数学上的分析和证明。这么做的目的不仅仅是为了结果的严格性，而是因为设计一个聪明的算法通常都需要对问题本身的数学结构有深刻的认识。

=== 先修课程 Prerequisites ===
必须：离散数学，概率论。
推荐：算法设计与分析。

=== [[Randomized Algorithms (Spring 2010)/Course materials|教材和参考书 Course materials]] ===

=== [[Randomized Algorithms (Spring 2010)/Policies|规则 Policies]] ===

= Assignments =
There is no assignment yet.

= Lecture Notes =

Randomized Algorithms (Spring 2010)

2009-12-27T16:41:53Z

210.28.131.14:

{{Infobox
|name = Infobox
|bodystyle =
|title = 随机算法
Randomized Algorithms
|titlestyle =

|image = [[File:MR-randomized-algorithms.png|100px]]
|imagestyle =
|caption = ''Randomized Algorithms'' by Motwani and Raghavan
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = 尹一通
|header3 =
|label3 = Email
|data3 = yitong.yin@gmail.com yinyt@nju.edu.cn yinyt@lamda.nju.edu.cn
|header4 =
|label4= office
|data4= 蒙民伟楼 406
|header5 = Class
|label5 =
|data5 =
|header6 =
|label6 = Class meetings
|data6 = 8 am-10 am, Wednesday
|header7 =
|label7 = Place
|data7 =
|header8 =
|label8 = Office hours
|data8 = 2pm-5pm, Saturday, MMW 406
|header9 = Textbook
|label9 =
|data9 =
|header10 =
|label10 =
|data10 = Motwani and Raghavan, ''Randomized Algorithms''. Cambridge Univ Press, 1995.

|belowstyle = background:#ddf;
|below =
}}

This is the page for the class ''Randomized Algorithms'' for the Spring 2010 semester. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =
There is no announcement yet.

= Syllabus =
随机化（randomization）是现代计算机科学最重要的方法之一，近二十年来被广泛的应用于计算机科学的各个领域。在这些应用的背后，有一些共通的随机化原理。在随机算法这门课程中，我们将用数学的语言描述这些原理，将会讲授以下内容：
* 一些重要的随机算法的设计与分析；
* 概率论工具，其中包括概率分析的工具，也包括数学证明的概率方法 (the probabilistic method);
* 随机算法的概率模型，既包括一些算法模型，例如随机漫游 (random walks)，也包括复杂度模型——概率图灵机。
作为一门理论课程，这门课的内容将更加侧重数学上的分析和证明。这么做的目的不仅仅是为了结果的严格性，而是因为设计一个聪明的算法通常都需要对问题本身的数学结构有深刻的认识。

=== 先修课程 Prerequisites ===
必须：离散数学，概率论。
推荐：算法设计与分析。

=== [[Randomized Algorithms (Spring 2010)/Course materials|教材和参考书 Course materials]] ===

=== [[Randomized Algorithms (Spring 2010)/Policies|规则 Policies]] ===

= Assignments =
There is no assignment yet.

= Lecture Notes =

Randomized Algorithms (Spring 2010)/Policies

2009-12-27T16:37:20Z

210.28.131.14:

== 作业与考试 ==
本课程将会有六次作业和一次期末考试。最终成绩将由平时作业成绩和期末考试成绩综合得出。

== 辅助材料的使用 ==
除了教材和讲义之外，学生也可以从其它学术出版物以及互联网获得有用的信息。在完成作业的过程中，允许参考各种书籍、论文、以及互联网页面来获得帮助，这种行为是被鼓励的，因为在解决实际问题的过程中，寻找有用的参考信息也是解决问题的一部分。但是，'''剽窃'''是不可容忍的。一旦发现剽窃行为，课程成绩将被取消。关于剽窃的定义，参见 [http://www.acm.org/publications/policies/plagiarism_policy ACM Policy on Plagiarism]。

== 讨论 ==
学生可以通过各种方式——例如当面讨论，email，bbs等——讨论课程内容和作业中不懂的地方。但是署着你名字的工作（你的作业）必须是由你个人完成的，这既包括文本的书写，也包括关键难点的解决。任何形式的抄袭：文本抄袭以及关键思想的抄袭，将不被允许。一旦发现抄袭行为，'''抄袭和被抄袭双方的成绩都将被取消'''。如果你在完成作业的过程中，得到任何形式的帮助（讨论、建议、反馈等等），则需在提交文本中明确的致谢（acknowledge），指出受到何人何种形式的帮助。符合规则的致谢将不会影响你作业的分数。

== 迟交 ==
如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。

Randomized Algorithms (Spring 2010)/Policies

2009-12-27T16:36:27Z

210.28.131.14:

== 作业与考试 ==
本课程将会有六次作业和一次期末考试。最终成绩将由平时作业成绩和期末考试成绩综合得出。

== 辅助材料的使用 ==
除了教材和讲义之外，学生也可以从其它学术出版物以及互联网获得有用的信息。在完成作业的过程中，允许参考各种书籍、论文、以及互联网页面来获得帮助，这种行为是被鼓励的，因为在解决实际问题的过程中，寻找有用的参考信息也是解决问题的一部分。但是，'''剽窃'''是不可容忍的。一旦发现剽窃行为，课程成绩将被取消。关于剽窃的定义，参见 [http://www.acm.org/publications/policies/plagiarism_policy ACM Policy on Plagiarism]。

== 讨论 ==
学生可以通过各种方式——例如当面讨论，email，bbs等——讨论课程内容和作业中不懂的地方。但是署着你名字的工作（你的作业）必须是由你个人完成的，这既包括文本的书写，也包括关键难点的解决。任何形式的抄袭：文本抄袭以及关键思想的抄袭，将不被允许。一旦发现抄袭行为，'''抄袭和被抄袭双方的成绩都将被取消'''。如果你在完成作业的过程中，得到任何形式的帮助（讨论、建议、反馈等等），则需在提交文本中明确的致谢（acknowledge），指出受到何人何种形式的帮助。合适的致谢将不会影响你作业的分数。

== 迟交 ==
如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。

Randomized Algorithms (Spring 2010)/Policies

2009-12-27T16:36:00Z

210.28.131.14: Created page with '== 作业与考试 == 本课程将会有六次作业和一次期末考试。最终成绩将由平时作业成绩和期末考试成绩综合得出。只参加期末考试的人将…'

== 作业与考试 ==
本课程将会有六次作业和一次期末考试。最终成绩将由平时作业成绩和期末考试成绩综合得出。只参加期末考试的人将不会及格。

== 辅助材料的使用 ==
除了教材和讲义之外，学生也可以从其它学术出版物以及互联网获得有用的信息。在完成作业的过程中，允许参考各种书籍、论文、以及互联网页面来获得帮助，这种行为是被鼓励的，因为在解决实际问题的过程中，寻找有用的参考信息也是解决问题的一部分。但是，'''剽窃'''是不可容忍的。一旦发现剽窃行为，课程成绩将被取消。关于剽窃的定义，参见 [http://www.acm.org/publications/policies/plagiarism_policy ACM Policy on Plagiarism]。

== 讨论 ==
学生可以通过各种方式——例如当面讨论，email，bbs等——讨论课程内容和作业中不懂的地方。但是署着你名字的工作（你的作业）必须是由你个人完成的，这既包括文本的书写，也包括关键难点的解决。任何形式的抄袭：文本抄袭以及关键思想的抄袭，将不被允许。一旦发现抄袭行为，'''抄袭和被抄袭双方的成绩都将被取消'''。如果你在完成作业的过程中，得到任何形式的帮助（讨论、建议、反馈等等），则需在提交文本中明确的致谢（acknowledge），指出受到何人何种形式的帮助。合适的致谢将不会影响你作业的分数。

== 迟交 ==
如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。

Randomized Algorithms (Spring 2010)

2009-12-27T15:30:20Z

210.28.131.14:

{{Infobox
|name = Infobox
|bodystyle =
|title = 随机算法
Randomized Algorithms
|titlestyle =

|image = [[File:MR-randomized-algorithms.png|100px]]
|imagestyle =
|caption = ''Randomized Algorithms'' by Motwani and Raghavan
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = 尹一通
|header3 =
|label3 = Email
|data3 = yitong.yin@gmail.com yinyt@nju.edu.cn yinyt@lamda.nju.edu.cn
|header4 =
|label4= office
|data4= 蒙民伟楼 406
|header5 = Class
|label5 =
|data5 =
|header6 =
|label6 = Class meetings
|data6 = 8 am-10 am, Wednesday
|header7 =
|label7 = Place
|data7 =
|header8 =
|label8 = Office hours
|data8 = 2pm-5pm, Saturday, MMW 406
|header9 = Textbook
|label9 =
|data9 =
|header10 =
|label10 =
|data10 = Motwani and Raghavan, ''Randomized Algorithms''. Cambridge Univ Press, 1995.

|belowstyle = background:#ddf;
|below =
}}

This is the page for the class ''Randomized Algorithms'' for the Spring 2010 semester. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =
There is no announcement yet.

= Syllabus =
随机化（randomization）是现代计算机科学最重要的方法之一，近二十年来被广泛的应用于计算机科学的各个领域。在这些重要应用的背后，有着彼此相通的随机化的原理。在随机算法这门课程中，我们将用数学的语言描述这些原理，将会讲授以下内容：
* 一些重要的随机算法的设计与分析；
* 概率论工具，其中包括概率分析的工具，也包括数学证明的概率方法 (the probabilistic method);
* 随机算法的概率模型，既包括一些算法模型，例如随机漫游 (random walks)，也包括复杂度模型——概率图灵机。
作为一门理论课程，这门课的内容将更加侧重数学上的分析和证明。这么做的目的不仅仅是为了结果的严格性，而是因为设计一个聪明的算法通常都需要对问题本身的数学结构有深刻的认识。

=== 先修课程 Prerequisites ===
必须：离散数学，概率论。
推荐：算法设计与分析。

=== [[Randomized Algorithms (Spring 2010)/Course materials|教材和参考书 Course materials]] ===

=== [[Randomized Algorithms (Spring 2010)/Policies|规则 Policies]] ===

= Assignments =
There is no assignment yet.

= Lecture Notes =