随机算法 \ 高级算法 (Fall 2016)/Problem Set 1 and 组合数学 (Fall 2017)/Problem Set 1: Difference between pages

From TCS Wiki
(Difference between pages)
Jump to navigation Jump to search
VisualWikitext
imported>Etone
 
imported>Etone
No edit summary
 
Line 1: Line 1:
每道题目的解答都要有<font color="red" >完整的解题过程</font>。中英文不限。
*每道题目的解答都要有<font color="red" size=4>完整的解题过程</font>。中英文不限。


== Problem 1 ==
#有<math>k</math>种不同的明信片，每种明信片有无限多张，寄给<math>n</math>个人，每人一张，有多少种方法？
#有<math>k</math>种不同的明信片，每种明信片有无限多张，寄给<math>n</math>个人，每人一张，每个人必须收到不同种类的明信片，有多少种方法？
#有<math>k</math>种不同的明信片，每种明信片有无限多张，寄给<math>n</math>个人，每人收到<math>r</math>张不同的明信片（但不同的人可以收到相同的明信片），有多少种方法？
#只有一种明信片，共有<math>m</math>张，寄给<math>n</math>个人，全部寄完，每个人可以收多张明信片或者不收明信片，有多少种方法？
#有<math>k</math>种不同的明信片，其中第<math>i</math>种明信片有<math>m_i</math>张，寄给<math>n</math>个人，全部寄完，每个人可以收多张明信片或者不收明信片，有多少种方法？


== Problem 1==
== Problem 2 ==
For any <math>\alpha\ge 1</math>, a cut <math>C</math> in an undirected (multi)graph <math>G(V,E)</math>is called an <math>\alpha</math>-min-cut if <math>|C|\le\alpha|C^*|</math> where <math>C^*</math> is a min-cut in <math>G</math>.  
Find the number of ways to select <math>2n</math> balls from <math>n</math> identical blue balls, <math>n</math> identical red balls and <math>n</math> identical green balls.
* Give a combinatorial proof for the problem.
* Give an algebraic proof for the problem.


# Give a lower bound to the probability that Karger's Random Contraction algorithm returns an <math>\alpha</math>-min-cut in a graph <math>G(V,E)</math> of <math>n</math> vertices.
== Problem 3 ==
# Use the above bound to estimate the number of distinct <math>\alpha</math>-min cuts in <math>G</math>.
*一个长度为<math>n</math>的“山峦”是如下由<math>n</math>个"/"和<math>n</math>个"\"组成的，从坐标<math>(0,0)</math>到<math>(0,2n)</math>的折线，但任何时候都不允许低于<math>x</math>轴。例如下图：


== Problem 2==
    /\
Let <math>G(V,E)</math> be an undirected graph with positive edge weights <math>w:E\to\mathbb{Z}^+</math>. Given a partition of <math>V</math> into <math>k</math> disjoint subsets <math>S_1,S_2,\ldots,S_k</math>, we define
  / \/\/\    /\/\
:<math>w(S_1,S_2,\ldots,S_k)=\sum_{uv\in E\atop \exists i\neq j: u\in S_i,v\in S_j}w(uv)</math>
  /       \/\/    \/\/\
as the cost of the '''<math>k</math>-cut''' <math>\{S_1,S_2,\ldots,S_k\}</math>. Our goal is to find a <math>k</math>-cut with maximum cost.
  ----------------------
# Give a poly-time greedy algorithm for finding the weighted max <math>k</math>-cut. Prove that the approximation ratio is <math>(1-1/k)</math>.
:长度为<math>n</math>的“山峦”有多少？
# Consider the following local search algorithm for the weighted max cut (max 2-cut).
start with an arbitrary bipartition of <math>V</math> into disjoint <math>S_0,S_1</math>;
while (true) do
    if <math>\exists i\in\{0,1\}</math> and <math>v\in S_i</math> such that <font color=red>(______________)</font>
      then <math>v</math> leaves <math>S_i</math> and joins <math>S_{1-i}</math>;
      continue;
    end if
    break;
