All public logs

Combined display of all available logs of TCS Wiki. You can narrow down the view by selecting a log type, the username (case-sensitive), or the affected page (also case-sensitive).

• 15:55, 14 May 2024 Gispzjz talk contribs created page 组合数学 (Spring 2024)/Problem Set 3 (Created page with "== Problem 1 == Solve the following two existence problems: * You are given <math>n</math> integers <math>a_1,a_2,\dots,a_n</math>, such that for each <math> 1\leq i\leq n</math> it holds that <math>i-n\leq a_i\leq i-1</math>. Show that there exists a '''nonempty''' subsequence (not necessarily consecutive) of these integers, whose sum is equal to <math> 0 </math>. (Hint: Consider <math> b_i=a_i-i </math>) * You are given two '''multisets''' <math> A </math> and <ma...")
• 12:42, 19 March 2024 Gispzjz talk contribs created page 组合数学 (Fall 2024)/Problem Set 1 (Created page with "== Problem 1 == How many <math>n\times m</math> matrices of <math>0</math>'s and <math>1</math>'s are there, such that every row and column contains an even number of <math>1</math>'s? An odd number of <math>1</math>'s? == Problem 2 == * There is a set of <math>2n</math> people: <math>n</math> male and <math>n</math> female. A good party is a set with the same number of male and female. How many possibilities are there to build such a good party? * Try to express the a...")
• 14:15, 8 June 2023 Gispzjz talk contribs created page 组合数学 (Fall 2023)/Problem Set 4 (Created page with "== Problem 1 == Prove that * <math>R(4,3)\leq 9</math>. (Hint: Proof by contradiction. Color the edges of <math>K_9</math> in red and blue, and assume that there are no red triangles and no blue <math>4</math>-cliques. Try to determine the number of red and blue edges adjacent to each vertex) * <math>R(4,4)\leq 18</math>. ==Problem 2== We color each non-empty subset of <math>[n]=\{1,2,\ldots,n\}</math> with one of the <math>r</math> colors in <math>[r]</math>. Show tha...")
• 12:46, 13 April 2023 Gispzjz talk contribs created page 组合数学 (Fall 2023)/Problem Set 2 (Created page with "Let <math>S=\{P_1,...,P_n\}</math> be a set of properties, and let <math>f_k</math> (respectively, <math>f_{\geq k}</math>) denote the number of objects in a finite set <math>U</math> that have '''exactly''' <math>k</math> (respectively, '''at least''' <math>k</math>) of the properties. Let <math>A_i</math> denote the set of objects satisfies <math>P_i</math> in <math>U</math>, for any <math>I\subseteq\{1,...,n\}</math>, we denote <math>A_I=\bigcap_{i\in I}A_i</math> wi...")
• 07:29, 12 December 2022 Gispzjz talk contribs created page 高级算法 (Fall 2022)/Problem Set 4 (Created page with "== Problem 1 == Suppose there is a coin <math> C </math>. During each query, it outputs HEAD with probability <math>p</math> and TAIL with probability <math>1-p</math>, where <math> p \in (0, 1) </math> is a real number. * Let <math> q \in (0, 1) </math> be another real number. Design an algorithm that outputs HEAD with probability <math>q</math> and TAIL with probability <math>1-q</math>. There is no other random sources for your algorithm except the coin <math>C</math...")
• 08:39, 9 October 2022 Gispzjz talk contribs created page 高级算法 (Fall 2022)/Problem Set 1 (Created page with "== Problem 1 == Modify the Karger's Contraction algorithm so that it works for the ''weighted min-cut problem''. Prove that the modified algorithm returns a weighted minimum cut with probability at least <math>\frac{2}{n(n-1)}</math>. The weighted min-cut problem is defined as follows. *'''Input''': an undirected weighted graph <math>G(V, E)</math>, where every edge <math>e \in E</math> is associated with a positive real weight <math>w_e</math>; *'''Output''': a cut <ma...")
• 13:57, 5 September 2022 Gispzjz talk contribs created page File:DPV.jpg
• 13:57, 5 September 2022 Gispzjz talk contribs uploaded File:DPV.jpg