随机算法 (Fall 2015)/Problem Set 2 and Permeability (electromagnetism): Difference between pages

From TCS Wiki
(Difference between pages)
Jump to navigation Jump to search
VisualWikitext
imported>Etone
 
(The value of µ0 is 4E-7\pi, this is how it is defined.)
 
Line 1: Line 1:
== Problem 1==
{{MagneticCircuitSegments}}
For any <math>\alpha\ge 1</math>, a cut <math>C</math> in an undirected (multi)graph <math>G(V,E)</math>is called an <math>\alpha</math>-min-cut if <math>|C|\le\alpha|C^*|</math> where <math>C^*</math> is a min-cut in <math>G</math>.  
'''Permeability''' is a [[property]] of a material that describes how [[density|dense]] a [[magnetism|magnetic field]] would be if the same amount of [[electric current|current]] was passed through it. Permeability is measured in henries per [[metre]] (H/m) and its symbol is <math>\mu</math>.  


* Give a lower bound to the probability that a single iteration of Karger's Random Contraction algorithm returns an <math>\alpha</math>-min-cut in a graph <math>G(V,E)</math> of <math>n</math> vertices.
Since [[vacuum|empty space]] has a [[constant]] permeability (called the '''permeability of free space''' or <math>\mu_{0}</math>) of exactly <math>0.0000004 \times \pi</math>, most materials are listed with a ''relative permeability'' (symbol <math>\mu_{r}</math>). Relative permeability is the permeability of the material divided by the permeability of free space (<math>\mu_{r} = \mu / \mu_{0}</math>). The permeability of most materials is very close to 1. That means that the permeability of most materials is close enough that we can typically ignore it and use the permeability of free space instead.<ref>Lines and Fields in Electronic Technology, Stanley and Harrington pg 13</ref> The biggest exceptions are materials called [[ferromagnetism|ferromagnetic materials]]. Some examples are [[iron]] (5000) and [[nickel]] (600). Some materials have been specially designed to have a permeability one million times larger than empty space.<ref>http://info.ee.surrey.ac.uk/Workshop/advice/coils/mu/#mur</ref>


* Use the above bound to estimate the number of distinct <math>\alpha</math>-min cuts in <math>G</math>.
== References ==
{{reflist}}


 
[[Category:Electromagnetism]]
==Problem 2 ==
Suppose that we flip a fair coin <math>n</math> times to obtain <math>n</math> random bits. Consider all <math>m={n\choose 2}</math> pairs of these bits in some order. Let <math>Y_i</math> be the exclusive-or of the <math>i</math>th pair of bits, and let <math>Y=\sum_{i=1}^m Y_i</math> be the number of <math>Y_i</math> that equal 1.
# Show that the <math>Y_i</math> are '''NOT''' mutually independent.
# Show that the <math>Y_i</math> satisfy the property <math>\mathbf{E}[Y_iY_j]=\mathbf{E}[Y_i]\mathbf{E}[Y_j]</math>.
# Compute <math>\mathbf{Var}[Y]</math>.
# Using Chebyshev's inequality, prove a bound on <math>\Pr[|Y-\mathbf{E}[Y]|\ge n]</math>.
 
==Problem 3==
Show that the maximum load when <math>n</math> balls are hashed into <math>n</math> bins using a hash function chosen from a 2-universal family of hash functions is at most <math>O(\sqrt{n})</math> with probability at least 0.99. Generalize this argument to <math>k</math>-universal hash functions.
 
Hint: Perhaps the only information we can use about a 2-universal hash function is the number of collisions. What does it become for <math>k</math>-universal hashing?
 
*(Optional) Can this <math>O(\sqrt{n})</math> be improved if the only thing we assume about the hash function is the 2-universality? Why?
 
== Problem 4==
;The maximum directed cut problem (MAX-DICUT).
We are given as input a directed graph <math>G=(V,E)</math>, with each directed edge <math>(u,v)\in E</math> having a nonnegative weight <math>w_{uv}\ge 0</math>. The goal is to partition <math>V</math> into two sets <math>S\,</math> and <math>\bar{S}=V\setminus S</math> so as to maximize the value of <math>\sum_{(u,v)\in E\atop u\in S,v\not\in S}w_{uv}</math>, that is, the total weight of the edges going from <math>S\,</math> to <math>\bar{S}</math>.
 
