CSC 344
Homework 2

Assigned Feb. 23, due Mar. 7

Problems from the textbook

• Chapter 3, Exercise 3, algorithm to find a cycle or a topological ordering.
• Chapter 3, Exercise 7, sorta-proof about connectedness.
• Chapter 3, Exercise 9, sorta-proof and algorithm about articulation points.
• Chapter 3, Exercise 12, algorithm for checking consistency of life spans.

A problem from another textbook

Recall the definition of a connected graph. In this problem we'll study how securely connected a graph is. (For example, if we think of the graph as representing a computer network, could an enemy disconnect the network by sabotaging a single computer or communication link?)

A bridge edge is defined as an edge which, if removed, would leave a disconnected graph.

An articulation point is defined as a vertex which, if removed (with all its incident edges) would leave a disconnected graph.

Write and analyze an efficient algorithm which takes in an undirected, connected graph and finds all its bridge edges.

Write and analyze an efficient algorithm which takes in an undirected, connected graph and finds all its articulation points.

For both of these, you'll get partial credit for a correct but inefficient algorithm.

Hint: It may help to start by drawing a graph with a single bridge edge or an articulation point, run a breadth-first or depth-first search on it, and see what's special about the bridge edge or articulation point. Then try one with two bridge edges or two articulation points....

Another problem from another textbook

The diameter of an (undirected) graph is defined as the maximum, over all pairs of vertices, of the shortest-path distance between the vertices.

1. Assuming that the graph is a tree, give and analyze an efficient algorithm to compute the diameter.
2. For extra credit, give and analyze an efficient algorithm to compute the diameter without the assumption that the graph is a tree.

And another...

A directed graph is said to be semiconnected if for every pair of vertices (u,v), either there is a path from u to v or there is a path from v to u (or both). Give and analyze an efficient algorithm to decide whether a directed graph is semiconnected.

Programming

1. In a programming language of your choice, develop a data structure to represent graphs (and directed graphs), with names for each vertex and numeric weights for each edge.
2. Choose one of the algorithms you wrote for this assignment, and implement it in a real programming language, using the above data structure.