Exercise Lecture For Advanced Algorithms(2022 Fall) TA:Hongyang Liu and Chunyang Wang
TA: Hongyang Liu and Chunyang Wang Exercise Lecture For Advanced Algorithms (2022 Fall)
Proofs We have therefore written out the proof 形peove theorem2l Thearem得.I.ou alsags med年asecae to berinale reraion.. with the maximum of attention to detail. Proof.The proof of this theorem can be found in [4.18]. Proof See proof of Theorem 21 以上，我們嚴謹且细緻地 這個定理的證明可以 定理21：你雪要有一個终止徐件， 將之證明完畢。 參照[4,18] 才能結束遞迥的狀態。 證明：見定理2.1的證明 守序善良 中立善良 混亂善良 We suppress the straightforward but tiresome details of the proof. We sketch the proof of this fact. Proof.This is checked by C++. 雄1我們省略了這個雖然直截 我們粗略地帶過這個證明。 證明：已用C++核實。 了當卻也煩人的證明細節· 守序中立 絕對中立 混亂中立 trc or uivine rroviucnee,wIncn Ius I The peador is invited to do it as an exereise PROOF.Trivial. 1This was once revealed to me in a dream. 我們邀請讀者把它當作 See R.Otto,Das Heilige.He has some 一個練習。 證明：顯而易見。 姓1有人托夢給我。 守序邪惡 中立邪惡 混亂邪惡 This is not good
Proofs This is not good…
Some tips on writing proofs 1.Write in complete sentences.You should write proofs like you are writing an article. Use conjunctions like "suppose that","therefore","hence"instead of.and.. 2.Avoid imprecision in proofs. Label(i.e.,name)all relevant objects Define any new terms you are using Avoid informal language,e.g.,contractions,hand-wavy statements,etc. 3.Don't skip nontrivial steps.Explain your arguments.Please let me know clearly you really understand your arguments so that I don't have to guess your purpose and possibly deduct your points
Some tips on writing proofs 1. Write in complete sentences. You should write proofs like you are writing an article. Use conjunctions like “suppose that”, “therefore”, “hence” instead of and 2. Avoid imprecision in proofs. • Label (i.e., name) all relevant objects • Define any new terms you are using •Avoid informal language, e.g., contractions, hand-wavy statements, etc. 3. Don’t skip nontrivial steps. Explain your arguments. Please let me know clearly you really understand your arguments so that I don’t have to guess your purpose and possibly deduct your points. ∵ ∴
Problem Set 1-Problem 1 Modify Karger's algorithm so that it works for the following weighted min-cut problem.Prove that the 2 modified algorithm returns a weighted minimum cut with probability at least n(n-1) Input:an undirected weighted graph G=(V,E),where every edge eEE is associated with a positive real weight we; Output:a cut C in G such that ∑wisminimized. e∈C
Problem Set 1-Problem 1 Modify Karger's algorithm so that it works for the following weighted min-cut problem. Prove that the modified algorithm returns a weighted minimum cut with probability at least . Input: an undirected weighted graph , where every edge is associated with a positive real weight ; Output: a cut in such that is minimized. 2 n(n − 1) G = (V, E) e ∈ E we C G ∑ e∈C we
Problem Set 1-Problem 1 Modify Karger's algorithm so that it works for the following weighted min-cut problem.Prove that the 2 modified algorithm returns a weighted minimum cut with probability at least- n(n-1) Input:an undirected weighted graph G=(V,E),where every edge eEE is associated with a positive real weight we; Output:a cut C in G such that ∑wisminimized. e∈C Thinking:What if all weights are positive integers?
Problem Set 1-Problem 1 Modify Karger's algorithm so that it works for the following weighted min-cut problem. Prove that the modified algorithm returns a weighted minimum cut with probability at least . Input: an undirected weighted graph , where every edge is associated with a positive real weight ; Output: a cut in such that is minimized. 2 n(n − 1) G = (V, E) e ∈ E we C G ∑ e∈C we Thinking: What if all weights are positive integers?
Problem Set 1-Problem 1 Modify Karger's algorithm so that it works for the following weighted min-cut problem.Prove that the 2 modified algorithm returns a weighted minimum cut with probability at least- n(n-1) Input:an undirected weighted graph G=(V,E),where every edge eEE is associated with a positive real weight we; Output:a cut C in G such that ∑wisminimized. eEC Thinking:What if all weights are positive integers? In weighted min-cut problem, an edge with positive integer weight wean edge with weight 1 and multiplicity we
Problem Set 1-Problem 1 Modify Karger's algorithm so that it works for the following weighted min-cut problem. Prove that the modified algorithm returns a weighted minimum cut with probability at least . Input: an undirected weighted graph , where every edge is associated with a positive real weight ; Output: a cut in such that is minimized. 2 n(n − 1) G = (V, E) e ∈ E we C G ∑ e∈C we Thinking: What if all weights are positive integers? In weighted min-cut problem, an edge with positive integer weight w an edge with weight and multiplicity e⟺ 1 we
Problem Set 1-Problem 1 Modify Karger's algorithm so that it works for the following weighted min-cut problem.Prove that the 2 modified algorithm returns a weighted minimum cut with probability at least- nn-1) Input:an undirected weighted graph G=(V,E),where every edge eEE is associated with a positive real weight we; Output:a cut C in G such that ∑wisminimized. eEC Thinking:What if all weights are positive integers? In weighted min-cut problem, an edge with positive integer weight wean edge with weight 1 and multiplicity we Solution sketch:Choose an edge e with probability Pe we! Analysis is similar to Karger's
Problem Set 1-Problem 1 Modify Karger's algorithm so that it works for the following weighted min-cut problem. Prove that the modified algorithm returns a weighted minimum cut with probability at least . Input: an undirected weighted graph , where every edge is associated with a positive real weight ; Output: a cut in such that is minimized. 2 n(n − 1) G = (V, E) e ∈ E we C G ∑ e∈C we Thinking: What if all weights are positive integers? In weighted min-cut problem, an edge with positive integer weight w an edge with weight and multiplicity e⟺ 1 we Solution sketch: Choose an edge with probability ! Analysis is similar to Karger’s. e pe ∝ we
Problem Set 1-Problem 2 Consider the functionf:R”→Rdefinedasf)=fx,&,,x,)=Π(apx-b) i=l Where(and (bisn are unknown integer coefficients such that0abn be the smallest prime strictly greater than n,the function g:is defined as g(d)=g,2,,）-Π(ax-b)where+and·are over the finite field i=1 You can't calculate f()directly,but you have an oracle that can output g()given any. 1.Provef丰0→g丰0. 2.Given any g e(0,1),use to design an algorithm to determine whetherf0,with error probability at most g
Consider the function defined as Where and are unknown integer coefficients such that . Let be the smallest prime strictly greater than , the function is defined as where and are over the finite field . You can’t calculate directly, but you have an oracle that can output given any . 1. Prove . 2. Given any , use to design an algorithm to determine whether , with error probability at most f : ℝn → ℝ f( x ) = f(x1, x2, …, xn) = n ∏ i=1 (ai xi − bi ) {ai }1≤i≤n {bi }1≤i≤n 0 ≤ ai , bi ≤ n p > n n g : ℤn p → ℤp g( x ) = g(x1, x2,…, xn) = n ∏ i=1 (ai xi − bi ) + ⋅ ℤp f( x ) 𝒪 g( x ) x f ≢ 0 ⟹ g ≢ 0 ε ∈ (0,1) 𝒪 f ≢ 0 ε Problem Set 1-Problem 2
Problem Set 1-Problem 2 Consider the functionf:R”→Rdefinedasf)=fx,&,,x,)=Π(apx-b) i=l Where(and (bisn are unknown integer coefficients such that0abn be the smallest prime strictly greater than n,the function g:is defined as =g=(ab)where and are over the finite field i=1 You can't calculate f()directly,but you have an oracle that can output g()given any. 1.Provef丰0→g丰0. 2.Given any g e(0,1),use to design an algorithm to determine whetherf0,with error probability at most g Solution sketch: 1. Use properties of finite fields 2. Choose u.a.r,and use to check.Repeat enough times and use SZ-Lemma to bound the error probability
Consider the function defined as Where and are unknown integer coefficients such that . Let be the smallest prime strictly greater than , the function is defined as where and are over the finite field . You can’t calculate directly, but you have an oracle that can output given any . 1. Prove . 2. Given any , use to design an algorithm to determine whether , with error probability at most f : ℝn → ℝ f( x ) = f(x1, x2, …, xn) = n ∏ i=1 (ai xi − bi ) {ai }1≤i≤n {bi }1≤i≤n 0 ≤ ai , bi ≤ n p > n n g : ℤn p → ℤp g( x ) = g(x1, x2,…, xn) = n ∏ i=1 (ai xi − bi ) + ⋅ ℤp f( x ) 𝒪 g( x ) x f ≢ 0 ⟹ g ≢ 0 ε ∈ (0,1) 𝒪 f ≢ 0 ε Problem Set 1-Problem 2 Solution sketch: 1. Use properties of finite fields . 2. Choose u.a.r, and use to check. Repeat enough times and use SZ-Lemma to bound the error probability. ℤn p x 𝒪
Problem Set 1-Problem 3 In balls-and-bins model,we throw n balls into n bins,in the following three paradigms,respectively: n n balls are thrown into bins independently and uniformly at random.The balls are thrown into bins using the two-choices paradigm. n n 2.The firsballsrhibinsingh paradigm.The remainingballre thrown into bins independently and uniformly at random. 3.Assume all balls are throw in a sequence.The balls in even positions are thrown into bins using the two-choices paradigm.The balls in odd positions balls are thrown into bins independently and uniformly at random. Analyze the asymptotic bound of the max load w.h.p.for each of the three paradigms
In balls-and-bins model, we throw balls into bins, in the following three paradigms, respectively: 1.The first balls are thrown into bins independently and uniformly at random. The remaining balls are thrown into bins using the two-choices paradigm. 2.The first balls are thrown into bins using the two-choices paradigm. The remaining balls are thrown into bins independently and uniformly at random. 3.Assume all balls are throw in a sequence. The balls in even positions are thrown into bins using the two-choices paradigm. The balls in odd positions balls are thrown into bins independently and uniformly at random. Analyze the asymptotic bound of the max load w.h.p. for each of the three paradigms. n n n 2 n 2 n 2 n 2 Problem Set 1-Problem 3