Main 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).

• 14:53, 16 March 2025 Gispzjz talk contribs created page 组合数学 (Spring 2025)/Problem Set 1 (Created page with "== Problem 1 == Fix positive integers <math>n</math> and <math>k</math>. Let <math>S</math> be a set with <math>|S|=n</math>. Find the numbers of <math>k</math>-tuples <math>(T_1,T_2,\dots,T_k)</math> of subsets <math>T_i</math> of <math>S</math> subject to each of the following conditions separately. Briefly explain your answer. * <math>T_1\subseteq T_2\subseteq \cdots \subseteq T_k.</math> * The <math> T_i</math>s are pairwise disjoint. * <math> T_1\cup T_2\cup \cdots...")
• 09:28, 18 February 2025 Gispzjz talk contribs created page 组合数学 (Spring 2025)/Course materials (Created page with "== 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%"| :J. H. van Lint and R. M. Wilson. ''A course in Combinatorics, 2nd Edition.'' Cambridge University Press, 2001. |- |border|100px|| :S. Jukna. ''Extremal Combinatorics: With Applications in Computer Science, 2nd Edition...")
• 09:23, 18 February 2025 Gispzjz talk contribs created page 组合数学 (Spring 2025)/Basic enumeration (Created page with "== Basic Enumeration == The three basic rules for enumeration are: *'''The sum rule''': for any '''''disjoint''''' finite sets <math>S</math> and <math>T</math>, the cardinality of the union <math>|S\cup T|=|S|+|T|</math>. *'''The product rule''': for any finite sets <math>S</math> and <math>T</math>, the cardinality of the Cartesian product <math>|S\times T|=|S|\cdot|T|</math>. *'''The bijection rule''': if there exists a bijection between finite sets <math>S</math> a...")
• 09:21, 18 February 2025 Gispzjz talk contribs created page 组合数学 (Fall 2025)/Basic enumeration (Created page with "== Basic Enumeration == The three basic rules for enumeration are: *'''The sum rule''': for any '''''disjoint''''' finite sets <math>S</math> and <math>T</math>, the cardinality of the union <math>|S\cup T|=|S|+|T|</math>. *'''The product rule''': for any finite sets <math>S</math> and <math>T</math>, the cardinality of the Cartesian product <math>|S\times T|=|S|\cdot|T|</math>. *'''The bijection rule''': if there exists a bijection between finite sets <math>S</math> a...")
• 09:18, 18 February 2025 Gispzjz talk contribs created page 组合数学 (Spring 2025) (Created page with " This is the webpage for the ''Combinatorics'' class of Spring 2024. Students who take this class should check this page periodically for content updates and new announcements. = Announcement = = Course info = * '''Instructor ''': 尹一通 ([http://tcs.nju.edu.cn/yinyt/ homepage]) :* '''email''': yinyt@nju.edu.cn :* '''office''': 计算机系 804 * '''Teaching assistant''': ** [https://lhy-gispzjz.github.io/ 刘弘洋] ([mailto:liuhongyang@smail.nju.edu.cn liuhongy...") Tag: Visual edit
• 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