ADU Recitations (Feb 7-8)

ADU Recitations (Feb 7-8)

a WimpyPoint presentation owned by Mark Dettinger

Turning Real-World Problems into CS Problems


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:

    
    
    
    

Topics for Feb 8


    
    
    
    

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

We use a queue to store the nodes of the tree. At the start the queue is empty.
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

We use a queue to store vertices. At the start the queue is empty.
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