Path: utzoo!attcan!uunet!cs.utexas.edu!usc!apple!genbank!bionet!ig!arizona!mike
From: mike@cs.arizona.edu (Mike Coffin)
Newsgroups: comp.software-eng
Subject: Re: CS education [engineering, mathematics, and computer science]
Message-ID: <15730@megaron.cs.arizona.edu>
Date: 24 Nov 89 18:55:02 GMT
References: <34788@regenmeister.uucp>
Organization: U of Arizona CS Dept, Tucson
Lines: 21

From article <34788@regenmeister.uucp>, by chrisp@regenmeister.uucp (Chris Prael):
> Second, graph theory is obviously fundamental to the solution of a small
> but useful class of applications (such as trace routers for PC board
> design).  That does not make it fundamental to computing.

I think graph theory would have to be considered fundamental to
algorithm design.  A huge number of computing problems are naturally
modeled by graphs because graphs are the natural model for collections
of objects that are related in some way.  Problems as different
looking as process scheduling, register allocation, and DNA sequence
reconstruction lead (very naturally) to solving problems over graphs.
Any good designer of algorithms must be familiar with basic graph
algorithms such as topological sorting, shortest-path algorithms,
network-flow algorithms, and depth- and breadth-first search.



-- 
Mike Coffin				mike@arizona.edu
Univ. of Ariz. Dept. of Comp. Sci.	{allegra,cmcl2}!arizona!mike
Tucson, AZ  85721			(602)621-2858