Turning Real-World Problems into CS Problems

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

Topics for Feb 8

• 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

Depth-First Search

DFS in a Binary Tree

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

DFS in a Graph

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);
}

Breadth-First Search

BFS in a Binary Tree

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);
  }
}

BFS in a Graph

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