Home Page > > Details

CSCI 2300 — Introduction to Algorithms

Lab 4 (document version 1.0) — DUE July 15, 2020

Minimum Spanning Trees and Perfect Matchings

• This lab is to be completed individually. Do not share your work or code with anyone else.

• For all labs, please avoid using Google to find suggestions or solutions. The goal is to use

your own brain to work these problems out, which will help you develop the skills to do well

on the exams and, more importantly, become a substantially better computer scientist.

In this lab, we focus on minimum spanning trees and the new concept of perfect matchings.

1. Show that Prim’s Algorithm works for graphs that contain negative edge weights.

Hint: Start by working out a few examples, then prove the claim by showing that each step

of Prim’s Algorithm works for an edge of negative edge weight.

2. Prove by contradiction that if graph G = (V, E) has a cycle that includes unique heaviest

(highest-weighted) edge e, then e cannot be part of any minimum spanning tree of G.

3. Given undirected tree T = (V, E), write a linear-time algorithm that determines whether T

contains a perfect matching. Here, we define a perfect matching as subset Em of edge set E

that contains edges incident with each vertex exactly once. As an example, in the graph

shown below (not a tree!), we have two perfect matchings, i.e., Em = {{A, B}, {C, D}}

and Em = {{A, C}, {B, D}}.

Be sure to describe the runtime of your algorithm using Big-O() notation.

Hint: Start by looking for specific properties that must be true to have a perfect matching

in a tree (e.g., how many vertices must you have to actually have a perfect matching, how

many perfect matchings can a tree have, etc.?), then generalize into a linear-time algorithm.

What to submit

Please submit a single PDF file called upload.pdf that neatly contains your answers to the above

questions. Be sure to proofread your work and make sure it is clear, concise, and correct.

Contact Us(Ghostwriter Service)

- QQ：99515681
- WeChat：codinghelp
- Email：99515681@qq.com
- Work Time：8:00-23:00

- Ghostwriter Crc Programming,Help With ... 2020-10-27
- Algorithms Programmingghostwriter ,Hel... 2020-10-27
- Help With 158.225 Course Programming,G... 2020-10-27
- Gui Programminghelp With ,Ghostwriter ... 2020-10-27
- 70015 Programminghelp With ,Ghostwrite... 2020-10-27
- Ghostwriter Data Programming Course,He... 2020-10-27
- Comp9021help With ,Python Programmingd... 2020-10-27
- Ghostwriter 159.172 Programming,Help W... 2020-10-27
- Help With Program Programming,Python P... 2020-10-27
- Ghostwriter Fnce90045,Help With Java P... 2020-10-27
- Help With Spss|Help With Processing|Gh... 2020-10-27
- C++ Programmingdebug ,Cs 130Aghostwrit... 2020-10-27
- R Programminghelp With ,Ghostwriter Da... 2020-10-27
- Ghostwriter Ssci 599 Course,Help With ... 2020-10-27
- Cits1001help With ,Java Programmingdeb... 2020-10-26
- Ghostwriter Cfrm 542 Programming,R Cou... 2020-10-26
- Math2392help With ,Ghostwriter R Cours... 2020-10-26
- Help With Comp10002 Programming,Ghostw... 2020-10-26
- Math2392 Programmingghostwriter ,Data ... 2020-10-26
- Cse 320Help With ,Ghostwriter Programm... 2020-10-25

Contact Us - Email：99515681@qq.com WeChat：codinghelp

© 2014 www.asgnhelp.com

Programming Assignment Help！