Feb 19
Lots of tricky stuff here ...
Discuss today's homework and my answers .
topics to talk about
- breadth vs depth orderings
- How is "depth first" on a graph different than on a tree?
- For one thing, on a graph you need to keep track of visited nodes.
- How is "depth first" different on a directed vs undirected graph?
- For one thing, you may not get to all the vertices ...
- breadth-first recursive vs iterative
- ... is not the same algorithm - different order, different processing options (at least in the simple implementations).
- edge types :
- undirected - tree, back (what's what depends on start node)
- directed - tree, back, forward, cross (ditto)
- back edge => cycle
- topological sort
- a directed-graph thing
- A linear ordering of vertices such that A -> B means A is before B in ordering.
- Useful for things like scheduling.
- Several algorithms for finding one ... including add-ons to depth-first
problems to look at
OK, enough vague mutterings. Let's sink our teeth into some fun stuff.
two player games : min/max search
... coming ?
in class
We decided in class to look at the Knight's Tour and the Word Ladder problems
... please start doing some coding for Thursday's class on either of these,
and come to class ready to share.
