First posted on Monday, April 28th.
Updated Tuesday, April 29th.
------------------
Types of Questions
------------------
The math department mandates that a large chunk of our final exam will be
multiple choice questions. With 7,000-9,000 undergraduates taking final exams
in our department, we wouldn't be able to correct the exams and hand in grades
unless machines did most of the work.
You've already had a lot of Matching and True/False questions, and to some
extent I can use those types of questions on the final -- "Mark (A) if the
following statement is true, (B) if is is false."
Even so, you'll have a lot of multiple choice questions on the final exam. To
help you get used to that, I'm going to put at least one page of multiple
choice questions on this test.
Chapter 5
---------
* You should know the following terms, most of which are important for chpaters
6 and 7 as well: graph, vertex, edge, adjacent edjes, adjacent vertices,
bridge, connected (and disconnected), degree, path, circuit, Euler path, Euler
circuit, graph model, loop, multiple edges, eulerizing a graph,
semi-eulerization.
* You should be able to identify features of a graph, such as a loop, multiple
edges, a bridge, a vertex of a certain degree, and so on.
* You might be asked to make a graph model of a geographic area -- problems
such as 19-22 in the Chapter 5 exercises.
* You should know Euler's Theorems, particularly the first two. You should be
able to identify when a graph has an Euler Circuit or Path. On a simple graph
you may be asked to find such a circuit or path.
* Using Fleury's Algorithm you should be able to find an Euler Circuit or
Path. (This is a little different than the last point -- I might say, "Find
_any_ Euler Circuit" or I might say, "Find an Euler Circuit starting at A using
Fleury's Algorithm." If I say the second thing you really do need to use
Fleury's Algorithm.)
* You should know what both Eulerization and Semi-Eulerization mean, and be
able to do it. (I won't give you terribly large graphs for these problems, I
promise.)
Chapter 6
---------
* You should know the following terms: complete graph, weighted graph, Hamilton
Circuit, Hamilton Path, Traveling Salesman Problem (TSP).
* You should know how many Hamilton Circuits a complete graph with N vertices
has.
* You should know the following algorithms for finding a Hamilton Circuit:
Brute-Force, Nearest Neighbor, Repetetive Nearest Neighbor, Cheapest Link. You
should know which ones are efficient and not-efficient (basically, they're all
efficient except the Brute Force method) although I won't ask for a technical
definition of "efficient."
Chapter 7
---------
* You should know the following terms: tree, spanning subgraph (and spanning
tree in particular), minimum spanning tree (MST), Steiner Point, Steiner Tree.
* You should know what the four properties of a tree are. Pay special
attention to the last two, because they're tricky -- be careful about that word
"connected."
* You should be able to find a spanning tree of a graph. If it's a weighted
graph, you should be able to find the minimum spanning tree using Kruskal's
Algorithm.
* You should know what the shortest distance between 3 point is -- either the
MST or the corners linked to an interior Steiner Point, depending on how big
the angles are. In particular, you should know when you can or can't fit a
Steiner Point inside. (It has to do with 120.)
* You may be presented with a few simple examples of shortest networks with
more than three points. As discussed in class, there is no general solution,
but you should know what facts we do have. For example, if we can't add new
interior points, then the the shortest network is the minimum spanning tree
(MST). If we _can_ add new points, it's either the MST or a network with new
interior points, each of which must be a Steiner Point. (In other words, it's
either the MST or a Steiner Tree.)
* You should know why the number 13.4% is important.
Happy Studying!