CSCI 3110 esign and Analysis of Algorithms I
Fall 2022 Assignment
Instructions:
1. Before starting to work on the assignment, make sure that you have read and
understood policies regarding the assignments of this course, especially the policy
regarding collaboration.
2. Submit a PDF file with your assignment solutions via Brightspace. If you have notused
Brightspace for assignment submission before, you may find the the following
documentation for Brightspace useful:
3. If you submit a joint assignment, only one person in the study group should make
thesubmission. At the beginning of the assignment, clearly write down the names and
student IDs of the up to three group members.
4. We encourage you to typeset your solutions using LaTeX. However, you are free touse
other software or submit scanned handwritten assignments as long as they are legible.
We have the right to take marks off for illegible answers.
5. You may submit as many times as needed before the end of the grace period. A good
strategy is to create an initial submission days in advance after you solve some
problems, and make updates later.
Questions:
1. [10 marks] The minimum spanning tree problem is to look for a spanning tree with
minimum /tal cost Here, we explore another type of objective: finding a spanning
tree for which the most expensive edge is as inexpensive as possible.
More precisely, let G = (V,E) be a connected, undirected graph with n vertices and m
edges, in which each edge is assigned a distinct weight value. Let T be a spanning tree
of G.
We define the jumbo edge of T to be the edge of T with the largest weight. A spanning
tree T0 of G is a skinny spanning tree if there is no spanning tree of G whose jumbo edge
has a smaller weight.
Give a counterexample showing that not every skinny spanning tree of G must be a
minimum spanning tree of the same graph. Be sure to justify your claim with adequate
explanation.
2. [10 marks] Is every minimum spanning tree of G also a skinny spanning tree (as defined
in Question 1) of the same graph?
(a) [3 marks] Give your answer.
(b) [7 marks] Prove the answer that you gave for question (a).
As indicated in the definition for skinny spanning trees in Question 1, you can
assume that edge weights are distinct in G.
3. [10 marks] Consider the graph G in Figure 1.
f
A :?8
B :20
C :10
J :3
a
I : ? 10
b
K : ? 10
E :20
d
H :12
e
D : ? 15
F : ? 25
G :30
c
Figure 1: The graph G in question 1.
Using the Bellman-Ford algorithm, as described in the notes and in the text, either find
the length of the shortest path from vertex a to all the other vertices, or show that there
is a reachable negative-weight cycle. Describe the estimates of the vertices after each
iteration of the algorithm. Within each iteration, examine the edges in order starting
from the edge labeled A and continuing in alphabetic order to the edge labeled K.
Important:
In all of the assignments of this course, when you are asked to give an algorithm for a
problem, you are (unless otherwise indicated) expected to (i) describe the idea behind your
algorithm in English; (ii) provide pseudocode; (iii) argue that your algorithm is correct; and
(iv) analyze its running time.. Since these requirements apply to all the assignments in this
course, this reminder will not be repeated for future assignment questions

Purchase answer to see full
attachment