MIT 公开课 - 高等算法 lec23

《高级算法设计与分析》课程教学大纲课程代码：201400590任课教师（课程负责人）：林海任课教师（团队成员）：陈刚、沈志东课程中文名称: 高级算法设计与分析课程英文名称：Advanced algorithm design and analysis课程类别：学科通开课课程学分数：2课程学时数：32授课对象：网络空间安全及相关专业硕士研究生一．课程性质《高级算法设计与分析》是网络空间安全及相关专业硕士研究生的一门学科通开课程。

二、教学目的与要求本课程是对本科课程《算法设计与分析》的扩展和提高。

算法是计算机最核心的内容，计算机科学也被称为算法科学。

通过本科学习，学生已经掌握了分治、动态规划、回溯等基本算法，本课程在这些算法的基础上进一步培养学生的算法设计和分析能力，培养学生“时间高效和空间高效地”解决实际问题思维习惯和动手能力，进一步提高学生的算法修养。

本课程详细讲授了线性规划、最大/最小流问题、NP完全性理论、近似算法和随机算法等方面的相关知识，同时通过对各种算法的代码分析，使硕士研究生掌握各种算法原理的同时理解算法的设计思想，从而能够在实际中结合实际问题设计自己的算法，实现理论与实践的统一。

三．教学内容本课程由七大部分组成：（一）算法回顾（4学时）1.递归和分治2.动态规划3.贪心4.回溯（二）线性规划及对偶问题 (6学时)1.基本概念和例子2.图解法3.线性规划的标准形4. 可行解的性质5．单纯形法和单纯形表6．对偶线性规划7．对偶单纯形法8．整数线性规划及其分支界限发9．线性规划的应用和实例（三）最大流 (6学时)1．网络流及其性质2. 最大流与最小割的概念3. Ford-Fulkeson算法和Dinic算法4. 最小费用流与Floyd算法5. 最小费用流的负回路算法与最短路径算法6. 网络流算法的应用（四）NP完全性问题 (6学时)1．NP完全理论的基本概念2. 难解问题与易解问题、判定问题3. NP类与P类4. 几个NP完全问题:顶点覆盖、哈密顿回路与货郎问题、恰好覆盖、子集和、0-1背包、整数线性规划等（五）近似算法 (4学时)1．近似算法的设计思想及分析方法2. 基于组合优化的近似算法3. 基于贪心思想的近似算法4. 基于局部搜索的近似算法5. 基于动态规划的近似算法6. 基于线性规划的近似算法7. 不可近似性（六）随机算法(4学时)1．随机算法概述2. 数值随机算法3. 随机选择和拉斯维加斯算法4. 随即快速排序和舍伍德算法5. 蒙特卡罗算法（七）在线算法(2学时)1.在线算法与竞争度分析2.欧几里得最小生成树问题的在线算法3.线性链表在线更新算法四.五．教学方法本课程主要采用教师讲授、课堂讨论、学生自学、课堂练习及期末考试相结合的方法，灵活运用多种教学手段，如多媒体辅助教学、课堂互动教学等，同时注重知识传授上的整体性和连贯性，让学生能够从该课程的应用领域，逐渐了解到知识点，最后深入到该领域的知识体系，通过课堂练习和讨论，提高学生的积极性，引导学生进行自主学习，提高学生对该研究领域的学习兴趣。

如何在⼀年内⾃学完MIT计算机专业的全部33门课程？MIT挑战——项⽬概述计算机⼀直让我着迷。

从⾦融到脸书，算法是隐藏在我们绝⼤部分⽣活之下的语⾔。

我们这个世界最⼤的变⾰是由代码书写的，⼈⼯智能的进步让我们可以通过计算机来理解⼈类的意义。

除了机器谱写的诗篇，计算机科学也⾮常实⽤。

⼀⾏⾏代码创造了财富，激起⾰新的⽕花。

我⼀直都想学习这种语⾔，只不过不想花⼈⽣中四年的宝贵光阴和数⼗万美元去学。

我开始进⾏这项实验是因为想要证明学习这件事不需要录取委员会、SAT考试、数千美元的债务，以及⼤部分学⽣认为的学习⼀门专业所必须的四年时间。

我会失败吗？当然有这种可能——⽐我聪明得多的⼈⾯对MIT这类学校沉重的学业负担也要使出浑⾝解数，⽽且我还打算在没有指导的情况下⽤4倍速度学习同样的内容。

MIT挑战的常见问题1. 你遵循什么规则？2. 你要完成所有作业、论⽂和项⽬吗？3. 你的课程安排和MIT的有区别吗？4. 如果你没有通过⼀门课怎么办？5. 你为什么要这么做？你就是喜欢学习吗？6. 完成之后你会获得⽂凭吗？7. 你连续不断地上课，这不是为了考试填鸭式学习吗？8. 你过去在这个科⽬上有什么经验？问题：你遵循什么规则？因为我没有在MIT注册⼊学（也没有以任何⽅式⾪属于他们），因此我必须⾃⼰建⽴规则，从⽽使挑战公平可⾏。

基本的规则很简单：1. 如果能通过期末考试，则认为我成功完成了该门课程（通过考试通常意味着获得50%以上的分数，尽管我的⽬标⽐这要⾼得多）。

2. 我和MIT的学⽣在相同的限制条件下答题：事先不看考试问题或答案，考试过程中不带笔记或禁⽌携带的材料，在相同的时间限制下完成（如果没有说明，默认是3个⼩时）。

3. 我根据MIT提供的答案给⾃⼰的试卷打分。

我会把两者都贴出来，从⽽任何⼈都可以检查我的打分⽅法。

请记住这只是我挑战的最低要求。

对于要求⼤量编程的科⽬，我试着在可能的范围内完成有代表性的编程作业。

问题：你要完成所有作业、论⽂和项⽬吗？对于理论课程和以数学为主的课程，期末考试通常为评估提供了全⾯的基础，因此我⽤考试作为评估的⼯具。

mit 线性代数
线性代数是一门计算机科学、统计学、信号处理等其他数学领域中所使用的基本数学工具。

线性代数是一门涉及向量、矩阵、空间、几何体和多重变换等内容的数学学科。

线性代数背后的基本概念是空间的抽象，它们用于描述实现空间中的向量、矩阵和几何体的结构关系和变换。

MIT的线性代数课程涉及空间的抽象，描述空间中向量、矩阵和几何体的结构关系和变换。

课程将研究从最基本的向量和矩阵开始，教授向量空间，到矩阵分解、范数、特征值等。

它们将被用来说明这些空间、矩阵和几何体之间的变换以及这些变换的性质。

