CSC 344
Homework 4

Assigned 7 Apr, due 3 May

Note: will not be accepted late!

Problems from the Levitin textbook

A problem out of my head

You're a network administrator concerned about terrorist attacks, either on computers in the network or on cables between computers. You want to know whether

  1. the network is currently connected, i.e. a message can get from any computer to any other; and if so, whether
  2. there is a single computer which, if destroyed, would leave the network no longer connected; or
  3. there is a single cable which, if cut, would leave the network no longer connected.
For each of these three questions,
  1. re-phrase it in graph terminology
  2. give a pseudocode algorithm for solving it
  3. analyze the running time of your algorithm

Last modified: Wed Apr 6 11:38:26 EDT 2005
Stephen Bloch /