CSCI 2300代做、代写Algorithms、代写Python，c/c++，Java程序语言-代写C/C++编程

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.