A guide to events on our campuses.

Assembly Series

A tradition of convening thought leaders since 1953

McKelvey School of Engineering

Brown School

Minimum Spanning Trees

Friday, April 5 | 3:00 PM - 4:00 PM

McKelvey Hall, McKelvey 1020

Zihao Deng
PhD Candidate 
Computer Science & Engineering
Washington University in St. Louis

Minimum spanning trees are very helpful in many network design related applications and algorithms. They are often used in water networks, electrical grids, and computer networks. In this presentation I will discuss the formulation of the network design problem and two greedy algorithms for constructing minimum spanning trees to solve this problem, i.e., Kruskal’s algorithm and Prim’s algorithm. I will then explain the cut property, an important structural property of minimum spanning trees, and use it to prove the effectiveness of both these algorithms.

Talk Location: McKelvey 1020

Event Type



McKelvey School of Engineering


Science & Technology



Computer Science & Engineering
Event Contact


Speaker Information

I’m currently working to complete my PhD in Computer Science & Engineering at Washington University in St. Louis. My research interests include applying mathematical tools such as convex optimization and tensor decomposition to novel machine learning problems, such as developing algorithms for planning in reinforcement learning with an exponentially large environment, and learning stochastic effects in environments expressed in planning domain definition language. Before that, I focused on finding robust numerical solutions in nonlinear differential equations in physics. During my years in academia, I have also accumulated much experience in teaching. I have lectured at the University of Vermont and Washington University in St. Louis on multiple topics such as analysis of algorithms, advanced algorithms and college algebra.

Google Calendar iCal Outlook