MIT的线性代数课程的主要内容包括几何课中的矢量分析、代数方面的矩阵论和线性变换、以及线性代数应用。

该课程将会介绍矩阵的性质，例如初等矩阵的性质、秩的概念、行列式的特性以及如何通过LU变换来求解线性方程组。

此外，也会讨论矩阵乘法中几何变换的性质，以及如何计算向量空间中的内积和距离。

此外，该课程还会讨论常见的线性代数应用，例如线性拟合线性方程组的求解、最小二乘方法的应用、最优解的求解、极大似然估计的应用等。

有关统计和信号处理等数学应用，也会详细讨论。

最后，课程还会介绍线性代数在空间变换、游戏开发、照片处理等方面的应用。

MIT线性代数课程旨在让学生了解线性代数的基本概念，学会如何运用数学理论推导出结果，并学会一些线性代数在实际应用中的技
能。

该课程的目标是为学生们提供一个系统的学习环境，完全了解线性代数的基本概念，以及如何运用线性代数理论解决实际问题。

学完该课程，学生们将掌握高效运用线性代数理论和技能，更好地掌握和应用线性代数在实际应用中的重要性。

M IT OpenCourseWare6.453 Quantum Optical CommunicationSpring 2009For information about citing these materials or our Terms of Use, visit: /terms.Massachusetts Institute of TechnologyDepartment of Electrical Engineering and Computer Science6.453 Quantum Optical CommunicationLecture Number 12Fall 2008Jeffrey H. Shapiroc �2006, 2008 Date: Tuesday, October 21, 2008Linear attenuators, phase-insensitive and phase-sensitive linear amplifiersIntroductionIn this lecture will continue our quantum-mechanical treatment of linear attenua­tors and linear amplifiers. Among other things, we will distinguish between phase-insensitive and phase-sensitive amplifiers. We will also show that the attenuator and the phase-insensitive amplifier preserve classicality, i.e., their outputs are classical states when their inputs are classical states. Finally, we will use the transformation effected by the two-mode parametric amplifier to introduce the notion of entangle­ment.Single-Mode Linear Attenuation and Phase-Insensitive Linear AmplificationSlide 3 shows the quantum models for linear attenuation and linear amplification that were presented in Lecture 11. In both cases we are concerned with single-mode quantum fields at the input and output, whose excited modes are as follows,1E ˆin (t )= a ˆin √e −T jωt and E ˆout (t )= a ˆout √e T −jωt , for 0 ≤ t ≤ T , (1)where� √L a ˆin + √1 − L a ˆL , for the attenuatora ˆout = (2)√G a ˆin + √G − 1ˆa †for the amplifier, G , with 0 <L < 1 being the attenuator’s transmissivity and G > 1 being the amplifier’s gain. The presence of the auxiliary-mode annihilation operators, ˆa L and ˆa G , in these input-output relations, ensures that[ˆa out ,a ˆ†]=1,(3) out 1For the sake of brevity, we have omitted the “other terms” that are needed to ensure that these field operators have the appropriate commutators for freely propagating fields. So long as the photodetection measurements that we make are not sensitive to these vacuum-state other modes, there is no loss in generality in using these compact single-mode expressions.as is required for the Eˆout (t ) expression to be a proper photon-units representation of a single-mode quantum field. Minimum noise is injected by the auxiliary modes when they are in their vacuum states, so, unless otherwise noted, we shall assume that they are indeed in these unexcited states.It is easy to show that the annihilation operator input-output relation, (2), implies the following input-output relation for the θ-quadratures, � √L a ˆin θ + √1 − L a ˆL θ , for the attenuator a ˆout θ = (4) √G a ˆin θ + √G − 1ˆa G −θ , for the amplifier,where ˆa θ ≡ Re(ˆa e −jθ) defines the θ-quadrature of an annihilation operator ˆa . Taking the expectation of these equations, with ˆa in being in an arbitrary quantum state, gives, � √L �a ˆin θ �, for the attenuator �a ˆout θ � = √G �aˆin θ �, for the amplifier. (5) Because �a ˆout θ �/�a ˆin θ � is independent of θ, for both the attenuator and the amplifier, we say that these systems are phase-insensitive , i.e., all the input quadratures undergo the same mean-field attenuation (for the attenuator) or gain (for the amplifier). Output State of the AttenuatorIn Lecture 11 we derived the means and variances of photon number and quadrature measurements made on the output of the linear attenuator. Today we will obtain the complete statistical characterization of this output, and use our result to determine when semiclassical theory can be employed for photodetection measurements made on the attenuator’s output. Our route to these results will be through characteristic functions.2We know that the output mode density operator, ˆρout , is completely characterized by its associated anti-normally ordered characteristic function,χρout ζa ˆ†A (ζ∗,ζ)= �e −ζ∗a ˆout e out �. (6)Substituting in from (2) and using the fact that the ˆa in and ˆa L modes are in a product state, with the latter being in its vacuum state, givesχρout a in +√1−L a ˆL )ζ(√L a ˆ†+√1−L a ˆ†)(ζ∗,ζ)= �e−ζ∗(√L ˆe in L � (7) A a in in a L L = �e−ζ∗√L ˆe ζ√L a ˆ†��e −ζ∗√1−L ˆe ζ√1−L a ˆ†� (8) χρin 2(1−L )= A (ζ∗√ζ√e −|ζ|.(9) 2This should not be surprising. We are dealing with a linear quantum transformation. In classical probability theory it is well known that characteristic function techniques are very convenient for dealing with linear classical transformations. So, we are going to see that the same is true in the quantum case.� We won’t use the operator-valued inverse transform to find ˆρout from this result, but we will examine what happens when the ˆa in mode is in the coherent state |αin �. Here, our known expression for the anti-normally ordered characteristic function of the coherent state leads toχρout (ζ∗,ζ)= e −ζ∗√L αin +ζ√L α∗ in e −|ζ|2 , (10)A out which we recognize as being equal to �√L αin |e −ζ∗a ˆout e ζa ˆ†|√L αin �. This shows that a coherent-state input |αin � to the attenuator results in a coherent-state output |√L αin �from the attenuator.3 Moreover, if the input mode is in a classical state, i.e., its density operator has a P -representationρˆin =d 2αP in (α,α∗)|α��α|, (11)with P in (α,α∗) being a joint probability density function for α1 = Re(α) and α2 = Im(α), then it follows that the output mode is also in a classical state, with a proper P -function given by � � P out (α, α∗) = 1 L P in α √L , α∗ √L. (12) The derivation of this scaling relation—which coincides with the like result from clas­sical probability theory—is left as an exercise for the reader. The essential message, however, is not the derivation; it is that linear attenuation (with a vacuum-state auxiliary mode) preserves classicality.Output State of the Phase-Insensitive Linear AmplifierTurning to the phase-insensitive linear amplifier, we will determine its output-state behavior by the same characteristic function technique that we just used for the linear attenuator. Substituting in from (2) and using the fact that the ˆa in and ˆa G modes are in a product state, with the latter being in its vacuum state, givesχρout a in +√G −1ˆa †)ζ(√G a ˆ†+√G −1ˆa G )(ζ∗,ζ)= �e−ζ∗(√G ˆG e in � (13) A �e−ζ∗√G a ˆin ζ√G a ˆin †��e −ζ∗√G −1ˆa †ζ√G −1ˆa G �= e G e (14) = χρin (ζ∗√G,ζ√G ). (15) A Once again, we will not try to get an explicit general result for ˆρout , but only pursue that result for coherent-state inputs. When the ˆa in mode is in the coherent 3This same result can be gleaned from the homework, where the characteristic function approach is used to show that coherent-state inputs to a beam splitter produce coherent-state outputs from the beam splitter.� state |αin �, we find thatχρout 2 a out ζa ˆ†2 A (ζ∗,ζ)= e −ζ∗√G αin +ζ√G α∗ in e −G |ζ|= �√G αin e −ζ∗ ˆe out √G αin �e −(G −1)|ζ|.||(16)Because the classical state2/(G −1) ρˆ= d 2α e π−|(αG |− 1)|α��α|, (17) has an anti-normally ordered characteristic function equal to e −G |ζ|2 , it follows thatthe classical pure-state input |αin � produces a classical mixed-state output whose P ­representation is � √G αin |2/(G −1) ρˆout =d 2αe −|α−π(G − 1)|α��α|. (18) Moreover, if the input state is a classical state with proper P -function P in (α,α∗), we then find that the output state is also classical, with its P -function being given by1 � αα � e −|α|2/(G −1) P out (α,α∗)= G P in √G , √G�π(G − 1) , (19) where � denotes 2-D convolution. The derivation, which we have omitted, is a straight­forward classical probability theory exercise. The key statement to be made here is that the phase-insensitive linear amplifier (with a vacuum-state auxiliary mode) pre­serves classicality.Semiclassical Models for the Linear Attenuator and the Phase-Insensitive Linear AmplifierWe have just seen that the linear attenuator and the phase-insensitive linear amplifier— both with vacuum-state auxiliary modes—preserve classicality. That means if we re­strict the ˆa in mode to be in a classical state, then we can use semiclassical theory to find the statistics of photodetection measurements that are made on the ˆa out mode. Let us explore that semiclassical theory now. From the P -representation transfor­mation that we found above for the linear attenuator, its classical single-mode input and output fields,E in (t ) = a in e −jωt √T and E out (t ) = a out e −jωt√Tfor 0 ≤ t ≤ T , (20) are related by a out = √L a in . (21) This implies that semiclassical photodetection theory applies for the linear attenuator with the output field as given above, i.e.,• Direct detection of the attenuator’s output field yields a final count that is a Poisson-distributed random variable with mean L |a in |2, given knowledge of a in . • Homodyne detection of the attenuator output’s θ-quadrature yields a variance­1/4 Gaussian-distributed random variable with mean √L a in θ , given knowledge of a in .• Heterodyne detection of the attenuator’s output field gives real and imagi­nary quadrature measurements that are statistically independent, variance­1/2 Gaussianrandom variables with mean values √L a in 1 = √L Re(a in ) and √a in 2 = √ Im(a in ), respectively, given knowledge of a in .Physically, this makes perfect classical sense. Think of the attenuator as a beam split­ter with transmissivity L for the input mode, and a zero-field input for its auxiliary mode. In that case it is obvious that a out = √a in will prevail. Things are different, however, for the amplifier, as we will now show.From the P -representation transformation that we found above for the phase-insensitive linear amplifier, its classical single-mode input and output fields,a in e −jωt a out e −jωtE in (t )= √and E out (t )= √for 0 ≤ t ≤ T , (22) are related bya out = √G a in + n. (23)In the last expression, n is a complex-valued random variable—statistically indepen­dent of a in —whose real and imaginary parts are statistically independent, zero-mean, variance (G − 1)/2 Gaussian random variables. This implies that semiclassical pho­todetection theory applies for the linear amplifier with the output field as given above, i.e.,• Direct detection of the amplifier’s output field yields a final count that is a Poisson-distributed random variable with mean |√a in + n |2, given knowledge of a in and n .• Homodyne detection of the amplifier output’s θ-quadrature yields a variance-1/4 Gaussian-distributed random variable with mean √G a in θ +n θ, given knowledge of a in and n , where n θ ≡ Re(ne −jθ).• Heterodyne detection of the attenuator’s output field gives real and imaginary quadrature measurements that are statistically independent, variance-1/2 Gaus­sian random variables with mean values √G a in 1 + n 1 = √G Re(a in ) + Re(n ) and √G a in 2 + n 2 = √G Im(a in ) + Im(n ), respectively, given knowledge of a in and n , where n 1 ≡ Re(n ) and n 2 ≡ Im(n ).� � The conditioning on n should be removed, as we will never have prior knowledge of its value. The direct detection result can be derived from a related case that will be treated on the homework. The homodyne and heterodyne results are trivial to obtain, because n 1 and n 2 are statistically independent, identically distributed, zero-mean, variance-(G − 1)/2 random variables. We then have that• Direct detection of the amplifier’s output field yields a final count that, given knowledge of a in , is a Laguerre-distributed random variable,2 Pr( N = n | a in )= (G − 1)n e −|a in |L n −(G |a in −|21), for n =0, 1, 2,..., (24) G n +1 where L n () is the n th Laguerre polynomial.·• Homodyne detection of the amplifier output’s θ-quadrature yields a variance­(2G − 1)/4 Gaussian-distributed random variable with mean √G a in θ , given knowledge of a in• Heterodyne detection of the attenuator’s output field gives real and imag­inary quadrature measurements that are statistically independent, variance-G/2 Gaussian random variables with mean values √G a in 1 = √G Re(a in ) and √G a in 2 = √G Im(a in ), respectively, given knowledge of a in .As as final exercise, in this semiclassical analysis, let us use the conditional direct detection statistics—i.e., those given both a in and n —to find the mean and variance of the final photocount N . Define N = √G a in + n . From the Poisson distribution we know that the conditional mean and conditional variance of N areE ( N |N )= N and var( N |N )= E ( N 2 |N ) − [E ( N |N )]2 = N , (25) where E ( ·|N ) denotes expectation with respect to the probability mass function Pr( N = n |N ), i.e., the Poisson distribution with mean N . To remove the condi­tioning on n that is implicit in the preceding mean and variance formulas, we average them over the conditional statistics of N given only knowledge of a in . The mean is easily found,E ( N | a in )= E n (|√G a in + n |2) (26)= G ||2 +2√G [a in E n (n ∗)+ √G a ∗ E n (n )] + E n (|n |2) (27)a in in = G |a in |2 +(G − 1), (28)where E ( ·| a in ) denotes expectation with respect to the probability mass function Pr( N = n | a in ) and E n (·) denotes expectation with respect to the Gaussian prob­ability density function for n , i.e., the joint probability density function for n 1 and n 2.For the mean-squared value of N , conditioned only on knowledge of a in , we proceed as follows. From the Poisson distribution we know that4E ( N 2 | a in )= E n (|√G a in + n |+ |√G a in + n |2). (29)Working on the first term on the right-hand side leads to4) G 2E n (|√G a in + n |= |a in |4 +2G 3/2|a in |2[a in E n (n ∗)+ a in ∗ E n (n )]+4G |a in |2E n (|n |2)+ G [a 2 E n (n ∗2)+ a ∗2E n (n 2)]in in +2√G [a in E n (|n |2 n ∗)+ a ∗ in E n (|n |2 n )] + E (|n |4). (30)From the given Gaussian statistics of n , we haveE n (n )= E n (n ∗)= E (n 2)= E (n ∗2)= E n (|n |2 n )= E n (|n |2 n ∗)=0, (31)and E n (|n |2)= G − 1 and E n (|n |4) = 2(G − 1)2 .(32) Putting everything together gives usE ( N 2 | a in )= G |a in |2 +(G − 1) + G 2|a in |4 +4G (G − 1)|a in |2 + 2(G − 1)2 , (33) from which the conditional variance readily follows,var( N | a in )= G |a in |2 +(G − 1) + 2G (G − 1)|a in |2 +(G − 1)2 . (34) Now suppose that a in is a complex-valued classical random variable with known values of �|a in |2�, �|a in |4�, and var(|a in |2). We can now remove the a in conditioning, and we find that�N � = G �|a in |2� +(G − 1)(35) �N 2� = G 2�|a in |4� +4G (G − 1)�|a in |2� + 2(G − 1)2(36)�ΔN 2� =[G �|a in |2� +(G − 1)]+[G 2var(|a in |2)+2G (G − 1)�|a in |2� +(G − 1)2], (37) give the unconditional mean, mean-square, and variance of the photon count N . We have used brackets to group terms in the variance expression (37) for an important reason. The first bracket on the right-hand side of this equation equals �N �, and as such it is the variance contribution from the shot noise (Poissonian­variance noise) in N , i.e., the noise that would be present even if |√G a in + n |were deterministic. The second term on the right-hand side of this equation equals var(|√G a in + n |2), and so it is the variance contribution of the excess noise in N , i.e.,22the noise that is due to randomness in the illumination |√G a in + n |. Thus, we couldalso write (37) as(38)�ΔN 2� = �N � + �ΔN 2�, where the first term on the right is due to shot noise and the second term on the right is due to excess noise.The Two-Mode Parametric AmplifierWe are now ready to tackle the phase-sensitive linear amplifier. To do so, we start with a two-mode model for a degenerate parametric amplifier, as shown on Slide 9. Limiting our field operators at the input and output to the two excited—x -polarized and y -polarized, frequency-ω—modes,4a ˆin x e −jωt a ˆin y e −jωt a ˆout x e −jωt a ˆout y e −jωt E ˆin (t )= √T i x + √T i y and E ˆout (t )= √T i x + √Ti y , (39) for 0 ≤ t ≤ T , where i x and i y are x -and y -directed unit vectors, we write the input-output relation for this system as follows:a ˆout x = µa ˆin x + νa ˆin †y and a ˆout y = µa ˆin y + νa ˆin †x , with |µ|2 −|ν|2 = 1. (40)Equation (40) is a two-mode Bogoliubov transformation. The first thing that we must check is that this transformation—like the single-mode version we em­ployed when we introduced the squeezed states—preserves commutator brackets. It is straightforward to show that this is so, e.g., we have that[ˆa out x ,a ˆ†]= |µ|2[ˆa in x ,a ˆ†]+ |ν|2[ˆa †,a ˆin y ]= |µ|2 −|ν|2 =1. (41)out x in x in y We leave it as an exercise for you to verify that[ˆ,a ˆ†]=1,(42) a out y out y and that[ˆ, ˆ]=[ˆ,a ˆ†]=0. (43)The two-mode Bogoliubov transformation that characterizes this parametric am­plifier embodies both phase-insensitive and phase-sensitive amplification. Suppose that µ and ν are real and positive. We can then make the identifications √G = µ and √G − 1= ν, where G > 1. So,if the ˆa in x and ˆa out x modes are regarded as inputand output, we find that our input-output relation isa out x a out y a out x out y a ˆout x = √G a ˆin x + √G − 1ˆa †.(44) in y 4Here we are suppressing the “other terms” that are needed to make the field operators have proper commutators. As in what we have done earlier in this lecture, so long as our measurements are not sensitive to these vacuum-state other modes, there is no loss of generality in employing these simple two-mode field operator expressions.Taking the ˆa in y mode to be in its vacuum state makes this input-output relationidentical to the phase-insensitive linear amplifier that we considered earlier today. Now, however, for the two-mode parametric amplifier, we have a physical locus for the auxiliary mode.What about phase-sensitive linear amplification? To see how this comes about, let us rewrite the input and output field operators as follows,E ˆin (t )= a ˆin + e −jωt i + + a ˆin − e −jωt i and E ˆout (t )= a ˆout + e −jωt i + + a ˆout − e −jωt i −,√T √T − √T √T (45)where i ± = i x √± 2i y , (46) and a ˆin ± = a ˆin x √± 2 a ˆin y and a ˆout ± = a ˆout x √± 2a ˆout y . (47) Physically, what we have done here is to convert from writing the two field modes in the x -y basis to writing them the ±45◦ basis. Trivial though this change may seem, it has a profound effect on the input-output behavior for a single mode, as we will now demonstrate.Equation (40) leads to the following input-output relation for the ±45◦ modes:a ˆout + = µa ˆin + + νa ˆ†and a ˆout = µa ˆin a †, with µ2 ν2 = 1, (48)in + −− − νˆin − ||−||which is a pair of single-mode Bogoliubov transformations. Suppose that µ and ν are real and positive—with √G = µ and √G − 1= ν for G > 1—and that we regard the ˆa in + and ˆa out + modes as the input and the output. We then have that the meanvalues of the ˆa out + mode’s θ-quadrature obeys �a ˆout +θ � = Re {[(√G + √G − 1)�a ˆin +1 � + j (√G −√G − 1)�a ˆin +2 �]e −jθ} (49)=(√G + √�a ˆin +1 � cos(θ)+(√G −√�a ˆin +2 � sin(θ). (50)where the 1 and 2 quadratures of ˆa in + denote the real and imaginary parts of thisannihilation operator. This mean-field input-output relation is linear, but it is phase sensitive, i.e., for the real-part quadrature (θ = 0) we get amplification,�a ˆout +1 � =(√G + √G − 1)�a ˆin +1 �, where √G + √G − 1 > 1. (51)On the other hand, for the imaginary-part quadrature (θ = π/2) we get attenuation,�a ˆout +2 � =(√G −√G − 1)�a ˆin +2 �, where 0 < √−√G − 1 < 1. (52)Similar phase-sensitive behavior can be seen on the ˆa out mode, only now it is the real− part quadrature that undergoes attenuation whereas the imaginary part quadrature enjoys amplification.Our final task for today will be to use characteristic functions to obtain the com­plete statistical characterization of the two-mode parametric amplifier when √G = µ> 0 and √G − 1= ν> 0. Here, we choose to start from the Wigner characteristic function for the two output modes,5a out x −ζ∗a out y a †+ζy ˆout y χρW out (ζx ∗,ζy ∗,ζx ,ζy )= �e −ζx ∗ˆy ˆ+ζx ˆout x a †�. (53)By substituting in the two-mode Bogoliubov transformation that relates the output annihilation operators to the input annihilation operators it easily seen thatχρout (ζ∗,ζ∗,ζx ,ζy )= χρin (ξ∗,ξ∗,ξx ,ξy ), (54)W x y W x y where ξx = √G ζx −√G − 1 ζ∗ and ξy = √G ζy −√G − 1 ζ∗. (55) y x Using the Baker-Campbell-Hausdorf theorem, we have that the anti-normally ordered characteristic function for ˆρout satisfiesχρout (ζ∗,ζ∗,ζx ,ζy )= χρin (ξ∗,ξ∗,ξx ,ξy )e −(|ζx |2+|ζy |2)/2 . (56)A x y W x y One important special case is worth exhibiting before we close. Let the input modes both be in their vacuum states. Then, because this impliesχρin 2/2 W (ξx ∗,ξy ∗,ξx ,ξy )= e −|ξx |2/2−|ξy |,(57) we find χρout 2+|ζy |2)+2√G (G −1)Re(ζx ζy )A (ζx ∗,ζy ∗,ζx ,ζy )= e −G (|ζx |. (58) Furthermore, becauseχA ρout x (ζx ∗,ζx )= χA ρout (ζx ∗, 0,ζx , 0) = e −G |ζx |2 , (59)and χ ρout y (ζ∗,ζy )= χρout (0,ζ∗, 0,ζy )= e −G |ζy |2, (60) A y A y we see that ˆρout is not a product state, viz.,6χρout (ζ∗,ζ∗,ζx ,ζy )=χρout x (ζ∗,ζx )χ ρout y (ζ∗,ζy ). (61)A x y A x A y Instead, ˆρout is an entangled state, whose properties be the subject of considerable attention in the next few lectures.75Below, we will convert the Wigner characteristic function to the anti-normally ordered charac­teristic function, from which the normally-ordered form of the density operator can be obtained by inverse Fourier transformation or the density operator itself can be found from an operator-valued inverse Fourier transform.6Taking the inverse Fourier transform of both sides of this inequality shows that the normally-ordered form of ˆρout does not factor into the product of the normally-ordered forms of ˆρout x and ρˆout y , and so ˆρout is not a product state.7Strictly speaking, all we have shown, by demonstrating that ˆρout is not a product state, is thatThe Road AheadIn the next lecture we shall continue our work on parametric amplification and entan­glement. There we shall investigate the individual (marginal) output statistics of the a ˆout x and ˆa out y modes, and show that their joint statistics exhibit a photon-twinningbehavior. We shall then employ a dual parametric amplifier setup to produce polar­ization entangled photons, which will be the basis for qubit teleportation.there is dependence (classical or quantum) between the states of the individual output modes ˆa out x and ˆa out y . However, as we will see next lecture, because the two-mode Bogoliubov transformation is unitary, a pure-state input leads to a pure-state output. Thus, when the input modes ˆa in x and a ˆin y are both in their vacuum states, the resulting ˆρout must be of the form |ψ��ψ| for some purestate |ψ� on the joint state space of ˆa out x and ˆa out y . Because this pure state is not a product state it must be entangled.。

Chapter23Michelle Bodnar,Andrew LohrApril12,2016Exercise23.1-1Suppose that A is an empty set of edges.Then,make any cut that has(u,v) crossing it.Then,since that edge is of minimal weight,we have that(u,v)is a light edge of that cut,and so it is safe to add.Since we add it,then,once wefinish constructing the tree,we have that(u,v)is contained in a minimum spanning tree.Exercise23.1-2Let G be the graph with4vertices:u,v,w,z.Let the edges of the graph be (u,v),(u,w),(w,z)with weights3,1,and2respectively.Suppose A is the set {(u,w)}.Let S=A.Then S clearly respects A.Since G is a tree,its minimum spanning tree is itself,so A is trivially a subset of a minimum spanning tree. Moreover,every edge is safe.In particular,(u,v)is safe but not a light edge for the cut.Therefore Professor Sabatier’s conjecture is false.Exercise23.1-3Let T0and T1be the two trees that are obtained by removing edge(u,v) from a MST.Suppose that V0and V1are the vertices of T0and T1respectively. Consider the cut which separates V0from V1.Suppose to a contradiction that there is some edge that has weight less than that of(u,v)in this cut.Then,we could construct a minimum spanning tree of the whole graph by adding that edge to T1∪T0.This would result in a minimum spanning tree that has weight less than the original minimum spanning tree that contained(u,v).Exercise23.1-4Let G be a graph on3vertices,each connected to the other2by an edge, and such that each edge has weight1.Since every edge has the same weight, every edge is a light edge for a cut which it spans.However,if we take all edges we get a cycle.1Exercise23.1-5Let A be any cut that causes some vertices in the cycle on once side of the cut,and some vertices in the cycle on the other.For any of these cuts,we know that the edge e is not a light edge for this cut.Since all the other cuts wont have the edge e crossing it,we won’t have that the edge is light for any of those cuts either.This means that we have that e is not safe.Exercise23.1-6Suppose that for every cut of the graph there is a unique light edge crossing the cut,but that the graph has2spanning trees T and T .Since T and T are distinct,there must exist edges(u,v)and(x,y)such that(u,v)is in T but not T and(x,y)is in T but not T.Let S={u,x}.There is a unique light edge which spans this cut.Without loss of generality,suppose that it is not(u,v). Then we can replace(u,v)by this edge in T to obtain a spanning tree of strictly smaller weight,a contradiction.Thus the spanning tree is unique.For a counter example to the converse,let G=(V,E)where V={x,y,z} and E={(x,y),(y,z),(x,z)}with weights1,2,and1respectively.The unique minimum spanning tree consists of the two edges of weight1,however the cut where S={x}doesn’t have a unique light edge which crosses it,since both of them have weight1.Exercise23.1-7First,we show that the subset of edges of minimum total weight that con-nects all the vertices is a tree.To see this,suppose not,that it had a cycle. This would mean that removing any of the edges in this cycle would mean that the remaining edges would still connect all the vertices,but would have a total weight that’s less by the weight of the edge that was removed.This would con-tradict the minimality of the total weight of the subset of vertices.Since the subset of edges forms a tree,and has minimal total weight,it must also be a minimum spanning tree.To see that this conclusion is not true if we allow negative edge weights,we provide a construction.Consider the graph K3with all edge weights equal to −1.The only minimum weight set of edges that connects the graph has total weight−3,and consists of all the edges.This is clearly not a MST because it is not a tree,which can be easily seen because it has one more edge than a tree on three vertices should have.Any MST of this weighted graph must have weight that is at least-2.Exercise23.1-8Suppose that L is another sorted list of edge weights of a minimum span-ning tree.If L =L,there must be afirst edge(u,v)in T or T which is of smaller weight than the corresponding edge(x,y)in the other set.Without2loss of generality,assume(u,v)is in T.Let C be the graph obtained by adding (u,v)to L .Then we must have introduced a cycle.If there exists an edge on that cycle which is of larger weight than(u,v),we can remove it to obtain a tree C of weight strictly smaller than the weight of T ,contradicting the fact that T is a minimum spanning tree.Thus,every edge on the cycle must be of lesser or equal weight than(u,v).Suppose that every edge is of strictly smaller weight.Remove(u,v)from T to disconnect it into two components.There must exist some edge besides(u,v)on the cycle which would connect these,and since it has smaller weight we can use that edge instead to create a spanning tree with less weight than T,a contradiction.Thus,some edge on the cycle has the same weight as(u,v).Replace that edge by(u,v).The corresponding lists L and L remain unchanged since we have swapped out an edge of equal weight, but the number of edges which T and T have in common has increased by1. If we continue in this way,eventually they must have every edge in common, contradicting the fact that their edge weights differ somewhere.Therefore all minimum spanning trees have the same sorted list of edge weights.Exercise23.1-9Suppose that there was some cheaper spanning tree than T .That is,we have that there is some T so that w(T )<w(T ).Then,let S be the edges in T but not in T .We can then construct a minimum spanning tree of G by considering S∪T .This is a spanning tree since S∪T is,and T makes all the vertices in V connected just like T does.However,we have that w(S∪T )=w(S)+w(T )<w(S)+w(T )=w(S∪T )=w(T).This means that we just found a spanning tree that has a lower total weight than a minimum spanning tree.This is a contradiction,and so our assumption that there was a spanning tree of V cheaper than T must be false.Exercise23.1-10Suppose that T is no longer a minimum spanning tree for G with edge weights given by w .Let T be a minimum spanning tree for this graph.Then we have we have w (T )<w(T)−k.Since the edge(x,y)may or may not be in T we have w(T )≤w (T )+k<w(T),contradicting the fact that T was minimal under the weight function w.Exercise23.1-11If we were to add in this newly decreased edge to the given tree,we would be creating a cycle.Then,if we were to remove any one of the edges along this cycle,we would still have a spanning tree.This means that we look at all the weights along this cycle formed by adding in the decreased edge,and remove the edge in the cycle of maximum weight.This does exactly what we want since we could only possibly want to add in the single decreased edge,and then,from there we change the graph back to a tree in the way that makes its total weight3minimized.Exercise23.2-1Suppose that we wanted to pick T as our minimum spanning tree.Then,to obtain this tree with Kruskal’s algorithm,we will order the edgesfirst by their weight,but then will resolve ties in edge weights by picking an edgefirst if it is contained in the minimum spanning tree,and treating all the edges that aren’t in T as being slightly larger,even though they have the same actual weight. With this ordering,we will still befinding a tree of the same weight as all the minimum spanning trees w(T).However,since we prioritize the edges in T,we have that we will pick them over any other edges that may be in other minimum spanning trees.Exercise23.2-2At each step of the algorithm we will add an edge from a vertex in the tree created so far to a vertex not in the tree,such that this edge has minimum weight.Thus,it will be useful to know,for each vertex not in the tree,the edge from that vertex to some vertex in the tree of minimal weight.We will store this information in an array A,where A[u]=(v,w)if w is the weight of(u,v) and is minimal among the weights of edges from u to some vertex v in the tree built so far.We’ll use A[u].1to access v and A[u].2to access w.Algorithm1PRIM-ADJ(G,w,r)Initialize A so that every entry is(NIL,∞)T={r}for i=1to V doif Adj[r,i]=0thenA[i]=(r,w(r,i))end ifend forfor each u∈V−T dok=min i A[i].2T=T∪{k}k.π=A[k].1for i=1to V doif Adj[k,i]=0and Adj[k,i]<A[i].2thenA[i]=(k,Adj[k,i])end ifend forend forExercise23.2-34Prim’s algorithm implemented with a Binary heap has runtime O((V+ E)lg(V)),which in the sparse case,is just O(V lg(V)).The implementation with Fibonacci heaps is O(E+V lg(V))=O(V+V lg(V))=O(V lg(V)).So, in the sparse case,the two algorithms have the same asymptotic runtimes.In the dense case,we have that the binary heap implementation has runtime O((V+E)lg(V))=O((V+V2)lg(V))=O(V2lg(V)).The Fibonacci heap implementation however has a runtime of O(E+V lg(V))=O(V2+V lg(V))= O(V2).So,in the dense case,we have that the Fibonacci heap implementation is asymptotically faster.The Fibonacci heap implementation will be asymptotically faster so long as E=ω(V).Suppose that we have some function that grows more quickly than linear,say f,and E=f(V).The binary heap implementation will have runtime O((V+E)lg(V))=O((V+f(V))lg(V))=O(f(V)lg(V)).However, we have that the runtime of the Fibonacci heap implementation will have run-time O(E+V lg(V))=O(f(V)+V lg(V)).This runtime is either O(f(V))or O(V lg(V))depending on if f(V)grows more or less quickly than V lg(V)re-spectively.In either case,we have that the runtime is faster than O(f(V)lg(V)).Exercise23.2-4If the edge weights are integers in the range from1to|V|,we can make Kruskal’s algorithm run in O(Eα(V))time by using counting sort to sort the edges by weight in linear time.I would take the same approach if the edge weights were integers bounded by a constant,since the runtime is dominated by the task of deciding whether an edge joins disjoint forests,which is independent of edge weights.Exercise23.2-5If there the edge weights are all in the range1,...,|V|,then,we can imagine adding the edges to an array of lists,where the edges of weight i go into the list in index i in the array.Then,to decrease an element,we just remove it from the list currently containing it(constant time)and add it to the list corresponding to its new value(also constant time).To extract the minimum wight edge,we maintain a linked list among all the indices that contain non-empty lists,which can also be maintained with only a constant amount of extra work.Since all of these operations can be done in constant time,we have a total runtime O(E+V).If the edge weights all lie in some bounded universe,suppose in the range 1to W.Then,we can just vEB tree structure given in chapter20to have the two required operations performed in time O(lg(lg(W))),which means that the total runtime could be made O((V+E)lg(lg(W))).Exercise23.2-6For input drawn from a uniform distribution I would use bucket sort with5Kruskal’s algorithm,for expected linear time sorting of edges by weight.This would achieve expected runtime O(Eα(V)).Exercise23.2-7Wefirst add all the edges to the new vertex.Then,we preform a DFS rooted at that vertex.As we go down,we keep track of the largest weight edge seen so far since each vertex above us in the DFS.We know from exercise23.3-6that in a directed graph,we don’t need to consider cross or forward edges.Every cycle that we detect will then be formed by a back edge.So,we just remove the edge of greatest weight seen since we were at the vertex that the back edge is going to.Then,we’ll keep going until we’ve removed one less than the degree of the vertex we added many edges.This will end up being linear time since we can reuse part of the DFS that we had already computed before detecting each cycle.Exercise23.2-8Professor Borden is mistaken.Consider the graph with4vertices:a,b,c, and d.Let the edges be(a,b),(b,c),(c,d),(d,a)with weights1,5,1,and5 respectively.Let V1={a,d}and V2={b,c}.Then there is only one edge incident on each of these,so the trees we must take on V1and V2consist of precisely the edges(a,d)and(b,c),for a total weight of10.With the addition of the weight1edge that connects them,we get weight11.However,an MST would use the two weight1edges and only one of the weight5edges,for a total weight of7.Problem23-1a.To see that the second best minimum spanning tree need not be unique,weconsider the following example graph on four vertices.Suppose the vertices are{a,b,c,d},and the edge weights are as follows:a b c da−143b1−52c45−6d326−Then,the minimum spanning tree has weight7,but there are two spanning trees of the second best weight,8.b.We are trying to show that there is a single edge swap that can demote ourminimum spanning tree to a second best minimum spanning tree.In obtaining the second best minimum spanning tree,there must be some cut of a single vertex away from the rest for which the edge that is added is not light,otherwise,we wouldfind the minimum spanning tree,not the second best minimum spanning tree.Call the edge that is selected for that cut for6the second best minimum spanning tree(x,y).Now,consider the same cut, except look at the edge that was selected when obtaining T,call it(u,v).Then,we have that if consider T−{(u,v)}∪{(x,y)},it will be a second best minimum spanning tree.This is because if the second best minimum spanning tree also selected a non-light edge for another cut,it would end up more expensive than all the minimum spanning trees.This means that we need for every cut other than the one that the selected edge was light.This means that the choices all align with what the minimum spanning tree was.c.We give here a dynamic programming solution.Suppose that we want tofind it for(u,v).First,we will identify the vertex x that occurs immediately after u on the simple path from u to v.We will then make max[u,v]equal to the max of w((u,x))and max[w,v].Lastly,we just consider the case that u and v are adjacent,in which case the maximum weight edge is just the single edge between the two.If we canfind x in constant time,then we will have the whole dynamic program running in time O(V2),since that’s the size of the table that’s being built up.Tofind x in constant time,we preprocess the tree.Wefirst pick an arbitrary root.Then,we do the preprocessing for Tarjan’s off-line least common an-cestors algorithm(See problem21-3).This takes time just a little more than linear,O(|V|α(|V|)).Once we’ve computed all the least common ancestors, we can just look up that result at some point later in constant time.Then, tofind the w that we should pick,wefirst see if u=LCA(u,v)if it does not,then we just pick the parent of u in the tree.If it does,then weflip the question on its head and try to compute max[v,u],we are guaranteed to not have this situation of v=LCA(v,u)because we know that u is an ancestor of v.d.We provide here an algorithm that takes time O(V2)and leave open if thereexists a linear time solution,that is a O(E+V)time solution.First,we find a minimum spanning tree in time O(E+V lg(V)),which is in O(V2).Then,using the algorithm from part c,wefind the double array max.Then, we take a running minimum over all pairs of vertices u,v,of the value of w(u,v)−max[u,v].If there is no edge between u and v,we think of the weight being infinite.Then,for the pair that resulted in the minimum value of this difference,we add in that edge and remove from the minimum spanning tree, an edge that is in the path from u to v that has weight max[u,v].Problem23-2a.We’ll show that the edges added at each step are safe.Consider an un-marked vertex u.Set S={u}and let A be the set of edges in the tree so far. Then the cut respects A,and the next edge we add is a light edge,so it is safe for A.Thus,every edge in T before we run Prim’s algorithm is safe for T.Any edge that Prim’s would normally add at this point would have to connect two7of the trees already created,and it would be chosen as minimal.Moreover,we choose exactly one between any two trees.Thus,the fact that we only have the smallest edges available to us is not a problem.The resulting tree must be minimal.b.We argue by induction on the number of vertices in G.We’ll assume that|V|>1,since otherwise MST-REDUCE will encounter an error on line6 because there is no way to choose v.Let|V|=2.Since G is connected,there must be an edge between u and v,and it is trivially of minimum weight.They are joined,and|G .V|=1=|V|/2.Suppose the claim holds for|V|=n.Let G be a connected graph on n+1vertices.Then G .V≤n/2prior to thefinal vertex v being examined in the for-loop of line4.If v is marked then we’re done, and if v isn’t marked then we’ll connect it to some other vertex,which must be marked since v is the last to be processed.Either way,v can’t contribute an additional vertex to G .V,so|G .V|≤n/2≤(n+1)/2.c.Rather than using the disjoint set structures of chapter21,we can simply use an array to keep track of which component a vertex is in.Let A be an array of length|V|such that A[u]=v if v=F IND−SET(u).Then FIND-SET(u) can now be replaced with A[u]and UNION(u,v)can be replaced by A[v]=A[u]. Since these operations run in constant time,the runtime is O(E).d.The number of edges in the output is monotonically decreasing,so each call is O(E).Thus,k calls take O(kE)time.e.The runtime of Prim’s algorithm is O(E+V lg V).Each time we run MST-REDUCE,we cut the number of vertices at least in half.Thus,af-ter k calls,the number of vertices is at most|V|/2k.We need to minimizeE+V/2k lg(V/2k)+kE=E+V lg(V)k −V kk+kE with respect to k.If we choosek=lg lg V then we achieve the overall running time of O(E lg lg V)as desired.To see that this value of k minimizes,note that the V k2k term is always less thanthe kE term since E≥V.As k decreases,the contribution of kE decreases,and the contribution of V lg V2k increases.Thus,we need tofind the value of kwhich makes them approximately equal in the worst case,when E=V.Todo this,we set lg V2k =k.Solving this exactly would involve the Lambert Wfunction,but the nicest elementary function which gets close is k=lg lg V.f.We simply set up the inequality E lg lg V<E+V lg V tofind that weneed E<V lg Vlg lg V−1=OV lg Vlg lg V.Problem23-3a.To see that every minimum spanning tree is also a bottleneck spanning tree.Suppose that T is a minimum spanning tree.Suppose there is some edge in it(u,v)that has a weight that’s greater than the weight of the bottleneck8spanning tree.Then,let V1be the subset of vertices of V that are reach-able from u in T,without going though v.Define V2symmetrically.Then, consider the cut that separates V1from V2.The only edge that we could add across this cut is the one of minimum weight,so we know that there are no edge across this cut of weight less than w(u,v).However,we have that there is a bottleneck spanning tree with less than that weight.This is a contradiction because a bottleneck spanning tree,since it is a spanning tree, must have an edge across this cut.b.To do this,wefirst process the entire graph,and remove any edges thathave weight greater than b.If the remaining graph is selected,we can just arbitrarily select any tree in it,and it will be a bottleneck spanning tree of weight at most b.Testing connectivity of a graph can be done in linear time by running a breadthfirst search and then making sure that no vertices remain white at the end.c.Write down all of the edge weights of e the algorithm from section9.3tofind the median of this list of numbers in time O(E).Then,run theprocedure from part b with this median value as the one that you are testing for there to be a bottleneck spanning tree with weight at most.Then there are two cases:First,we could have that there is a bottleneck spanning tree with weight at most this median.Then just throw the edges with weight more than the median,and repeat the procedure on this new graph with half the edges.Second,we could have that there is no bottleneck spanning tree with at most that weight.Then,we should run the procedure from problem23-2 to contract all of the edges that have weight at most this median weight.This takes time O(E lg(lg(V)))and then we are left solving the problem ona graph that now has half the vertices.Problem23-4a.This does return an MST.To see this,we’ll show that we never remove anedge which must be part of a minimum spanning tree.If we remove e,thene cannot be a bridge,which means that e lies on a simple cycle of the graph.Since we remove edges in nonincreasing order,the weight of every edge on the cycle must be less than or equal to that of e.By exercise23.1-5,there isa minimum spanning tree on G with edge e removed.To implement this,we begin by sorting the edges in O(E lg E)time.For each edge we need to check whether or not T−{e}is connected,so we’ll need to run a DFS.Each one takes O(V+E),so doing this for all edges takes O(E(V+E).This dominates the running time,so the total time is O(E2).9b.This doesn’t return an MST.To see this,let G be the graph on3verticesa,b,and c.Let the eges be(a,b),(b,c),and(c,a)with weights3,2,and1 respectively.If the algorithm examines the edges in their order listed,it will take the two heaviest edges instead of the two lightest.An efficient implementation will use disjoint sets to keep track of connected components,as in MST-REDUCE in problem23-2.Trying to union within the same component will create a cycle.Since we make|V|calls to MAKE-SET and at most3|E|calls to FIND-SET and UNION,the runtime is O(Eα(V)).c.This does return an MST.To see this,we simply quote the result from exer-cise23.1-5.The only edges we remove are the edges of maximum weight on some cycle,and there always exists a minimum spanning tree which doesn’t include these edges.Moreover,if we remove an edge from every cycle then the resulting graph cannot have any cycles,so it must be a tree.To implement this,we use the approach taken in part(b),except now we also need tofind the maximum weight edge on a cycle.For each edge which introduces a cycle we can perform a DFS tofind the cycle and max weight edge.Since the tree at that time has at most one cycle,it has at most|V| edges,so we can run DFS in O(V).The runtime is thus O(EV).10。

mit公开课《线性代数》线性代数是数学中的一门重要的基础学科，也是学习大一数学课程的必要知识。

线性代数在工程、物理、经济、运筹学等领域有着广泛的应用。

而MIT公开课《线性代数》正是为了让更多学生更好地理解线性代数，能够有效地应用到实践中去而设计出来的一门免费公开课程。

《MIT公开课《线性代数》》由教授Gilbert Strang教授主讲，是一门由MIT开设的18节课程。

课程的主要内容包括：几何意义的矩阵、向量空间、线性变换、内积空间、多项式拟合和优化等。

在几何意义的矩阵，教授Gilbert Strang让我们以一种形象的方式理解矩阵，使得把矩阵看成是向量的集合，使得矩阵能够更加生动地表达出来。

在向量空间方面，教授主要介绍了内积和外积，并运用它们在实际应用中的能力。

关于线性变换，教授以正交变换和正定矩阵为例，介绍了变换后向量和矩阵的特点。

还有内积空间，这里教授介绍了内积空间的性质，如正定性、完备性等，以及在多项式拟合和优化中的应用，其中用到了最小二乘法和对偶方法。

最后，在MIT的《线性代数》课程中，教授还介绍了矩阵的秩、特征向量和特征值，以及正定矩阵的最小值和最大值的求解方法。

在MIT的课程结束之后，学生们有了更深入的了解线性代数，以及矩阵、向量空间、线性变换、内积空间、多项式拟合和优化等方面对其他应用中的应用。

总之，MIT公开课《线性代数》设计的理念是为了帮助更多的学生了解线性代数，使之能够更好地应用在实际中。

作为一门公开课，《线性代数》的教学注重于基础知识的讲解和深入的理解，以及矩阵、向量空间、线性变换、内积空间、多项式拟合和优化等方面的知识。

因此，有兴趣学习线性代数的学生，可以参加MIT公开课《线性代数》，以深入理解线性代数知识。