Math 118 -- Useful information concerning the Final Exam

 

The final exam will be held on Friday, December 20, 11:00am-1:30pm, Dance Studio and will be comprehensive.   You may not use any notes or books.  You will need a calculator!  Please come to class 10 minutes early, so that you don’t forfeit any of your exam time. At the end of the exam, when you turn in your paper you must sign your name in the list provided and show a picture id.

 

You must take the final examination at the time scheduled by the university; in particular the exam will not be rescheduled because of travel arrangements. It is your responsibility to schedule travel appropriately!   If you are ill, please email or call me in my office (632-8358) BEFORE the test.

 

Please review all material covered in class, in particular you should review the info sheets for the past two midterms:

The following list of concepts and "skills" reflects material covered in class since Midterm #2:

 

· The Traveling Salesman problem is to find a Hamiltonian circuit in a complete weighted graph for which the sum of the weights of the edges is minimal. The sum of the weights of the edges of a circuit is called the weight of the circuit. More generally the Traveling salesman problem asks to find in a weighted (simple) graph a Hamiltonian circuit of least total weight.

 

· A Brute Force Algorithm approach to the Traveling salesman problem is: Check all circuits and select the one with the least total weight! In other words:

- Make a list of all possible Hamiltonian circuits of the graph

- For each Hamiltonian circuit, calculate its total weight by adding the weights of all the edges in the circuit.

- Find the circuit(s) with the least total weight.

 

Pros: Guaranteed to find the most (cost/weight)-efficient circuit! Cons: Enormous amount of work to carry out the algorithm!
(each increase in the number of vertices increases the work by a factor equal to the number of vertices in the graph)

 

· The Nearest Neighbor Algorithm is an approximate algorithm for the Traveling salesman problem in a complete weighted graph:

- Start at the vertex where the circuit is supposed to begin

- From the starting vertex, go to the vertex for which the corresponding edge has the smallest weight (= nearest neighbor).

- Build the circuit, one vertex at a time, by always going from a vertex to the nearest neighbor of that vertex from among the vertices that haven't been visited yet. If there is a tie choose any of the nearest vertices. Keep doing this until all the vertices have been visited.

- Once all the vertices have been visited, from the last vertex, return to the start.

 

Pros: Much less work then the brute force approach! Cons: It doesn't necessarily produce the optimal Hamilton circuit (so it is a compromise answer).

 

· The Greedy Algorithm is also an approximate algorithm for the Traveling salesman problem in a complete weighted graph:

- Begin by choosing the edge of least weight and marking this edge. If there is a tie choose any of the edges with that weight.

- At every stage in the algorithm the next edge should be an unmarked edge of least weight unless it creates a circuit that does not visit every edge of the graph or unless it results in three marked edges coming out of the same vertex in the graph. Again in case of a tie choose any of the edges with that weight.

- The algorithm ends when the marked edges form a Hamiltonian circuit. The (approximate) solution provided by the algorithm is the circuit that starts at one of the vertices, travels along the marked edges in either (appropriate) direction and returns to the starting vertex.

 

Pros: Much less work then the brute force approach! Cons: It doesn't necessarily produce the optimal Hamilton circuit (so it is a compromise answer).

 

For some graphs the Nearest Neighbor Algorithm gives a better approximation than the Greedy Algorithm, for other graphs the Greedy Algorithm may produce a better solution. In some cases both algorithm lead to the same solution.

 

Check this web site for lots of resources on the Traveling Salesman problem

 

A networking problem in graph theory asks to efficiently connect all vertices of a (weighted) graph.

· A subgraph of a graph is any collection of its edges and vertices that themselves form a graph. In other words a subgraph is another graph lying within the original graph.

· Any graph that is connected and contains no circuits is called a tree. A subgraph which is a tree containing all vertices of the given graph is called a spanning tree of the graph.

· The weight of a (weighted) tree is the sum of the weights of its edges.

· A minimum spanning tree of a weighted graph is a spanning tree of minimum weight (among spanning trees).

 

Although no efficient algorithm is known for the Traveling Salesman problem, there are simple and efficient algorithms for finding a minimum spanning tree of a weighted graph.

· One such efficient algorithms for finding a minimum spanning tree of a weighted graph is Prim's Algorithm :

- Start at any vertex of the graph, and mark this one as the starting tree for the algorithm.

- From among those vertices not yet contained in the current tree, find the one that may be connected to a vertex in the current tree by an edge of the lest weight. Connect this vertex to the current tree by the edge of least weight connecting them. In case of a tie choose any one of them.

- Continue the previous step until all vertices are contained in the tree.

 

· A (simple) polygon is a closed connected plane figure consisting of a finite number of line segments each of whose endpoints is the endpoint of exactly one other line segment, and such such that there are no other points where two of the line segments intersect. Each of the line segments forming a polygon is called a side, each point where two sides meet is called a vertex. A polygon with n sides is called a n-gon. The word "polygon" derives from the Greek (poly) meaning "many" and (gonia) meaning "angle."

 

· A polygon is convex if it contains all the line segments connecting any pair of its points. A polygon that is not convex is called concave. Thus, for example, the left pentagon is convex, while the right (indented) pentagon is not! The right one is concave.

 

· If all sides and angles of a convex simple polygon are equivalent, the polygon is called regular. For example, the left pentagon in the above picture is a regular pentagon.

 

· The sum of the (interior) angles of any n-gon is (n-2)180 degrees.

 

