User contributions for Etone

16:3916:39, 26 September 2023 diff hist +5,755 N 高级算法 (Fall 2023)/Basic deviation inequalities Created page with "=Markov's Inequality= One of the most natural information about a random variable is its expectation, which is the first moment of the random variable. Markov's inequality draws a tail bound for a random variable from its expectation. {{Theorem |Theorem (Markov's Inequality)| :Let <math>X</math> be a random variable assuming only nonnegative values. Then, for all <math>t>0</math>, ::<math>\begin{align} \Pr[X\ge t]\le \frac{\mathbf{E}[X]}{t}. \end{align}</math> }} {{Proo..." current
16:3916:39, 26 September 2023 diff hist +10 高级算法 (Fall 2023) →Lecture Notes
16:3816:38, 26 September 2023 diff hist +15,812 N 高级算法 (Fall 2023)/Limited independence Created page with "= <math>k</math>-wise independence = Recall the definition of independence between events: {{Theorem |Definition (Independent events)| :Events <math>\mathcal{E}_1, \mathcal{E}_2, \ldots, \mathcal{E}_n</math> are '''mutually independent''' if, for any subset <math>I\subseteq\{1,2,\ldots,n\}</math>, ::<math>\begin{align} \Pr\left[\bigwedge_{i\in I}\mathcal{E}_i\right] &= \prod_{i\in I}\Pr[\mathcal{E}_i]. \end{align}</math> }} Similarly, we can define independence between..." current
16:3716:37, 26 September 2023 diff hist +294 高级算法 (Fall 2023) →Lecture Notes

12:2112:21, 19 September 2023 diff hist +56 高级算法 (Fall 2023)/Fingerprinting →Schwartz-Zippel Theorem current
12:2012:20, 19 September 2023 diff hist −18 高级算法 (Fall 2023)/Fingerprinting →Communication protocols for Equality by fingerprinting
12:1912:19, 19 September 2023 diff hist −11 高级算法 (Fall 2023)/Fingerprinting →Randomized pattern matching
12:1912:19, 19 September 2023 diff hist −26 高级算法 (Fall 2023)/Fingerprinting →Checking distinctness
12:1912:19, 19 September 2023 diff hist −3 高级算法 (Fall 2023)/Fingerprinting →Checking distinctness
11:0511:05, 19 September 2023 diff hist +2,354 高级算法 (Fall 2023)/Fingerprinting →Fingerprinting
11:0211:02, 19 September 2023 diff hist +5,391 高级算法 (Fall 2023)/Fingerprinting No edit summary
10:5810:58, 19 September 2023 diff hist +6,210 N 高级算法 (Fall 2023)/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
10:5710:57, 19 September 2023 diff hist +30,540 N 高级算法 (Fall 2023)/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..."
10:5710:57, 19 September 2023 diff hist +203 高级算法 (Fall 2023) →Lecture Notes

08:5308:53, 14 September 2023 diff hist −2 高级算法 (Fall 2023)/Min Cut, Max Cut, and Spectral Cut →Spectrum of Regular Graphs current
08:5208:52, 14 September 2023 diff hist +1 高级算法 (Fall 2023)/Min Cut, Max Cut, and Spectral Cut →Spectrum of Regular Graphs
08:5208:52, 14 September 2023 diff hist +1 高级算法 (Fall 2023)/Min Cut, Max Cut, and Spectral Cut →Spectrum of Regular Graphs
01:3001:30, 14 September 2023 diff hist −33 General Circulation(Fall 2023) →Course info
01:2901:29, 14 September 2023 diff hist 0 General Circulation(Fall 2023) →Course info
01:2901:29, 14 September 2023 diff hist +1 General Circulation(Fall 2023) →Course info
01:2901:29, 14 September 2023 diff hist −95 General Circulation(Fall 2023) →Announcement
01:2501:25, 14 September 2023 diff hist +8,324 N General Circulation(Fall 2023) Created page with "{{Infobox |name = Infobox |bodystyle = |title = 大气环流 <br> General Circulation of the Atmosphere |titlestyle = |headerstyle = background:#ccf; |labelstyle = background:#ddf; |datastyle = |header1 =Instructor |label1 = |data1 = |header2 = |label2 = |data2 = 张洋 |header3 = |label3 = Email |data3 = yangzhang@nju.edu.cn |header4 = |label4= office |data4= 仙林大气楼 B410 |header5 = Class |label5 = |data5 = |hea..."
01:1901:19, 14 September 2023 diff hist 0 Main Page →Home Pages for Courses and Seminars
01:1801:18, 14 September 2023 diff hist −34 General Circulation(Fall 2022) →Assignments current

10:3610:36, 12 September 2023 diff hist +44,308 N 高级算法 (Fall 2023)/Min Cut, Max Cut, and Spectral 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..."
10:3510:35, 12 September 2023 diff hist 0 高级算法 (Fall 2023) →Lecture Notes
10:3410:34, 12 September 2023 diff hist +17,328 N 高级算法 (Fall 2023)/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
10:3410:34, 12 September 2023 diff hist +23 高级算法 (Fall 2023)/Min Cut, Min Cut, and Spectral Cut No edit summary current
10:3310:33, 12 September 2023 diff hist +44,285 N 高级算法 (Fall 2023)/Min Cut, Min Cut, and Spectral 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..."
10:3310:33, 12 September 2023 diff hist +30 高级算法 (Fall 2023) →Lecture Notes
10:3210:32, 12 September 2023 diff hist +193 高级算法 (Fall 2023) →Lecture Notes

13:3913:39, 10 September 2023 diff hist 0 高级算法 (Fall 2023) / Course materials →References and further readings
11:4411:44, 10 September 2023 diff hist +1,429 N 高级算法 (Fall 2023) / Course materials Created page with "= Course textbooks = {|border="2" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;" |border|100px |width="100%"| :Rajeev Motwani and Prabhakar Raghavan. :'''''Randomized Algorithms'''''. :Cambridge University Press, 1995. |- |border|100px|| : Vijay Vazirani. :'''''Approximation Algorithms'''''. :S..."
11:4311:43, 10 September 2023 diff hist 0 高级算法 (Fall 2023) →Course materials