User contributions for Etone

11:4711:47, 21 September 2022 diff hist +11,376 N 高级算法 (Fall 2022)/Balls into bins Created page with "=Balls into Bins= Consider throwing <math>m</math> balls into <math>n</math> bins uniformly and independently at random. This is equivalent to a random mapping <math>f:[m]\to[n]</math>. Needless to say, random mapping is an important random model and may have many applications in Computer Science, e.g. hashing. We are concerned with the following three questions regarding the balls into bins model: * birthday problem: the probability that every bin contains at most one..."
11:4711:47, 21 September 2022 diff hist +61 高级算法 (Fall 2022) →Lecture Notes
11:4611:46, 21 September 2022 diff hist 0 高级算法 (Fall 2022) →Lecture Notes
11:4611:46, 21 September 2022 diff hist −122 高级算法 (Fall 2022) →Lecture Notes
11:4611:46, 21 September 2022 diff hist +371 高级算法 (Fall 2022) →Lecture Notes

08:0708:07, 13 September 2022 diff hist −71 高级算法 (Fall 2022) →Lecture Notes
05:4305:43, 13 September 2022 diff hist +6,210 N 高级算法 (Fall 2022)/Finite Field Basics Created page with "=Field= Let <math>S</math> be a set, '''closed''' under binary operations <math>+</math> (addition) and <math>\cdot</math> (multiplication). It gives us the following algebraic structures if the corresponding set of axioms are satisfied. {|class="wikitable" !colspan="7"|Structures !Axioms !Operations |- |rowspan="9" style="background-color:#ffffcc;text-align:center;"|'''''field''''' |rowspan="8" style="background-color:#ffffcc;text-align:center;"|'''''commutative<br>rin..." current
05:4305:43, 13 September 2022 diff hist +30,540 N 高级算法 (Fall 2022)/Fingerprinting Created page with "=Polynomial Identity Testing (PIT) = The '''Polynomial Identity Testing (PIT)''' is such a problem: given as input two polynomials, determine whether they are identical. It plays a fundamental role in ''Identity Testing'' problems. First, let's consider the univariate ("one variable") case: * '''Input:''' two polynomials <math>f, g\in\mathbb{F}[x]</math> of degree <math>d</math>. * Determine whether <math>f\equiv g</math> (<math>f</math> and <math>g</math> are identica..." current
05:4205:42, 13 September 2022 diff hist +73 高级算法 (Fall 2022) →Lecture Notes
05:4205:42, 13 September 2022 diff hist +134 高级算法 (Fall 2022) →Lecture Notes

07:3107:31, 5 September 2022 diff hist +17,328 N 高级算法 (Fall 2022)/Probability Basics Created page with "=Probability Space= The axiom foundation of probability theory is laid by [http://en.wikipedia.org/wiki/Andrey_Kolmogorov Kolmogorov], one of the greatest mathematician of the 20th century, who advanced various very different fields of mathematics. {{Theorem|Definition (Probability Space)| A '''probability space''' is a triple <math>(\Omega,\Sigma,\Pr)</math>. *<math>\Omega</math> is a set, called the '''sample space'''. *<math>\Sigma\subseteq 2^{\Omega}</math> is the..." current
07:3107:31, 5 September 2022 diff hist +71 高级算法 (Fall 2022) →Lecture Notes
07:3107:31, 5 September 2022 diff hist +44,285 N 高级算法 (Fall 2022)/Min-Cut and Max-Cut Created page with "= Graph Cut = Let <math>G(V, E)</math> be an undirected graph. A subset <math>C\subseteq E</math> of edges is a '''cut''' of graph <math>G</math> if <math>G</math> becomes ''disconnected'' after deleting all edges in <math>C</math>. Let <math>\{S,T\}</math> be a '''bipartition''' of <math>V</math> into nonempty subsets <math>S,T\subseteq V</math>, where <math>S\cap T=\emptyset</math> and <math>S\cup T=V</math>. A cut <math>C</math> is specified by this bipartition as..." current
07:3007:30, 5 September 2022 diff hist +126 高级算法 (Fall 2022) →Lecture Notes

Navigation menu