Name: ______Date: ______
Geometry Unit 7 Day 1: Intro to Triangles
Name: ______Date: ______
Geometry
Will Those Lengths Make A Triangle?
Real Life Warm Up: 2 boats take off from a dock at a Lake George house. Boat 1 travels 1000 feet. Boat 2 travels 750 feet. 3 scuba divers on boat 1 are going two swim to boat 2. How far will the scuba divers have to travel? Assuming that the boats are not drifting.
Directions: Use your measured sticks to answer the questions below.
1) Inventory your sticks. Create a list of how many you have of each size.
2) Create 2 lists with sketches for each: 1 list of possible triangles & 1 list of impossible triangles. Make sure you identify the type of triangle OR explain why the triangle is impossible.
3) Create a rule that can be used to determine if 3 sticks (side lengths) will form a triangle.
4) Ms. Potenza used to park in the front parking lot every day approximately where the smiley face is on the picture below. What is the shortest route from her car to the front door? Explain how you came up with your answer.
5) Karissa is walking her two dogs on the rail trial. Titus has a 35 foot leash and Zoe has a 50 foot leash. Assuming that the dogs always have their leashes at maximum length, at any given time how far apart are the dogs?
Name: ______Date: ______
Geometry
Practice:Sides of Triangles
1] Phil is cutting a triangular piece of tile. If the triangle is scalene, which set of numbers could represent the lengths of the sides?
1] {2, 4, 7}2] {4, 5, 6}3] {3, 5, 8}4] {5, 5, 8}
2] If two sides of a triangle are 1 and 3, the third side may be
1] 52] 23] 34] 4
3] Given the diagram, find the missing side SE and the missing angle.
4] The plot of land illustrated in the accompanying diagram has a perimeter of 34 yards. Find the length, in yards, of each side of the figure. Could these measures actually represent the measures of the sides of a triangle? Explain your answer.
5]In , BU = 9+3x. UN = 4+2x, BN = 17+5x. The perimeter of the triangle is 120. Find the value of x.
6] Which set of numbers could NOT represent the lengths of the sides of a triangle?
A) {5, 12, 13}B) {2, 3, 4}C) {5, 5, 10}D) {2, 6, 7}
7] In a triangle ABC, where AB = 14 and BC = 9, AC may be equal to?
A) 5B) 13C) 23D) 25
8] Two sides of an isosceles triangle are 4 and 8, what is the third side?
A) 4B) 6C) 8D) 5
9] Two sides of a triangle are 2 and 3, the third side can not be?
A) 1B) 3C) 2D) 4
10]Which is the smallest angle of triangle THB? * Hint: It is across from the smallest side*
11] Given the diagram below, find the missing angles.
12] From the given figure, find mQ.
What is the shortest path?
Dijkstra's algorithm, conceived by Dutch computer scientistEdsger Dijkstra in 1956 and published in 1959,[1][2] is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree. This algorithm is often used in routing and as a subroutine in other graph algorithms.
For a given source vertex (node) in the graph, the algorithm finds the path with lowest cost (i.e. the shortest path) between that vertex and every other vertex. It can also be used for finding costs of shortest paths from a single vertex to a single destination vertex by stopping the algorithm once the shortest path to the destination vertex has been determined. For example, if the vertices of the graph represent cities and edge path costs represent driving distances between pairs of cities connected by a direct road, Dijkstra's algorithm can be used to find the shortest route between one city and all other cities. As a result, the shortest path first is widely used in network routing protocols, most notably IS-IS and OSPF (Open Shortest Path First).
6) If the diagram on the left represents lengths of paths, what is wrong with it?
7) What is the shortest path from #2 to #5?
Finding the Shortest Path
Imagine you are given a road map and asked to find the shortest route between two points on the map. For very simple maps you can often do this just by looking at the map, but if the map looks more like a bunch of spaghetti thrown against the wall you're going to need a better method. This is actually a very important problem; services like Google Maps or MapQuest are entirely concerned with answering this problem. One way of finding the shortest path between two locations is Dijkstra's algorithm (DIKE-stra). In fact we will see that this algorithm does one better, and can actually find the shortest path from the starting location to any other location, not just the desired destination.
Setup
Since roads come in varying lengths we want to work on weighted graphs for this problem. A weighted graph is simply a graph where each edge e is assigned a non-negative value called the weight, w(e), of the edge. A path is a sequence of vertices p = (v1,...,vn) such that vi ~ vi+1. Set ei = (vi,vi+1). The length of a path p is d(p) = &Sigma w(ei). For convenience we will also write w(u,v) to denote the weight of the edge (u,v).
The Algorithm
The idea behind Dijkstra's algorithm is breadth-first search (BFS). This type of search explores vertices by spreading out as new vertices are found. This is akin to starting a fire on the graph. We light the starting vertex, and then the fire spreads to its neighbors while going out at the starting node. The fire then spreads to the unburned neighbors of the burning vertices, and so on until the entire graph is burned. For our purpose we will assume that only one vertex can be burning at a time; that is our fire will always choose to spread to the closest neighbor.
Pick a starting vertex o. We label each vertex v in the graph with a "distance" δ(v) from o. We start out with δ(o) = 0 and guess ∞ for the rest. We start with each vertex in the Unburned state, from which we will remove them as they are burned by the algorithm. Removed nodes are called Burned. For each vertex v we will also keep track of a source vertex called source(v), which is the vertex closest vertex to v along its shortest path to o. The algorithm is
Dijkstra's Algorithm
- For each vertex v in G
- Label v as Unburned
- Set δ(v) = &infin
- Set source(v) as undefined
- Set δ(o) = 0
- While any vertex is Unburned
- Call the Unburned vertex with smallest &delta value u
- Label u as Burned
- For each neighbor n of u
- If δ(u) + w(u,n) < &delta(n)
- Set δ(n) = δ(u) + w(u,n)
- Set source(n)=u
- End
If the above doesn't make a lot of sense to you, don't worry; it's written in a way to be digestible to those familiar with computer programming. The indented lines under a given line are done under the condition that line. Once that condition is no longer met you move on in the algorithm. The first part of the algorithm is an initialization of the graph into the setup described earlier; the rest is concerned with searching through the graph to find distances. To illustrate the algorithm we provide an example below.
In the above picture o is marked by a double circle. The Unburned node with the smallest &delta value is orange. It will be burned at the next step in the algorithm. The yellow vertex is the one that is currently burning. Gray vertices have been labeled as Burned by the algorithm. Neighbors if the burning vertex whose &delta is being updated have their edges marked in orange. This happens when δ(u) + w(u,n) < &delta(n). Edges corresponding to sources are marked in blue. Note that the algorithm will occasionally overwrite the source of a vertex with a closer source. Once all the vertices are Burned the algorithm is burned.
Now that we've run the algorithm how do we find the shortest path from o to another vertex? We simply follow the source edges (blue in the example) from the destination until we reach o, and the distance we have travelled corresponds to the label &delta on the destination. We also know that we have actually found the shortest path (it is possible to have more than one path tied for being the shortest) since our fire has always chosen to take the shortest steps possible when moving to a new location.
You might have already noticed that the blue subgraph doesn't contain any loops, and this is what mathematicians call a tree. In fact this is a very special kind of tree called a minimal spanning tree because it grows from the root o to all of its leaves, the other vertices in G, in the shortest way possible. Minimal spanning trees are very useful. For instance, if a cable company needs to wire all the houses in a neighborhood using as little wire as possible, a minimal spanning tree of the neighborhood provides them with the most efficient way to do so.
Activity 1
Find the shortest path and distance of every vertex from o in the following graph using Dijkstra's algorithm.
Varying Weights
We can also think of more complicated shortest path problems. The most basic of which is to have the weight of an edge be random. Suppose you're supposed to meet your friends at the mall in 15 minutes, but it snowed last night. You know of two routes from your house to the mall. Route B takes 17 minutes and is always cleared while the other is a shortcut using roads that are less likely to be cleared.
If road C has been plowed the short cut takes 12 minutes while if it hasn't been plowed it takes 20 minutes. Suppose there is a 75% chance of road C being plowed. In this case you should really think of C as being weighted with the expected value of how long it takes, that is if you were to attempt the drive many times how long would C take on average. In this case road C to takes 0.25(20)+0.75(12)=14 minutes on average. Since the average time for C is faster than B, you should take C to avoid being late.
Activity 2
Suppose that there is a chance p between 0 and 1 of road C being cleared. Figure out a reasonable means of determining when it is better to take C, and then decide which p you should never chose to use the shortcut.