## Description

1. Consider the weighted graph below:

(a) Demonstrate Prim’s algorithm starting from vertex A. Write the edges in the order they were added

to the minimum spanning tree.

(b) Demonstrate Dijkstra’s algorithm on the graph, using vertex A as the source. Write the vertices in the

order which they are marked and compute all distances at each step.

2. Below is a list of courses and prerequisites for a factious CS degree.

Course Prerequisite

CS 150 None

CS 151 CS 150

CS 221 CS 151

CS 222 CS 221

CS 325 CS 221

CS 351 CS 151

CS 370 CS 151

CS 375 CS 151, CS 222

CS 401 CS 375, CS 351, CS 325, CS 222

CS 425 CS 325, CS 222

MATH 200 None

MATH 201 MATH 200

(a) Draw a directed acyclic graph (DAG) that represents the precedence among the courses.

(b) Give a topological sort of the graph.

(c) Find an order in which all the classes can be taken.

(d) Determine the length of the longest path in the DAG. How did you find it? What does this represent?

CS 325 – Homework Assignment 3

3. Suppose you have an undirected graph G=(V,E) and you want to determine if you can assign two

colors (blue and red) to the vertices such that adjacent vertices are different colors. This is the graph

Two-Color problem. If the assignment of two colors is possible, then a 2-coloring is a function C: V ->

{blue, red} such that C(u) C(v) for every edge (u,v) E. Note: a graph can have more than one 2-

coloring.

Give an O(V + E) algorithm to determine the 2-coloring of a graph if one exists or terminate with the

message that the graph is not Two-Colorable. Assume that the input graph G=(V,E) is represented using

adjacency lists.

(a) Give a verbal description of the algorithm and provide detailed pseudocode.

(b) Analyze the running time.

4. A region contains a number of towns connected by roads. Each road is labeled by the average

number of minutes required for a fire engine to travel to it. Each intersection is labeled with a circle.

Suppose that you work for a city that has decided to place a fire station at location G. (While this

problem is small, you want to devise a method to solve much larger problems).

(a) What algorithm would you recommend be used to find the fastest route from the fire station to

each of the intersections? Demonstrate how it would work on the example above if the fire station is

placed at G. Show the resulting routes.

(b) Suppose one ”optimal” location (maybe instead of G) must be selected for the fire station such that

it minimizes the distance to the farthest intersection. Devise an algorithm to solve this problem given an

arbitrary road map. Analyze the time complexity of your algorithm when there are f possible locations

for the fire station (which must be at one of the intersections) and r possible roads.

(c) In the above graph what is the “optimal” location to place the fire station? Why?