随机算法 (Spring 2013)/Problem Set 4 and 高级算法 (Fall 2018): 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:
== Problem 1 ==
{{Infobox
Consider the Markov chain of graph coloring
|name        = Infobox
{{Theorem|Markov Chain for Graph Coloring|
|bodystyle    =  
:Start with a proper coloring of <math>G(V,E)</math>. At each step:
|title        = <font size=3>高级算法
# Pick a vertex <math>v\in V</math> and a color <math>c\in[q]</math> uniformly at random.
<br>Advanced Algorithms</font>
# Change the color of <math>v</math> to <math>c</math> if the resulting coloring is proper; do nothing if otherwise.
|titlestyle  =
 
|image        =
|imagestyle  =
|caption      =
|captionstyle =
|headerstyle  = background:#ccf;
|labelstyle  = background:#ddf;
|datastyle    =
 
|header1 =Instructor
|label1  =
|data1  =
|header2 =
|label2  =
|data2  = 尹一通<br>郑朝栋
|header3 =
|label3  = Email
|data3  = yinyt@nju.edu.cn chaodong@nju.edu.cn 
|header4 =
|label4= office
|data4= 计算机系 804
|header5 = Class
|label5  =
|data5  =
|header6 =
|label6  = Class meetings
|data6  = Wednesday, 8am-10am <br> 仙I-319
|header7 =
|label7  = Place
|data7  =
|header8 =
|label8  = Office hours
|data8  = Wednesday, 10am-12pm <br>计算机系 804（尹一通）、302（郑朝栋）
|header9 = Textbooks
|label9  =
|data9  =
|header10 =
|label10  =
|data10  = [[File:MR-randomized-algorithms.png|border|100px]]
|header11 =
|label11  =
|data11  = Motwani and Raghavan. <br>''Randomized Algorithms''.<br> Cambridge Univ Press, 1995.
|header12 =
|label12  =
|data12  = [[File:Approximation_Algorithms.jpg|border|100px]]
|header13 =
|label13  =
|data13  =  Vazirani. <br>''Approximation Algorithms''. <br> Springer-Verlag, 2001.
|belowstyle = background:#ddf;
|below =
}}
}}


Show that the Markov chain is:
This is the webpage for the ''Advanced Algorithms'' class of fall 2018. Students who take this class should check this page periodically for content updates and new announcements.  
# aperiodic;
# irreducible if <math>q\ge \Delta+2</math>;
# with uniform stationary distribution.


== Problem 2 ==
= Announcement =
Consider the following random walk on hypercube:
* (2018/9/5) 新学期第一次上课。
{{Theorem|Yet another random Walk on Hypercube|
 
: At each step, for the current state <math>x\in\{0,1\}^n</math>:
= Course info =
# pick an <math>i\in\{0,1,2,\ldots,n\}</math> uniformly at random;
* '''Instructor ''': 尹一通、郑朝栋
# flip <math>x_i</math> (let <math>x_i=1-x_i</math>) if <math>i\neq 0</math>.
:*email: yinyt@nju.edu.cn, chaodong@nju.edu.cn
}}
* '''Class meeting''': Wednesday 8am-10am, 仙I-319.
* Show that the random walk is ergodic.
* '''Office hour''': Wednesday 10am-12pm, 计算机系 804.
* Give the stationary distribution of the random walk.
 
* Analyze the mixing time of the random walk by coupling.
= Syllabus =
 
=== 先修课程 Prerequisites ===
* 必须：离散数学，概率论，线性代数。
* 推荐：算法设计与分析。
 
=== Course materials ===
* [[高级算法 (Fall 2018) / Course materials|<font size=3>教材和参考书</font>]]
 
=== 成绩 Grades ===
* 课程成绩：本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩和期末考试成绩综合得出。
* 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。


Hint.1: Construct a coupling rule such that the Hamming distance between two states never increases.
=== <font color=red> 学术诚信 Academic Integrity </font>===
学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。


Hint.2: When constructing the coupling, consider a cyclic permutation of disagreeing positions.
作业完成的原则：署你名字的工作必须由你完成。允许讨论，但作业必须独立完成，并在作业中列出所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。