end
:Fill in the blank parenthesis. Give an analysis of the running time of the algorithm. And prove that the approximation ratio is 0.5.


== Problem 3==
*一个长度为<math>n</math>的“地貌”是由<math>n</math>个"/"和<math>n</math>个"\"组成的，从坐标<math>(0,0)</math>到<math>(0,2n)</math>的折线，允许低于<math>x</math>轴。长度为<math>n</math>的“地貌”有多少？
Given <math>m</math> subsets <math>S_1,S_2,\ldots, S_m\subseteq U</math> of a universe <math>U</math> of size <math>n</math>, we want to find a <math>C\subseteq\{1,2,\ldots, n\}</math> of fixed size <math>k=|C|</math> with the maximum '''coverage''' <math>\left|\bigcup_{i\in C}S_i\right|</math>.
 
* Give a poly-time greedy algorithm for the problem. Prove that the approximation ratio is <math>1-(1-1/k)^k>1-1/e</math>.


== Problem 4==
== Problem 4==
We consider minimum makespan scheduling on parallel identical machines when jobs are subject to '''precedence constraints'''.
李雷和韩梅梅竞选学生会主席，韩梅梅获得选票 <math>p</math> 张，李雷获得选票 <math>q</math> 张，<math>p>q</math>。我们将总共的 <math>p+q</math> 张选票一张一张的点数，有多少种选票的排序方式使得在整个点票过程中，韩梅梅的票数一直高于李雷的票数？等价地，假设选票均匀分布的随机排列，以多大概率在整个点票过程中，韩梅梅的票数一直高于李雷的票数。
 
We still want to schedule <math>n</math> jobs <math>j=1,2,\ldots, n</math> on <math>m</math> identical machines, where job <math>j</math> has  processing time <math>p_j</math>. But now a partial order <math>\preceq</math> is defined on jobs, so that if <math>j\prec k</math> then job <math>j</math> must be completely finished before job <math>k</math> begins. The following is a variant of the ''List'' algorithm for this problem: we still assume that the input is a list of <math>n</math> jobs with processing times <math>p_1,p_2,\ldots, p_n</math>.
 
whenever a machine becomes idle
    assign the next ''available'' job on the list to the machine;


Here a job <math>k</math> is available if all jobs <math>j\prec k</math> have already been completely processed.
==Problem 5==
A <math>2\times n</math> rectangle is to be paved with <math>1\times 2</math> identical blocks and <math>2\times 2</math> identical blocks. Let <math>f(n)</math> denote the number of ways that can be done. Find a recurrence relation for <math>f(n)</math>, solve the recurrence relation.


* Prove that the approximation ratio is 2.
== Problem 6 ==
* 令<math>s_n</math>表示长度为<math>n</math>，没有2个连续的1的二进制串的数量，即
*:<math>s_n=|\{x\in\{0,1\}^n\mid \forall 1\le i\le n-1, x_ix_{i+1}\neq 11\}|</math>。
:求 <math>s_n</math>。


== Problem 5 ==
*令<math>t_n</math>表示长度为<math>n</math>，没有3个连续的1的二进制串的数量，即
For a '''hypergraph''' <math>H(V,E)</math> with vertex set <math>V</math>, every '''hyperedge''' <math>e\in E</math> is a subset <math>e\subset V</math> of vertices, not necessarily of size 2. A hypergraph <math>H(V,E)</math> is '''<math>k</math>-uniform''' if every hyperedge <math>e\in V</math> is of size <math>k=|e|</math>.
*:<math>t_n=|\{x\in\{0,1\}^n\mid \forall 1\le i\le n-2, x_ix_{i+1}x_{i+2}\neq 111\}|</math>。
*#给出计算<math>t_n</math>的递归式，并给出足够的初始值。
*#计算<math>t_n</math>的生成函数<math>T(x)=\sum_{n\ge 0}t_n x^n</math>，给出生成函数<math>T(x)</math>的闭合形式。


