Instructor: Lubos Thoma
Office: Tyler Hall 214
Class Schedule: TR 2pm--3.15pm, Wales 224
Office hours: TR 12.10 - 1.00 pm, W 2.00 - 3.00 pm, and by appointment
Printable syllabus: postscript pdf
Textbook: F. Buckley, M. Lewinter, A friendly introduction to graph theory, Prentice Hall.
A graph G = (V,E) is a set of vertices V and edges E, each edge consisting of unordered pairs
of vertices. We picture graphs with dots for vertices in any desired arrangement and lines
for edges, connected pairs of vertices in that edge. Graph theory has many applications
in Electrical Engineering and Computer Science. For example, the electrical engineer will
be interested in planar graphs and the computer scientist in algorithms to
properly color graphs. We will see some of these applications, but we must build up some
background knowledge about graphs before we can make sense of such things as the rigidity
of a graph or the crossing number of a graph.
In the course of our study of Graph Theory, we will learn about the following topics as well: set theory, proof techniques, enumeration, and recursive formulas. There is no official prerequisite for this course however, it is recommended that you have been exposed to a variety of math and science courses. All topics will be treated in an introductory manner.
Exams: Exams will draw from material covered in class, that is, any theorems, proofs, example, or homework problem that we actually discuss in class is possible material for the tests. So, the best way to prepare for the exams will be to start with your class notes. There will be two in-class exams and a comprehensive final. The in-class exams will be given on Tuesday October 7 and Thursday November 13, and the final will be on December 16, 8.00 -- 11.00am.
Homework: You learn more by doing, than by watching others give demonstrations. Therefore, homework is very important. When you sit down to do your homework is when you realize whether or not you understood the material from class. You also learn by practice, so do as many of the examples assigned as possible. I will assign homework on a regular basis. Your solutions should be written up with your best effort at explanation and should be neat. These problems will challenge your problem solving abilities. You may work in groups provided you follow the following guidelines: each person must write up each problem in their own words, no copying. Whenever you would like to discuss the class material, have any questions or are stuck on the homework, please visit me in my office either during my office hours or by appointment.
The purpose of the project is that you learn to work with literature
and other sources of information.
The possible topics will be posted shortly. You will be able to
choose from describing a problem or result in graph theory, describing
an application of graph theory in your field, or a program for
a graph theoretical problem. Of course, if you have a topic in mind
on your own that will be very welcome.
You can work alone or in small groups (up to three people). A goal will be to write a short survey paper or create a program concerning the chosen topic.
Draft version due: November 10; final version due December 4.
Your grade will be based on your exam scores, final exam score and homework grades.
Your final score will be computed according to the following percentages.
in-class exams 20% each
Sections covered and homework assignments:
1.Read the book carefully. I chose this book because I believe it gives nice explanations. It may be helpful to read sections before we talk about them in class.
2.Do all of the homework assigned. You should spend an average of 6 hours a week on homework for this class. If you don't gain experience in doing the problems yourself, it will be hard to remember how to do them on a test. It is helpful to start study groups and work together on homework. I do believe that how well you do in this course will depend on how well you study.
3.Attend class to keep current, ask questions, and learn knew topics. Also, attending class allows you to see what is emphasized. Remember the material for the tests will come from what was emphasized.
4.Be sure to keep current of all topics. You will need to study a little almost everyday. If you don't understand something, don't let it wait too long because the concepts in this class build, one upon the next. You don't want the ``snowball effect'' to take over.
5.You may not understand an idea at first. Give it time to sink in. Sometimes you must go over it several times before it begins to make sense. It is not unusual for someone to be stuck on a particular kind of problem and not understand it in class. You may need to have it explained again, later. Please feel free to ask me to do so outside of class.