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

From TCS Wiki
Jump to navigation Jump to search
Kvrmnks (talk | contribs)
Kvrmnks (talk | contribs)
Line 4: Line 4:


== Problem 1 (Min-cut/Max-cut) ==
== Problem 1 (Min-cut/Max-cut) ==
['''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?)
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?)


== Problem 2 (Fingerprinting) ==
== Problem 2 (Fingerprinting) ==

Revision as of 03:01, 28 September 2024

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

Problem 1 (Min-cut/Max-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?)

Problem 2 (Fingerprinting)

Design a randomized algorithm to decide if an integer sequence [math]\displaystyle{ a_1,...,a_n }[/math] is a permutation of another integer sequence [math]\displaystyle{ b_1,...,b_n }[/math]. Give upper bounds on the time complexity and the error probability.

Problem 3 (Hashing)

Problem 4 (Concentration of measure)

Problem 5 (Dimension reduction)