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:

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

```

## Topics for Feb 8

• Depth-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);
}
```

```

```

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

```

```