* Give a randomized <math>\frac{1}{4}</math>-approximation algorithm based on random sampling.
* Prove that the following is an integer programming for the problem:
:<math>
\begin{align}
\text{maximize} && \sum_{(i,j)\in E}w_{ij}z_{ij}\\
\text{subject to} && z_{ij} &\le x_i, & \forall (i,j)&\in E,\\
&& z_{ij} &\le 1-x_j, & \forall (i,j)&\in E,\\
&& x_i &\in\{0,1\}, & \forall i&\in V,\\
&& 0 \le z_{ij}&\le 1, & \forall (i,j)&\in E.
\end{align}
</math>
* Consider a randomized rounding algorithm that solves an LP relaxation of the above integer programming and puts vertex <math>i</math> in <math>S</math> with probability <math>f(x_i^*)</math>. We may assume that <math>f(x)</math> is a linear function in the form <math>f(x)=ax+b</math> with some constant <math>a</math> and <math>b</math> to be fixed. Try to find good <math>a</math> and <math>b</math> so that the randomized rounding algorithm has a good approximation ratio.
 
==Problem 5 ==
The set cover problem is defined as follows:
*Let <math>U=\{u_1,u_2,\ldots,u_n\}</math> be a set of <math>n</math> elements, and let <math>\mathcal{S}=\{S_1,S_2,\ldots,S_m\}</math> be a family of subsets of <math>U</math>. For each <math>u_i\in U</math>, let <math>w_i</math> be a nonnegative weight of <math>u_i</math>. The goal is to find a subset <math>V\subseteq U</math> with the minimum total weight <math>\sum_{i\in V}w_i</math>, that intersects with all <math>S_i\in\mathcal{S}</math>.
 
This problem is '''NP-hard'''.
 
('''Remark''': There are two equivalent definitions of the set cover problem. We take the '''hitting set''' version.)
 
Questions:
* Prove that the following is an integer programming for the problem:
:<math>
\begin{align}
\text{minimize} &&  \sum_{(i,j)\in E}w_{i}x_{i}\\
\text{subject to} && \sum_{i:u_i\in S_j}x_i &\ge 1, &1\le j\le m,\\
&& x_i &\in\{0,1\}, & 1\le i\le n.
\end{align}
</math>
* Give a randomized rounding algorithm which returns an <math>O(\log m)</math>-approximate solution with probability at least <math>\frac{1}{2}</math>. (Hint: you may repeat the randomized rounding process if there remains some uncovered subsets after one time of applying the randomized rounding.)

Latest revision as of 16:23, 28 June 2016

Magnetic Circuits
Conventional Magnetic Circuits
Phasor Magnetic Circuits
Related Concepts
Gyrator-capacitor model variables
This box: view · talk · edit

Permeability is a property of a material that describes how dense a magnetic field would be if the same amount of current was passed through it. Permeability is measured in henries per metre (H/m) and its symbol is [math]\displaystyle{ \mu }[/math].

Since empty space has a constant permeability (called the permeability of free space or [math]\displaystyle{ \mu_{0} }[/math]) of exactly [math]\displaystyle{ 0.0000004 \times \pi }[/math], most materials are listed with a relative permeability (symbol [math]\displaystyle{ \mu_{r} }[/math]). Relative permeability is the permeability of the material divided by the permeability of free space ([math]\displaystyle{ \mu_{r} = \mu / \mu_{0} }[/math]). The permeability of most materials is very close to 1. That means that the permeability of most materials is close enough that we can typically ignore it and use the permeability of free space instead.[1] The biggest exceptions are materials called ferromagnetic materials. Some examples are iron (5000) and nickel (600). Some materials have been specially designed to have a permeability one million times larger than empty space.[2]

References

Template:Reflist

  1. ↑ Lines and Fields in Electronic Technology, Stanley and Harrington pg 13
  2. ↑ http://info.ee.surrey.ac.uk/Workshop/advice/coils/mu/#mur
Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=随机算法_(Fall_2015)/Problem_Set_2&oldid=7719"