Name:
Period:
Date:

Exploring Computer Science

Assignment: Minimum Spanning Tree

In this activity you will:

  • Find how computers are used to find the best solutions for real-life problems
  • Complete the worksheet activity The Muddy City Problem
  • Upload your completed worksheet; make sure you include a copy of the map with the route you chose

Instructions:

  • read each item below
  • do what is requested
  • if you are asked to write an answer, type that answer in this document, using complete sentences
  1. Go to Mr. Gonzalez Website and under this period, download and watch the video: Networks--Minimum Spanning Tree
  1. Now work on the next worksheet, and Upload your completed worksheet; make sure you include a copy of the map with the route you chose.

Worksheet Activity: The Muddy City Problem

Once upon a time there was a city that had no roads. Getting around the city was particularly difficult after rain storms because the ground became very muddy – cars got stuck in the mud and people got their boots dirty. The mayor of the city decided that some of the streets must be paved, but didn’t want to spend more money than necessary because the city also wanted to build a swimming pool. The mayor therefore specified two conditions:

  • Enough streets must be paved so that it is possible for everyone to travel from their house to anyone else’s house only along paved roads.
  • The paving should cost as little as possible. Use as few stones as possible.

Here is the layout of the city. The number of paving stones between each house represents the cost of paving that route. Find the best route that connects all the houses, but uses as few counters (paving stones) as possible.

  1. Copy and paste the picture below into Paint Brush, using the fill with color bucket
  2. Color the paving stores of the way you selected (decorate, color as desired)
  3. Once you are satisfied with your work copy and paste the picture back to this document, and continue.

PASTE YOUR COMPLETED PICTURE HERE:

Activity: Answer the following questions, USING COMPLETE SENTNECES.

  1. What is your route? (REMMBER: you want to have the minimum numbers of stornes)
  1. What strategies did you use to logically solve the problem?
  1. How many stones were required in your plan?
  1. How many roads were there in all?

Turning in your work-

  1. First, save your answer document with the following format.

#-ECS-Minimum Spanning Tree --Last,First (use your period for #)

  1. Start a web browser and go the the following address:

DropItTo.me/Mr_Gonzalez

  1. Enter the password as requested.

The password is magnet

  1. Choose your file and click Upload each file.