| Lab Name |
Finding the shortest distance
|
| Subject Area |
Mathematics, and Computer Science
|
| Grade |
6 - 7
|
| Topic |
Dijkstra's algorithm
|
| Experiment Title |
Finding the shortest distance
|
| Hardware |
- COSMOS Toolkit: Computer Node
|
| Software |
- COSMOS Toolkit: Framework
|
| Number of Sessions to teach the topic |
1 session
|
| Educational standards to be addressed |
CSTA K-12 Computer Science Standards (2011)
- CT - Computational Thinking
Computer Science Principles
- 4.1 - Algorithms are precise sequences of instructions for processes that can be executed by a computer and are implemented using programming languages. 4.2 - Algorithms can solve many but not all computational problems.
|
| COSMOS concepts to be used for the lab |
The COSMOS testbed uses routing protocols to send signals and connect devices. Dijkstra's Algorithm is used in the Routing protocols (including wireless communication), the mechanisms that allow information to be gathered and distributed. In Routing protocols, routing algorithms such as Dijkstra's Algorithm, is used to determine paths. In addition, students learn about routing databases. Which is used to store information that the algorithm has discovered.
|
| K12 Educational Goals (How the educational goals are achieved through teaching using the experiment, how the topic is connected to the COSMOS concepts used) |
Mathematically proficient students start by explaining to themselves the meaning of a problem and looking for entry points to its solution. They analyze givens, constraints, relationships, and goals. They make conjectures about the form and meaning of the solution and plan a solution pathway rather than simply jumping into a solution attempt. They consider analogous problems, and try special cases and simpler forms of the original problem in order to gain insight into its solution. They monitor and evaluate their progress and change course if necessary. Older students might, depending on the context of the problem, transform algebraic expressions or change the viewing window on their graphing calculator to get the information they need. Mathematically proficient students can explain correspondences between equations, verbal descriptions, tables, and graphs or draw diagrams of important features and relationships, graph data, and search for regularity or trends. Younger students might rely on using concrete objects or pictures to help conceptualize and solve a problem. Mathematically proficient students check their answers to problems using a different method, and they continually ask themselves, 'Does this make sense?' They can understand the approaches of others to solving complex problems and identify correspondences between different approaches.
Have you ever used a Maps to find the shortest route to your destination or least amount of time to get from one point to another? If so, then you're already familiar with the shortest path problem. In math terms, this is a way to find the shortest possible distance between two vertices (or nodes) on a graph.Suppose we're trying to find the shortest path from your house to Jessica's house. You know the distances between different locations in your neighborhood. These different locations are called vertices and the routes (path) between them are called edges, we can create a weighted graph representing the situation. Dijkstra's algorithm is a step-by-step process we can use to find the shortest path between two vertices in a weighted graph. This algorithm enables us to find shortest distances and minimum costs, making it a valuable tool. In today's lesson we will explore the Shortest Path problem, by performing a hands on activity and then solving the problem with pencil and paper. Afterwards, students will be introduced to the famous Dijkstra's Algorithm that solves the shortest path problem. This lesson has a strong connection to routing algorithms used on the Internet. This lesson also introduces ideas about how we analyze algorithms: looking for correctness, efficiency and running time. Dijkstra's algorithm is a step-by-step process we can use to find the shortest path between two vertices in a weighted graph. This algorithm enables us to find shortest distances and minimum costs, making it a valuable tool.
|
| Short Description and Walk-through of the experiment |
Directions for the students:
- Step #1: Find the shortest path from A to C for the three graphs below. Underline the path and make a note of the total distance. When you are done, compare with a partner to see if you found the same things.
- Note: We are interested in finding the fastest, cheapest, most efficient way to route information from one place to another.
- Step #2, after you have identified the shortest path from A to C, go back and find the shortest path from A to B, D, and E.
- Note: Compare with a partner to see if you found the same things.
- In your notebook, write down a few ideas for how an algorithm to find the shortest path might work.
- Make a few notes about what is potentially tricky: what things do you want to be sure to remember?
|
| Testbed mapping of the experiment |
The COSMOS testbed uses routing protocols to send signals and connect devices. Dijkstra's Algorithm is used in the Routing protocols (including wireless communication), the mechanisms that allow information to be gathered and distributed. In Routing protocols, routing algorithms such as Dijkstra's Algorithm, is used to determine paths. In addition, students learn about routing databases. Which is used to store information that the algorithm has discovered. Students can find the shortest way to send a message from one node to another using the COSMOS Testbed. Where 1 node will be the router.
|