CSC 204 Homework 5 - Graphs: Algorithm Design and Analysis, UK

Published: 10 Dec, 2024
Category Homework Subject Computer Science
University Module Title CSC 204 - Algorithm Design and Analysis Homework 5 - Graphs

1. BFS and DFS (20 points)

BFS And DFS

a) Given the graph above suppose we run breadth-rst-search with the source vertex as A. Assume that vertices are entered into the queue in alphabetical order. Write down the order in which the vertices would be discovered. (7 points)

b) Given the graph above suppose we run depth-rst-search. Assume that the rst vertex explored is vertex A, and that neighbor vertices are visited in alphabetical order. Write down the order in which the vertices would be discovered. (7 points)

c) State both the discovery and nishing times of each vertex after running depth-rst-search in part (b). (6 points)

2. Graphs (20 points) 

Algorithm Design and Analysis

a) Show the topological sort that would be achieved after running depth rst search such that vertex m is the rst vertex explored, and the neighbor vertices are visited in alphabetical order. (5 points)

b) Draw boundaries around all of the strongly connected components of the graph below. (5 points)

CSC 204 Homework 5 - Graphs Algorithm Design and Analysis

c)  Perform Kruskal’s Algorithm on the graph below and draw the resulting minimum spanning tree. If two edges have the same weight, visit the edge that has the vertex ID with smallest value rst. (5 points)

CSC 204 Homework 5 - Graphs:  Algorithm Design and Analysis

d) Perform Dijkstra's Algorithm on the graph below and state the cost of the shortest path to each vertex with vertex 0 as the source. (5 points)

CSC 204 Homework 5 - Graphs

3. True/False - If you answer False you must provide an explanation or counterexample. (15 points)

a) Dijkstra's algorithm can handle graphs with negative edge weights.

b) A directed acyclic graph (DAG) always has a topological ordering.

c) A graph where all edges have distinct weights can have more than one minimum spanning tree.

d) Let T be a minimum spanning tree of a graph G. Then for any two vertices u,v the path from u to v in T is a shortest path from u to v in G.

e) A graph can have multiple topological orderings.

Looking for Assignment help Online Service? Our expert team is ready to assist UK students with CSC 204 Algorithm Design and Analysis Homework 5 Graphs . We cover key topics like DFS-BFS components, sorting algorithms, Dijkstra algorithm, Kruskal’s Algorithm, topological sorting, and strongly connected components of graphs. With years of experience, we provide homework support tailored to your needs. Expect 100% plagiarism-free content and get access to an AI Free assignment example to guide your learning. Let our homework helpers for all subject solutions support your success in mastering algorithm design and analysis!
Homework 1 - Nonlinear Finite Element Methods, UK

Consider the following benchmark: a cantilever beam of length L = 5 m, made of steel (E = 200 GPa, G = 80 GPa) with an IPE 100 profile (A = 10.32 cm2, Aweb = 3.63 cm2, I = 171 cm4, shear correction factor κ = Aweb/A, fully fixed on the left and loaded by a single force F = 1 N on the right end.

CO7207 Generative Development 2025: Homework (HW1) : UML Modelling and Programming with EMF (Eclipse Modelling Framework)

In this homework you will develop software models for a system designed to support a business. You will choose the business and the main functionality of the system

Data Mining and Neural Networks Homework 1

Study how the number of prototypes depends on the number of points for two convex well-separated classes and Prepare a series of examples with more sophisticated non-convex shapes of well-separated classes.

Online Assignment Help in UK