Fighting Fire with Computer Science - Introduction to Graph and Flow Algorithms

In this InfoSphere module, the students will solve various problems in the field of graph theory using algorithms. The problems are mostly navigation related and embedded into an exciting and real-life oriented story. Over the course of this module, the students discover the differences between breadth- and depth-first search and have the opportunity to create new algorithms. Since the overall goal is to convey the basics of algorithm design, the students won't have to implement any algorithms but visualize their ideas in easy to understand Nassi-Shneiderman diagrams (NDS). To catch the students' interest, the focus is put on the algorithms' operating principle and logic.

In this module, the students adopt the role of fire fighters that have to plan their mission and save lives in three steps.

The first step is to instruct the fire brigade so that it arrives at the operation site as quickly and effectively as possible. Some of the questions that arise during this step are: "How can I find the shortest path? Is the shortest path always the quickest? How can I find the optimal path reliably using algorithms and then put out the fire quickly?" At first, the students try to find the answers by themselves. Afterwards their ideas are systemized in NDSs and compared to professional algorithms which are then applied to find the shortest path.

The second step must be performed after arriving at the burning building. There, the students face another bunch of problems: How to get enough water to the fire's source? Which pipes are needed and where are the bottlenecks of the system? In order to prevail, the students use the Max-Cut-Min-Flow algorithm to analyze, upgrade and expand the pipe system.

While putting out the fire, a person must be rescued from the building. This is the third step of the mission. For this task, the students are given a depth-first search algorithm as well as a breadth-first search algorithm. First, they have to understand both algorithms by reading their pseudocode and then create their own algorithm based on what they learned from them. After applying all algorithms multiple times, they are compared to each other. During this phase, the students should realize that there is no "one perfect algorithm" but only the most efficient depending on the situation.

In the end, the person is saved and the students had an exciting and educational day at the InfoSphere. To close the module, each group presents its results and discusses its discoveries. By now the students should have realized that computer science is important for all of us, can be real-life oriented and might not be as dull and geeky as they thought.