Components of Presentation Summary Group size MUST be 3 to 4 students
Your summary must be a detailed plan on how you will proceed through your presentation and MUST include the following:
• A short introductory description of your topic
• An explanation of how any of the specific requirements (found below in your topic description) will be integrated into your presentation
• An outline of what you will present, in the ORDER you will present them, with the following:
o Who will be presenting that item/portion
o Estimated time that that item/portion will be addressed; remember you should estimate about 5 minutes total per person (so some group members may present several items/portions)
o A rough draft of any Slideshows (go to “Slide Sorter” and print the whole slideshow) or Presentation materials you intend to use
Paper Disclaimer Paper length MUST be 3 to 4 pages
If you intend to work alone and, alas, find no topics below that intrigue you enough to write a brief research report you MAY pick any topic relevant to mathematics that you’d like to learn about and subsequently report on the history, modern practice, examples of, etc. Any topic that you choose outside the scope of those found below MUST be discussed with and cleared by me in OFFICE HOURS prior to your Topic Submission.
Topic Ideas
1. Whenever possible, it is instructive to read about a great discovery from the original source. Euler’s landmark paper in graph theory with his solution to the Königsberg bridge problem was published in 1736. Luckily, the paper was written in a very readable style and the full English translation can be found in the following article: “The Bridges of Konigsberg” by Leonhard Euler (translated by James Newman), Scientific American, vol. 89 (1953), pp. 66-70. Write or present a summary/analysis of Euler’s original paper. Include (1) a description of how Euler originally tackled the Königsberg bridge problem, (2) a discussion of Euler’s general conclusions, and (3) a discussion of Euler’s approach toward finding an Euler circuit/path.
2. In many real0life routing problems, we have to deal with very large graphs ― a graph could have thousands of vertices and tens of thousands of edges. In these cases algorithms such as Fleury’s algorithm (as well as others we will study in later chapters) are done by computer. Unlike humans, computers are not very good at interpreting pictures, so the first step in using computers to perform computations with graphs is to describe the graph in a way the computer can understand it. The two most common ways to do so are by means of matrices. In this project you are asked to present/write a short exposition describing the use of matrices to represent a graph. Explain (1) what is a matrix, (2) what is the adjacency matrix of a graph, and (3) what is the incidence matrix of a graph. Illustrate some of the graph concepts from our discussions on Euler circuits/paths & Fleury’s algorithm in matrix terms. Include plenty of examples.
3. A weighted graph is a graph in which the edges are assigned positive numbers called weights. Finding optimal routes that cover all the edges of a weighted graph is known as the Chinese postman problem. Prepare a presentation/paper on the Chinese postman problem that includes (1) several examples to illustrate the Chinese postman problem and how they differ from the corresponding (unweighted) Euler circuit problems, (2) descriptions of some real-life applications of the Chinese postman problem, (3) a discussion on how to solve the simplest cases of the Chinese postman problem when the graph has zero or two odd vertices (consider using techniques discussed in class), and (4) a rough outline how one might attempt to solve a Chinese postman problem with four odd vertices.
4. The nearest-insertion algorithm is another approximate algorithm used for tackling TSPs (Traveling Salesman Problems). The basic idea of the algorithm is to start with a subcircuit (a circuit containing some, but not all vertices) and enlarge it, one step at a time, by adding an extra vertex ― the one that is closest to some vertex in the cirtcuit. By the time we have added all of the vertices, we have a full-fledged Hamilton circuit. You should prepare a presentation/paper on the nearest-insertion algorithm that includes (1) a full, detailed description of the algorithm, (2) at least two carefully worked-out examples, and (3) a comparison of nearest-insertion with the nearest-neighbor algorithm.
5. DNA is the basic molecule of life ― it encodes the genetic information that characterizes all living organisms. In 1994, Leonard Adleman was able to encode a graph representing seven cities into a set of DNA segments and use chemical reactions of the DNA fragments to uncover the existence of a Hamilton path in the graph. He was able to use the biochemistry of DNA to solve a graph theory problem. Prepare a presentation/paper telling the story of Adleman’s landmark discovery that discusses (1) how he encoded the graph into DNA, (2) how he extracted the mathematical solution from the chemical solution, (3) other problems that might be solved using DNA computing, and (4) the implications of Adleman’s discovery for the future of computing.
6. An individual ant is, by most standards, a dumb little creature, but collectively an entire ant colony can perform surprising feats of teamwork and self-organize to solve remarkably complex problems (finding the shortest route to a food source, optimizing foraging strategies, managing a smooth and steady traffic flow in congested ant highways). The ability of ants and other social insects to perform sophisticated group tasks goes by the name of swarm intelligence. Since ants don’t talk to each other and don’t have managers/supervisors telling them what to do, swarm intelligence is a decentralized, spontaneous type of intelligence that has many potential applications at the human scale. In recent years, computer scientists have been able to approach many difficult optimization problems (including TSPs) using ant colony optimization software. Prepare a presentation/paper that (1) describes the concept of swarm intelligence, (2) describes some recent developments in ant colony optimization methods, and (3) describes the use of virtual ant algorithms for solving TSPs.
