with Leigh Ann Yoder
The Study of Networks
Today we began our study of Networks. Many networks link our society, and we rely on them every day. Examples of everyday networks are telephones, utilities (gas, electric, water), computers, airplane flight paths, and roads.
Engineers spend a lot of time figuring out the most cost effective way to link objects in a network and computers play an important roll in solving these real world problems.
A simple example is air travel. Airlines use airports as hubs, and there are many ways to travel from Destination A to Destination B, but travelers often want the most direct route. Airlines also want to use the most direct routes since fuel and workforce costs add up quickly. Next week we will talk more about how to take the safest route as well as avoid crashes!
The students worked on "The Muddy City Problem". This activity helped them to discover direct and efficient routes by linking a network of houses.
After working through the problem I defined some computer science specific terms: Graph, Node, Vertices, Edge, Network and Tree. Students should understand the difference between a statistical graph and a computer science graph. After mastering these terms we defined a Minimum Spanning Tree.
Students then went on to create and solve their own Muddy City Problems. They were also asked to define rules for solving the Muddy City Problem.
Finally, I explained two famous algorithms for solving Minimum Spanning Trees -- Prim’s Algorithm and Kruskal’s Algorithm. Of course this lesson would not be complete without the famous Traveling Salesman Problem. Ask your student about it and if it has been solved!