- Turning Real-World Problems into CS Problems
- Topics for Feb 8
- Depth-First Search
- Breadth-First Search

Solving "real-world" problems consists of two parts. On the one hand, you need to know how to solve the common algorithmic problems like sorting arrays or finding a minimum spanning tree in a graph. On the other hand, you have to recognize which CS problem is hiding beneath its camouflage.

So today let's talk about some "serious" problems that occur in real life:

- Ordering Train Wagons
- Crossing Rivers
- Navigating Boats
- Building the Tower of Babel

- Depth-First Search
- Breadth-First Search
- Median of 5 in 6 comparisons
- Maintaining the median of n dynamically
- Order-Statistic Trees (augmented red-black trees)
- Review of Problem Set 1

void dfs (TreeElement t) { print(t); if (t.left!=null) dfs(t.left); if (t.right!=null) dfs(t.right); }

void dfs (Vertex u) { if (u has been visited before) return; print(u); mark u as visited; for (each vertex v adjacent to u) { dfs(v); }

void bfs (TreeElement t) { enqueue(t); while (queue is not empty) { x = dequeue(); print(x); if (x.left!=null) enqueue(x.left); if (x.right!=null) enqueue(x.right); } }

void bfs (Vertex u) { enqueue(u); while (queue is not empty) { u = dequeue(); print(u); mark u as visited; for (each vertex v adjacent to u) { if (v has not been visited before) enqueue(v); } } }

*Last modified 2001-02-08*

mdettinger@arsdigita.com |