== Problem 3==
本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 [http://www.acm.org/publications/policies/plagiarism_policy ACM Policy on Plagiarism]的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为，<font color=red> 抄袭和被抄袭双方的成绩都将被取消</font>。因此请主动防止自己的作业被他人抄袭。
Consider the following random walk over all subsets <math>S\in{[n]\choose k}</math> for some <math>k\le \frac{n}{2}</math>:
{{Theorem|Random walk over <math>k</math>-subsets|
: At each step, for the current state <math>S\in{[n]\choose k}</math>:
# with probability <math>p</math>, do nothing;
# else pick an <math>x\in S</math> and a <math>y\in[n]\setminus S</math> independently and uniformly at random, and change the current set to be <math>S\setminus\{x\}\cup\{y\}</math>.
}}
You are allowed to choose a self-loop probability <math>p</math> for your convenience.
* Show that the random walk is ergodic
* Give the stationary distribution of the random walk.
* Prove that the mixing time is <math>O(n\log k)</math> by coupling.


Hint.1: Considering a coupling <math>(S,T)</math>, the <math>[n]</math> is partitioned into <math>S\cap T,S\setminus T,T\setminus S,\overline{S\cup T}</math>. Design a coupling rule to adopt different cases (of where <math>x</math> and <math>y</math> belong).
学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。


Hint.2: Use a cyclic permutation of elements in <math>S\triangle T</math> which is the symmetric difference between <math>S</math> and <math>T</math>.
= Assignments =
* TBA


== Problem 4 ==
= Lecture Notes =
Let <math>G(V,E)</math> be a connected undirected simple graph (no self-loops and parallel edges) defined on <math>n</math> vertices. Let <math>\phi(G)</math> be the expansion ratio of <math>G</math>. <math>G</math> is NOT necessarily regular. For any <math>v\in V</math>, let <math>d_v</math> be the degree of vertex <math>v</math>.
# [[高级算法 (Fall 2018)/Min-Cut and Max-Cut|Min-Cut and Max-Cut]]
* What is the largest possible value for <math>\phi(G)</math>? Construct a graph <math>G</math> with this expansion ratio and explain why it is the largest.
#:  [[高级算法 (Fall 2018)/Probability Basics|Probability basics]]
* What is the smallest possible value for <math>\phi(G)</math>? Construct a graph <math>G</math> with this expansion ratio and explain why it is the smallest.
* Run a lazy random walk on <math>G</math>. What is the stationary distribution? Starting from an arbitrary vertex in an arbitrary unknown <math>G</math>, how long in the worst case should you run the random walk to guarantee the distribution of the current position is within a total variation distance of <math>\epsilon</math> from the stationary distribution? Give an upper bound of the time in terms of <math>n</math> and <math>\epsilon</math>.
* Suppose that the maximum degree of <math>G</math> is known but the graph is not necessarily regular. Design a random walk with uniform stationary distribution. How long should you run the random walk to be within <math>\epsilon</math>-close to the uniform distribution in the worst case?

Revision as of 14:15, 4 September 2018

高级算法
Advanced Algorithms
Instructor
尹一通
郑朝栋
Email yinyt@nju.edu.cn chaodong@nju.edu.cn
office 计算机系 804
Class
Class meetings Wednesday, 8am-10am
仙I-319
Office hours Wednesday, 10am-12pm
计算机系 804（尹一通）、302（郑朝栋）
Textbooks
Motwani and Raghavan.
Randomized Algorithms.
Cambridge Univ Press, 1995.
Vazirani.
Approximation Algorithms.
Springer-Verlag, 2001.
v · d · e

This is the webpage for the Advanced Algorithms class of fall 2018. Students who take this class should check this page periodically for content updates and new announcements.

Announcement

  • (2018/9/5) 新学期第一次上课。

Course info

  • Instructor : 尹一通、郑朝栋
  • email: yinyt@nju.edu.cn, chaodong@nju.edu.cn
  • Class meeting: Wednesday 8am-10am, 仙I-319.
  • Office hour: Wednesday 10am-12pm, 计算机系 804.

Syllabus

先修课程 Prerequisites

  • 必须：离散数学，概率论，线性代数。
  • 推荐：算法设计与分析。

Course materials

成绩 Grades

  • 课程成绩：本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩和期末考试成绩综合得出。
  • 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。

学术诚信 Academic Integrity

学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。

作业完成的原则：署你名字的工作必须由你完成。允许讨论，但作业必须独立完成，并在作业中列出所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。

本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 ACM Policy on Plagiarism的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为， 抄袭和被抄袭双方的成绩都将被取消。因此请主动防止自己的作业被他人抄袭。

学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。

Assignments

  • TBA

Lecture Notes

  1. Min-Cut and Max-Cut
    Probability basics
Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=随机算法_(Spring_2013)/Problem_Set_4&oldid=8055"