User contributions for Etone

Results for Etone talk block log uploads logs
A user with 1,150 edits. Account created on 30 August 2022.
Jump to navigation Jump to search
(newest | oldest) View ( | ) (20 | 50 | 100 | 250 | 500)

29 September 2024

27 September 2024

22 September 2024

19 September 2024

  • 11:3211:32, 19 September 2024 diff hist +10,715 N 高级算法 (Fall 2024)/Conditional expectations Created page with "= Conditional Expectations = The '''conditional expectation''' of a random variable <math>Y</math> with respect to an event <math>\mathcal{E}</math> is defined by :<math> \mathbf{E}[Y\mid \mathcal{E}]=\sum_{y}y\Pr[Y=y\mid\mathcal{E}]. </math> In particular, if the event <math>\mathcal{E}</math> is <math>X=a</math>, the conditional expectation :<math> \mathbf{E}[Y\mid X=a] </math> defines a function :<math> f(a)=\mathbf{E}[Y\mid X=a]. </math> Thus, <math>\mathbf{E}[Y\mid..." current
  • 11:3111:31, 19 September 2024 diff hist +41,013 N 高级算法 (Fall 2024)/Concentration of measure Created page with "=Chernoff Bound= Suppose that we have a fair coin. If we toss it once, then the outcome is completely unpredictable. But if we toss it, say for 1000 times, then the number of HEADs is very likely to be around 500. This phenomenon, as illustrated in the following figure, is called the '''concentration''' of measure. The Chernoff bound is an inequality that characterizes the concentration phenomenon for the sum of independent trials. File:Coinflip.png|border|450px|cent..." current
  • 11:3011:30, 19 September 2024 diff hist +229 高级算法 (Fall 2024) →Lecture Notes

18 September 2024

16 September 2024

  • 02:4502:45, 16 September 2024 diff hist +5,755 N 高级算法 (Fall 2024)/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
  • 02:4402:44, 16 September 2024 diff hist +15,812 N 高级算法 (Fall 2024)/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
  • 02:4402:44, 16 September 2024 diff hist +49,238 N 高级算法 (Fall 2024)/Hashing and Sketching Created page with "=Balls into Bins= The following is the so-called balls into bins model. 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..."
  • 02:4402:44, 16 September 2024 diff hist +304 高级算法 (Fall 2024) →Lecture Notes

12 September 2024

6 September 2024

5 September 2024

29 August 2024

28 August 2024

  • 12:1812:18, 28 August 2024 diff hist +109 Main Page No edit summary
  • 05:2405:24, 28 August 2024 diff hist +17,328 N 高级算法 (Fall 2024)/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
  • 05:2405:24, 28 August 2024 diff hist +50,059 N 高级算法 (Fall 2024)/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..."
  • 05:2305:23, 28 August 2024 diff hist +2,043 N 高级算法 (Fall 2024) / 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..." current
  • 05:2205:22, 28 August 2024 diff hist +6,278 N 高级算法 (Fall 2024) Created page with "{{Infobox |name = Infobox |bodystyle = |title = <font size=3>高级算法 <br>Advanced Algorithms</font> |titlestyle = |image = |imagestyle = |caption = |captionstyle = |headerstyle = background:#ccf; |labelstyle = background:#ddf; |datastyle = |header1 =Instructor |label1 = |data1 = |header2 = |label2 = |data2 = '''尹一通''' |header3 = |label3 = Email |data3 = yinyt@nju.edu.cn |header4 = |label4= office..."
  • 05:1405:14, 28 August 2024 diff hist +75 Main Page →Home Pages for Courses and Seminars

10 July 2024

13 June 2024

5 June 2024

  • 03:0203:02, 5 June 2024 diff hist +34,076 N 组合数学 (Fall 2024)/Matching theory Created page with "== Systems of Distinct Representatives (SDR)== A '''system of distinct representatives (SDR)''' (also called a '''transversal''') for a sequence of (not necessarily distinct) sets <math>S_1,S_2,\ldots,S_m</math> is a sequence of <font color=red>''distinct''</font> elements <math>x_1,x_2,\ldots,x_m</math> such that <math>x_i\in S_i</math> for all <math>i=1,2,\ldots,m</math>. === Hall's marriage theorem === If the sets <math>S_1,S_2,\ldots,S_m</math> have a system of dist..." current
  • 03:0203:02, 5 June 2024 diff hist +75 组合数学 (Spring 2024) →Lecture Notes

29 May 2024

(newest | oldest) View ( | ) (20 | 50 | 100 | 250 | 500)
Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=Special:Contributions/Etone"