· The measure of the angle of a regular n-gon is 180-360/n degree. In particular, an equilateral triangle has angles of 60 degrees, a square has angles of 90 degrees, a regular pentagon has angles of 108 degrees, a regular hexagon has angles of 120 degrees, and so on ...

 

· A (planar) tiling (or tessellation) is a plane-filling arrangement of plane polygonal figures (tiles). A monohedral tiling is a tiling in which all tiles are congruent. If the corners and sides of the polygonal tiles form all the vertices and edges of the tiling and vice versa, then the tiling is called edge-to-edge. Here is part of a tessellation that is not edge-to-edge:

 

· A (planar) regular tiling (or regular tessellation) is a an edge-to-edge monohedral tiling for which the tiles are regular polygons. The only regular tiling are the following three

 

That is the only regular tilings are those with regular hexagons, with squares and with equilateral triangles. There must be at least three polygons at each vertex. (Why?) There cannot be more than six. (Why?) There cannot be five. (Why?). What is the meaning of the pair of numbers beneath each of the above regular tilings?

 

· Edge -to-edge tessellations of the plane by two or more convex regular polygons such that the same polygons in the same order surround each polygon vertex are called semiregular tessellations (tilings), or sometimes Archimedean tessellations (tilings). In regular or semiregular tessellations all vertices have the same type. A vertex is said to have (vertex) type n1, n2, ..., nr if it is surrounded in cyclic (either clockwise, or counterclockwise) order by regular n-gons with n1, n2, ..., nr edges.

 

· There are 8 edge-to-edge semiregular tessellations (tilings)

 

Can you describe the vertex type of each of them ? The vertex type 4,6,12 is special, in that it has two different orientations. Labeling a vertex in the clockwise direction results in a different notation from labeling the vertex in the anti-clockwise direction. For the other tilings, direction makes no difference in the notation. In which of the above semiregular tessellations (tilings) can you find a vertex with clockwise type 4.6.12 and one with counterclockwise type 4.12.6. Notice that we need to use both orientations in order to tile the plane!

 

· There are many edge-to-edge monohedral tilings with non-regular polygons:

- Any triangle can tile the plane.

- Any (convex or concave) quadrilateral can tile the plane.

- There are only 3 classes of convex hexagons that can tile the plane.

- So far, there are 14 types of convex pentagons that can tile the plane. A complete answer is not known yet.

- A convex polygon with seven or more sides cannot tile the plane!

 

· All the above tilings are periodic tilings. If one draws a periodic tiling on a transparency, then it is possible to translate it, without rotating it, in at least two nonparallel directions, until the transparency exactly matches the original tiling everywhere! A nonperiodic tiling is a tiling in which there is no regular repetition of the pattern.

- It was once believed that if a set of one or more tiles could be used to construct a nonperiodic tiling, then the same set of tiles could be used in a different way to construct also a periodic tiling. In 1975 Roger Penrose found an aperiodic tiling of the plane with only two tiles. In its simplest form, it consists of 54 and 72 degree rhombi, with "matching rules" forcing the rhombi to line up against each other only in certain patterns. It can also be formed by tiles in the shape of (deformed) "kites" and "darts". Its main interest is that it has a five-fold symmetry impossible in periodic tilings; it also has been used to explain the structure of certain "quasicrystal" aloys of aluminium. Here is a Penrose (type) tiling :

 

· A polyhedron is a (closed) solid shape whose surface does not intersect itself, with polygonal sides called faces, that are arranged so that every edge of each face coincides entirely with an edge of another bordering face. (Poly means "many" and hedron means "flat surfaces".)

 

· A polyhedron is convex if it contains inside it all the line segments connecting any pair of points inside the polyhedron.

 

· For any convex polyhedron with, say, F faces, E edges and V vertices, Euler's formula says that

F-E+V=2

 

· A convex polyhedron is said to be regular if all its faces are regular polygons of the same size and shape, and moreover the number of edges meeting at a vertex is the same for all vertices.

 

· There are 5 regular polyhedra: the Tetrahedron, the Cube, the Octahedron, the Dodecahedron and the Icosahedron. These solids are also known as the Platonic solids since Plato in one of his books, the Timaeus, described how these solids relate to the four primordial elements and heaven.

- The regular polyehdra naturally fall into three groups, based on their symmetries and duals: The Octahedron and Cube, which are duals of each other, form one group, the Dodecahedron and Icosahedron form another group, while the Tetrahedron forms a third group on its own since it is its own dual.

- We have used in class Euler's formula to establish the following table containing their basic invariants:

PolyhedronFacesEdges
per Face
VerticesEdges at
Vertex
EdgesDual of...
Tetrahedron43436 Tetrahedron
Cube648312 Octahedron
Octahedron836412 Cube
Dodecahedron12520330 Icosahedron
Icosahedron20312530Dodecahedron

- Here are images of the five Platonic solids

 

· A semiregular polyhedron is a convex polyhedron with all its faces regular polygons, all of its vertices of the same type, with at least two different kinds of regular polygons as faces, and with the additional symmetry that up to mirroring the polyhedron looks exactly the same from every vertex. Semiregular solids are also called Archimedean solids.

- There are only 13 Archimedean solids, (not counting two mirror images twice).

- Nine of the Archimedean solids can be obtained by truncation of a Platonic solid, and two further can be obtained by a second truncation. The remaining two solids, the snub cube and snub dodecahedron, are obtained by moving the faces of a cube and dodecahedron outward while giving each face a twist. Can you describe the solid obtained by truncating an Icosahedron ? How many faces, edges, vertices does it have the truncated solid? How about same question for the truncated octahedron?

Good Luck!