高级算法 (Fall 2023)/Problem Set 1: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
Zouzongrui (talk | contribs)
Zouzongrui (talk | contribs)
Line 9: Line 9:
* ['''counting <math>\alpha</math>-approximate min-cut'''] For any '''<math>\alpha \ge 1</math>''', a cut is called an '''<math>\alpha</math>'''-approximate min-cut in a multigraph '''<math>G</math>''' if the number of edges in it is at most '''<math>\alpha</math>''' times that of the min-cut.  Prove that the number of '''<math>\alpha</math>'''-approximate min-cuts in a multigraph '''<math>G</math>''' is at most '''<math>n^{2\alpha} / 2</math>'''.  Hint: Run Karger's algorithm until it has '''<math>\lceil 2\alpha \rceil</math>''' supernodes. What is the chance that a particular '''<math>\alpha</math>'''-approximate min-cut is still available? How many possible cuts does this collapsed graph have?
* ['''counting <math>\alpha</math>-approximate min-cut'''] For any '''<math>\alpha \ge 1</math>''', a cut is called an '''<math>\alpha</math>'''-approximate min-cut in a multigraph '''<math>G</math>''' if the number of edges in it is at most '''<math>\alpha</math>''' times that of the min-cut.  Prove that the number of '''<math>\alpha</math>'''-approximate min-cuts in a multigraph '''<math>G</math>''' is at most '''<math>n^{2\alpha} / 2</math>'''.  Hint: Run Karger's algorithm until it has '''<math>\lceil 2\alpha \rceil</math>''' supernodes. What is the chance that a particular '''<math>\alpha</math>'''-approximate min-cut is still available? How many possible cuts does this collapsed graph have?
* ['''weighted min-cut problem'''] 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>{2}/{n(n-1)}</math>. The weighted min-cut problem is defined as follows.
* ['''weighted min-cut problem'''] 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>{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>
'''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 <math>C</math> in <math>G</math> such that <math>\sum_{e \in C} w_e</math> is minimized.
 
'''Output''': a cut <math>C</math> in <math>G</math> such that <math>\sum_{e \in C} w_e</math> is minimized.


* ['''max directed-cut''']
* ['''max directed-cut''']

Revision as of 05:47, 23 October 2023

  • 作业目前正在更新中,不是最终版
  • 每道题目的解答都要有完整的解题过程,中英文不限。
  • 我们推荐大家使用LaTeX, markdown等对作业进行排版。

Problem 1 (Min-cut/Max-cut)

  • [counting [math]\displaystyle{ \alpha }[/math]-approximate min-cut] For any [math]\displaystyle{ \alpha \ge 1 }[/math], a cut is called an [math]\displaystyle{ \alpha }[/math]-approximate min-cut in a multigraph [math]\displaystyle{ G }[/math] if the number of edges in it is at most [math]\displaystyle{ \alpha }[/math] times that of the min-cut. Prove that the number of [math]\displaystyle{ \alpha }[/math]-approximate min-cuts in a multigraph [math]\displaystyle{ G }[/math] is at most [math]\displaystyle{ n^{2\alpha} / 2 }[/math]. Hint: Run Karger's algorithm until it has [math]\displaystyle{ \lceil 2\alpha \rceil }[/math] supernodes. What is the chance that a particular [math]\displaystyle{ \alpha }[/math]-approximate min-cut is still available? How many possible cuts does this collapsed graph have?
  • [weighted min-cut problem] 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]\displaystyle{ {2}/{n(n-1)} }[/math]. The weighted min-cut problem is defined as follows.
    • Input: an undirected weighted graph [math]\displaystyle{ G(V, E) }[/math], where every edge [math]\displaystyle{ e \in E }[/math] is associated with a positive real weight [math]\displaystyle{ w_e }[/math]
    • Output: a cut [math]\displaystyle{ C }[/math] in [math]\displaystyle{ G }[/math] such that [math]\displaystyle{ \sum_{e \in C} w_e }[/math] is minimized.
  • [max directed-cut]

Problem 2 (Fingerprinting)

  • [Polynomial Identity Testing]
  • [Test isomorphism of rooted tree]
  • [2D pattern matching]

Problem 3 (Hashing)

  • [Bloom filter]
  • [Count Distinct Element]

Problem 4 (Concentration of measure)

  • [[math]\displaystyle{ k }[/math]-th moment bound]
  • [the median trick]
  • [cut size in random graph]
  • [code rate of boolean code]
  • [balls into bins with the "power of two choices"]

Problem 5 (Dimension reduction)

  • [inner product]
  • [linear separability]
  • [sparse vector]

Problem 1 (Lovász Local Lemma)

  • [colorable hypergrap]
  • [directed cycle]
  • [algorithmic LLL]