Graph Theory is the study of the mathematical objects known as graphs. Graphs consist simply of ‘vertices’ and ‘edges’ connecting these vertices, and as such have a wide range of applications from the study of social networks to the intricate details of register allocation in programming language compilers. In this course we will be introduced to the fundamental definitions and theorems pertaining graphs and get an appreciation for the very diverse kinds of graphs that are available.
The topic of Graph Theory is also an excellent opportunity for students to develop their mathematical abilities in terms of understanding definitions and developing proofs for theorems, as well as building mathematical intuition. The simple description of most definitions and theorems provides ample opportunity for exploration.
In this course you will
As time permits, the following topics will be covered:
On the website you will find a schedule with links to documents for each class day. In those documents you will find notes for the day’s lesson, and reading assignments. You are expected to do the reading before class.
You are expected to attend every class meeting. You are only allowed to miss 3 classes without excuse. From that point on, every unexcused absence will result in a reduction of your final score by one percentage point. Excused absences should be arranged in advance, and backed by appropriate documentation. Emergencies will be dealt with on an individual basis. There are very few reasons that would qualify as an excuse for an absence. During each class day you will be working on and submitting activity sheets, which will be scored as your class participation grade.
There will be regular written assignments, in addition to numerous practice problems that you are expected to work on. Homework assignments will count for 25% of the final grade.
There will be two midterms, tentatively scheduled for 2/22 and 4/3, and a final during finals week. You have to be here for the exams. If you have conflicts with these days, let me know as soon as possible. Do not plan your vacation before you are aware of the finals schedule.
Your final grade depends on class attendance, homework, midterms and the final, as follows:
| Component | Percent |
|---|---|
| Participation | 10% |
| Assignments | 25% |
| Lowest Midterm | 15% |
| Middle Midterm | 20% |
| Highest Midterm | 30% |
This gives a number up to 100, which is then converted to a letter grade based roughly on the following correspondence:
| Letter grade | Percentage Range |
|---|---|
| A, A- | 90%-100% |
| B+, B, B- | 80%-90% |
| C+, C, C- | 70%-80% |
| D+, D, D- | 60%-70% |
| F | 0%-60% |