Tuesday, January 30, 2018
Graph Theory in Application
We've talked about several applications of graph theory in our first unit this semester, including the Traveling Salesperson Problem, applications to networks, and other applications. There are many other ways that graph theory can be applied. The links below all apply graph theory in other areas. Read one of the articles below and write a response to the article. Tell me which article you chose and give a brief summary of the article, explaining how graph theory was applied. Finally, tell me what you thought of the way they applied graph theory in the article. Were you surprised that graph theory applied in this situation?
Upcoming Due Dates and Exam 1
You have now been introduced to all of the Graph Theory concepts for this unit. We will be spending some more time on these concepts this week to make sure you've got everything straight. There are a lot of new definitions in this unit. Definitions are important; without understanding the definitions, it's impossible to answer questions about them! You can expect to see some definitions on the exam.
There are several due dates coming up. Here's a reminder:
Graph Theory Worksheet 2 - Due in class Tuesday, Jan 30
Graph Theory WebWork 2 - Due Tuesday, Jan 30
Graph Theory Worksheet 3 - Due in class Thursday, Feb 1
Graph Theory WebWork 3 - Due Feb 2
Graph Theory Worksheet 4 - Due in class Tuesday, Feb 6
Graph Theory WebWork 4 - Due Friday, Feb 9 (but I strongly suggest you complete this assignment before the exam!)
Graph Theory Exam 1 - In class on Tuesday, Feb 6.
An exam review is posted in the Handouts folder linked on the right of the blog. You should print this out and bring it to class with you on Thursday.
It's natural to have some anxiety before an exam. To help make sure you are well-prepared for this exam, you should first work on learning all of the definitions from this unit. Then, practice with problems to make sure you can apply what you've learned. You have a wealth of problems with which to practice from the WebWork, worksheets, and from the reviews we will use in class this week. Identify the problems you marked wrong when you graded your worksheets and make sure you know how to correct the problem now. It helps to get yourself in the right mindset before an exam.
Ideas for response:
- You can find ideas of things to think about the night before an exam here. Have you ever used any of these to help prepare yourself for an exam? Do you have other tricks to help get yourself in the right frame of mind before an exam?
- What do you usually do to prepare for an exam? Do you do anything differently to prepare for a math exam versus an exam in a humanities course?
- Carol Dweck studies mindsets. Students with a growth mindset have an attitude of "I can't do this. . .yet", while students with a fixed mindset have an attitude of "I can't do this. . .ever". Watch the short video Mindsets: Fixed vs. Growth and report on what you learned. Do you think you have a fixed mindset or a growth mindset?
Monday, January 22, 2018
Graph Isomorphisms and Making Mistakes
I've received several questions about problems 12 and 13 in the first WebWork graph theory assignment. These questions give you a graph and ask you to determine which of the three graphs below is the same graph, represented differently. It then asks you to give the one-to-one correspondence that identifies the two graphs. This correspondence is called a graph isomorphism. These problems can be tricky, and require some thought and creativity to find the right correspondence. However, it's a valuable exercise to struggle with problems sometimes, and it makes finding the right solution all the more sweet!
Imagine if you had to do this same thing, but for a graph with thousands of vertices! It might be a daunting task to imagine. Of course, you wouldn't want to have to try to find this isomorphism by hand, but even asking a computer to do this would be difficult. In fact, recent research has been trying to determine if there is a way to determine if two graphs are isomorphic "quickly". A computer scientist, Laszlo Babai, from the University of Chicago, announced in November 2015 that he had found an algorithm to determine if two graphs were isomorphic in quasipolynomial time. But, in January 2017, another mathematician, Harald Helfgott, posted that he had found an error in the proof. It can be frustrating for you to find that you've answered a problem incorrectly in MAT110(E); imagine if you had announced to all of your colleagues that you had solved a problem, only to find that your solution was incorrect. This happens to professional mathematicians too. (I, too, have submitted a paper to a mathematics journal claiming to have proven something, only to find that there was a subtle error in my reasoning. I've still been unable to correct my error!) Even when we get the answer wrong, there is value in the struggle that it takes to work with a problem. Maybe those skills that you learned to work with this problem will help you with a problem in the future. Maybe you'll remember how to correct it just a little bit better because you had to struggle to find the right answer. Don't focus too much on worrying about making mistakes - everyone will make them - instead, make sure you learn from your mistakes and are ready to apply what you learned in the struggle to the next problem.
Don't worry about Babai - he's corrected the problem in his algorithm.
You can read more about graph isomorphisms and Laszlo Babai's algorithm at the American Mathematical Society's blog on math and the blog Computational Complexity.
In the comments, tell me about a time you struggled with a problem. What did you do to solve the problem? Did the struggle help the next time you had a similar problem?
Imagine if you had to do this same thing, but for a graph with thousands of vertices! It might be a daunting task to imagine. Of course, you wouldn't want to have to try to find this isomorphism by hand, but even asking a computer to do this would be difficult. In fact, recent research has been trying to determine if there is a way to determine if two graphs are isomorphic "quickly". A computer scientist, Laszlo Babai, from the University of Chicago, announced in November 2015 that he had found an algorithm to determine if two graphs were isomorphic in quasipolynomial time. But, in January 2017, another mathematician, Harald Helfgott, posted that he had found an error in the proof. It can be frustrating for you to find that you've answered a problem incorrectly in MAT110(E); imagine if you had announced to all of your colleagues that you had solved a problem, only to find that your solution was incorrect. This happens to professional mathematicians too. (I, too, have submitted a paper to a mathematics journal claiming to have proven something, only to find that there was a subtle error in my reasoning. I've still been unable to correct my error!) Even when we get the answer wrong, there is value in the struggle that it takes to work with a problem. Maybe those skills that you learned to work with this problem will help you with a problem in the future. Maybe you'll remember how to correct it just a little bit better because you had to struggle to find the right answer. Don't focus too much on worrying about making mistakes - everyone will make them - instead, make sure you learn from your mistakes and are ready to apply what you learned in the struggle to the next problem.
Don't worry about Babai - he's corrected the problem in his algorithm.
You can read more about graph isomorphisms and Laszlo Babai's algorithm at the American Mathematical Society's blog on math and the blog Computational Complexity.
In the comments, tell me about a time you struggled with a problem. What did you do to solve the problem? Did the struggle help the next time you had a similar problem?
Week 2 - Hamiltonian Circuits and Paths
This week we will be finishing up with Euler circuits and moving into Hamiltonian Paths and Circuits and weighted graphs. A weighted graph is just a graph with numbers (weights) on the edges. Our goal will be to use weighted graphs and Hamiltonian circuits to solve the Traveling Salesman Problem. We will see three algorithms for solving this: The Nearest Neighbor Algorithm, The Side-Sorted (or Best Edge) Algorithm, and the Repetitive Nearest Neighbor Algorithm. We will also discuss how to solve this using Brute Force. You will need to memorize each of these algorithms.
Don't forget to keep up with the homework on WebWork and the associated worksheets. Once you complete a worksheet, you should take it to the CAS to grade and correct your work. Make sure that you mark your mistakes and correct it with a different color writing utensil. I will collect all the graded/corrected worksheets in class on Tuesdays.
Challenge Problem: (Due Tuesday, January 30) The picture below is the floor plan for the Second Level of the Nelson-Atkins Museum in Kansas City. Doorways are represented by a break in the wall. Is it possible to start in one room on this floor, travel through every doorway, closing the door behind you, and return to where you started? Use graph theory to answer this question. Your solution should include a graph, explain how the graph is related to the floor plan, and explain how you used graph theory to determine if such a path exists. If the path exists, give it; otherwise explain why it is not possible. (https://www.nelson-atkins.org/museum-map/)
How to Email Your Professor
Every semester, I receive an email that looks something like the following:
hey mrs. mccune. did i miss anything important in class today? also, i don't know how to do number 2.
There are several issues with this email. First, you should address your instructors as Professor or Dr, unless they have asked to be addressed differently. (I am Dr. McCune.) Second, if you must miss class, please acknowledge that you are responsible for the material covered in your absence. I am happy to give a brief recap of what you missed, but please remember to first consult the syllabus and the notes before composing your email.
If you need help with a specific homework problem, please be clear about which problem you need help with. For example, "I need help with number two on the webwork Graph Theory set 1". You should tell me what you've tried so far and specifically what part of the problem is giving you trouble. It is often useful to include an attachment with a picture of your work so that I can best point you in the right direction to solve the problem.
Finally, be sure to sign your email with your name, course number, and section. It is especially difficult to respond to an email if I don't know who the sender is.
Wikihow has a nice summary of how to email a professor, which you should apply when emailing any of your professors on campus.
How to Email a Professor
hey mrs. mccune. did i miss anything important in class today? also, i don't know how to do number 2.
There are several issues with this email. First, you should address your instructors as Professor or Dr, unless they have asked to be addressed differently. (I am Dr. McCune.) Second, if you must miss class, please acknowledge that you are responsible for the material covered in your absence. I am happy to give a brief recap of what you missed, but please remember to first consult the syllabus and the notes before composing your email.
If you need help with a specific homework problem, please be clear about which problem you need help with. For example, "I need help with number two on the webwork Graph Theory set 1". You should tell me what you've tried so far and specifically what part of the problem is giving you trouble. It is often useful to include an attachment with a picture of your work so that I can best point you in the right direction to solve the problem.
Finally, be sure to sign your email with your name, course number, and section. It is especially difficult to respond to an email if I don't know who the sender is.
Wikihow has a nice summary of how to email a professor, which you should apply when emailing any of your professors on campus.
How to Email a Professor
Monday, January 15, 2018
Welcome To MAT110(E)!
Welcome to MAT110/MAT110E! You should be enrolled in MAT110 if you have a 22 or higher on the ACT or passed the math placement exam (MPE) with a 70 or higher. Otherwise, you should be enrolled in MAT110E and MAT110E Lab. Keep in mind that if you fail the lab section, you will fail this MAT110E lecture section as well, regardless of your exam and homework scores in MAT110E. Hence, it is imperative that you attend and actively participate in your MAT110E lab section. In particular, make sure that you complete each week's homework bank in your lab sections!
Our semester will be broken into three major units: Graph Theory, Financial Math, and Probability and Statistics. We will have a fourth shorter unit over Voting Theory at the end of the semester. I hope that you will enjoy learning a little bit about each of these topics and how they are used in your everyday life and the world around you. I'm looking forward to a great semester!
We will be kicking off the semester this week with an introduction to graph theory. A graph is a collection of vertices (think dots) and edges (think lines) between the vertices. We can use graphs to study many things in the world around us. For example, a graph can represent streets and intersections from a map (see The Traveling Salesperson Problem), computer networks, social networks, or even be used to study DNA (see A Graph Theoretical Approach to DNA Fragment Assembly). By the end of this week, you should know what a graph is and be able to describe several properties of a graph.
A little bit about me: I am in my sixth year as an Assistant Professor of mathematics here at Missouri Western State University. Before coming to MWSU, I spent a year as a visiting assistant professor at Ashland University. I received my PhD from the University of Nebraska-Lincoln in 2011. (Go Big Red!) My husband is also a mathematician at William Jewell College. We have a 3.5 year old daughter and a 1.5 year old son who are both a bundle of energy.
Please ask for help as soon as you are having trouble with this class. You can visit me in my office (Agenstein 135K). Peer tutoring is also available (for free) through the Center for Academic Support.
Challenge Problem #1: (Due at the start of class on Tuesday, January 23) Sketch several examples of graphs. Determine the degree of the vertices in each graph. When you add the degrees of all the vertices, you will always get an even number. Why is that?
Our semester will be broken into three major units: Graph Theory, Financial Math, and Probability and Statistics. We will have a fourth shorter unit over Voting Theory at the end of the semester. I hope that you will enjoy learning a little bit about each of these topics and how they are used in your everyday life and the world around you. I'm looking forward to a great semester!
We will be kicking off the semester this week with an introduction to graph theory. A graph is a collection of vertices (think dots) and edges (think lines) between the vertices. We can use graphs to study many things in the world around us. For example, a graph can represent streets and intersections from a map (see The Traveling Salesperson Problem), computer networks, social networks, or even be used to study DNA (see A Graph Theoretical Approach to DNA Fragment Assembly). By the end of this week, you should know what a graph is and be able to describe several properties of a graph.
A little bit about me: I am in my sixth year as an Assistant Professor of mathematics here at Missouri Western State University. Before coming to MWSU, I spent a year as a visiting assistant professor at Ashland University. I received my PhD from the University of Nebraska-Lincoln in 2011. (Go Big Red!) My husband is also a mathematician at William Jewell College. We have a 3.5 year old daughter and a 1.5 year old son who are both a bundle of energy.
Please ask for help as soon as you are having trouble with this class. You can visit me in my office (Agenstein 135K). Peer tutoring is also available (for free) through the Center for Academic Support.
Challenge Problem #1: (Due at the start of class on Tuesday, January 23) Sketch several examples of graphs. Determine the degree of the vertices in each graph. When you add the degrees of all the vertices, you will always get an even number. Why is that?
Subscribe to:
Posts (Atom)