A hypergraph <math>H(V,E)</math> is said to have '''property B''' (named after Bernstein) if <math>H</math> is 2-coloable; that is, if there is a '''proper 2-coloring''' <math>f:V\to\{{\color{red}R},{\color{blue}B}\}</math> which assigns each vertex one of the two colors <font color=red>Red</font> or <font color=blue>Blue</font>, such that none of the hyperedge is ''monochromatic''.
注意：只需解生成函数的闭合形式，无需展开。


# Let <math>H(V,E)</math> be a <math>k</math>-uniform hypergraph in which every hyperedge <math>e\in E</math> shares vertices with at most <math>d</math> other hyperedges.
== Problem 7 ==
#*Show that if <math>2\mathrm{e}\cdot (d+1)\le 2^{k}</math>, then <math>H</math> has property B.
Let <math>a_n</math> be a sequence of numbers satisfying the recurrence relation:
#*Describe how to use Moser's recursive Fix algorithm to find a proper 2-coloring of <math>H</math>. Give the pseudocode. Prove the condition in interns of <math>d</math> and <math>k</math> under which the algorithm can find a 2-coloring of <math>H</math> with high probability.
:<math>p a_n+q a_{n-1}+r a_{n-2}=0</math>
#*Describe how to use Moser-Tardos random solver to find a proper 2-coloring of <math>H</math>. Give the pseudocode. Prove the condition in interns of <math>d</math> and <math>k</math> under which the algorithm can find a 2-coloring of <math>H</math> within bounded expected time. Give an upper bound on the expected running time.
with initial condition <math>a_0=s</math> and <math>a_1=t</math>, where <math>p,q,r,s,t</math> are constants such that <math>{p}+q+r=0</math>, <math>p\neq 0</math> and <math>s\neq t</math>. Solve the recurrence relation.
# Let <math>H(V,E)</math> be a hypergraph (not necessarily uniform) with at least <math>n\ge 2</math> vertices satisfying that
#:<math>\forall v\in V, \sum_{e\ni v}(1-1/n)^{-|e|}2^{-|e|+1}\le \frac{1}{n}</math>.
#*Show that <math>H</math> has property B.
#*Describe how to use Moser-Tardos random solver to find a proper 2-coloring of <math>H</math>. Give an upper bound on the expected running time.

Revision as of 13:14, 17 September 2017

  • 每道题目的解答都要有完整的解题过程。中英文不限。

Problem 1

  1. 有[math]\displaystyle{ k }[/math]种不同的明信片，每种明信片有无限多张，寄给[math]\displaystyle{ n }[/math]个人，每人一张，有多少种方法？
  2. 有[math]\displaystyle{ k }[/math]种不同的明信片，每种明信片有无限多张，寄给[math]\displaystyle{ n }[/math]个人，每人一张，每个人必须收到不同种类的明信片，有多少种方法？
  3. 有[math]\displaystyle{ k }[/math]种不同的明信片，每种明信片有无限多张，寄给[math]\displaystyle{ n }[/math]个人，每人收到[math]\displaystyle{ r }[/math]张不同的明信片（但不同的人可以收到相同的明信片），有多少种方法？
  4. 只有一种明信片，共有[math]\displaystyle{ m }[/math]张，寄给[math]\displaystyle{ n }[/math]个人，全部寄完，每个人可以收多张明信片或者不收明信片，有多少种方法？
  5. 有[math]\displaystyle{ k }[/math]种不同的明信片，其中第[math]\displaystyle{ i }[/math]种明信片有[math]\displaystyle{ m_i }[/math]张，寄给[math]\displaystyle{ n }[/math]个人，全部寄完，每个人可以收多张明信片或者不收明信片，有多少种方法？

Problem 2

Find the number of ways to select [math]\displaystyle{ 2n }[/math] balls from [math]\displaystyle{ n }[/math] identical blue balls, [math]\displaystyle{ n }[/math] identical red balls and [math]\displaystyle{ n }[/math] identical green balls.

  • Give a combinatorial proof for the problem.
  • Give an algebraic proof for the problem.

