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

From TCS Wiki
Jump to navigation Jump to search
Zouzongrui (talk | contribs)
No edit summary
Zouzongrui (talk | contribs)
No edit summary
Line 5: Line 5:
*我们推荐大家使用LaTeX, markdown等对作业进行排版。
*我们推荐大家使用LaTeX, markdown等对作业进行排版。


== Problem 1 (min-cut/max-cut) ==
== Problem 1 (Min-cut/Max-cut) ==


* ['''counting <math>\alpha</math>-approximate min-cut''']
* ['''counting <math>\alpha</math>-approximate min-cut''']
* ['''weighted min-cut problem''']
* ['''max directed-cut''']


== Problem 2 (fingerprinting) ==
== 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>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''']

Revision as of 05:34, 23 October 2023

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

Problem 1 (Min-cut/Max-cut)

  • [counting [math]\displaystyle{ \alpha }[/math]-approximate min-cut]
  • [weighted min-cut problem]
  • [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]