Problem 3

  • 一个长度为[math]\displaystyle{ n }[/math]的“山峦”是如下由[math]\displaystyle{ n }[/math]个"/"和[math]\displaystyle{ n }[/math]个"\"组成的，从坐标[math]\displaystyle{ (0,0) }[/math]到[math]\displaystyle{ (0,2n) }[/math]的折线，但任何时候都不允许低于[math]\displaystyle{ x }[/math]轴。例如下图：
   /\
  /  \/\/\    /\/\
 /        \/\/    \/\/\
 ----------------------
长度为[math]\displaystyle{ n }[/math]的“山峦”有多少？
  • 一个长度为[math]\displaystyle{ n }[/math]的“地貌”是由[math]\displaystyle{ n }[/math]个"/"和[math]\displaystyle{ n }[/math]个"\"组成的，从坐标[math]\displaystyle{ (0,0) }[/math]到[math]\displaystyle{ (0,2n) }[/math]的折线，允许低于[math]\displaystyle{ x }[/math]轴。长度为[math]\displaystyle{ n }[/math]的“地貌”有多少？

Problem 4

李雷和韩梅梅竞选学生会主席，韩梅梅获得选票 [math]\displaystyle{ p }[/math] 张，李雷获得选票 [math]\displaystyle{ q }[/math] 张，[math]\displaystyle{ p\gt q }[/math]。我们将总共的 [math]\displaystyle{ p+q }[/math] 张选票一张一张的点数，有多少种选票的排序方式使得在整个点票过程中，韩梅梅的票数一直高于李雷的票数？等价地，假设选票均匀分布的随机排列，以多大概率在整个点票过程中，韩梅梅的票数一直高于李雷的票数。

Problem 5

A [math]\displaystyle{ 2\times n }[/math] rectangle is to be paved with [math]\displaystyle{ 1\times 2 }[/math] identical blocks and [math]\displaystyle{ 2\times 2 }[/math] identical blocks. Let [math]\displaystyle{ f(n) }[/math] denote the number of ways that can be done. Find a recurrence relation for [math]\displaystyle{ f(n) }[/math], solve the recurrence relation.

Problem 6

  • 令[math]\displaystyle{ s_n }[/math]表示长度为[math]\displaystyle{ n }[/math]，没有2个连续的1的二进制串的数量，即
    [math]\displaystyle{ s_n=|\{x\in\{0,1\}^n\mid \forall 1\le i\le n-1, x_ix_{i+1}\neq 11\}| }[/math]。
求 [math]\displaystyle{ s_n }[/math]。
  • 令[math]\displaystyle{ t_n }[/math]表示长度为[math]\displaystyle{ n }[/math]，没有3个连续的1的二进制串的数量，即
    [math]\displaystyle{ t_n=|\{x\in\{0,1\}^n\mid \forall 1\le i\le n-2, x_ix_{i+1}x_{i+2}\neq 111\}| }[/math]。
    1. 给出计算[math]\displaystyle{ t_n }[/math]的递归式，并给出足够的初始值。
    2. 计算[math]\displaystyle{ t_n }[/math]的生成函数[math]\displaystyle{ T(x)=\sum_{n\ge 0}t_n x^n }[/math]，给出生成函数[math]\displaystyle{ T(x) }[/math]的闭合形式。

注意：只需解生成函数的闭合形式，无需展开。

Problem 7

Let [math]\displaystyle{ a_n }[/math] be a sequence of numbers satisfying the recurrence relation:

[math]\displaystyle{ p a_n+q a_{n-1}+r a_{n-2}=0 }[/math]

with initial condition [math]\displaystyle{ a_0=s }[/math] and [math]\displaystyle{ a_1=t }[/math], where [math]\displaystyle{ p,q,r,s,t }[/math] are constants such that [math]\displaystyle{ {p}+q+r=0 }[/math], [math]\displaystyle{ p\neq 0 }[/math] and [math]\displaystyle{ s\neq t }[/math]. Solve the recurrence relation.

Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=随机算法_%5C_高级算法_(Fall_2016)/Problem_Set_1&oldid=7927"