Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Theory of Combinatorial Algorithms
Prof. Emo Welzl and Prof. Bernd Gärtner
Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Prof. Emo Welzl and Prof. Bernd Gärtner
 |
|
 |
|
|
|
|
|
|
 |
||||||||
IFW B48.1/ Tel: (01) 632-0858
MARCH 4th, 9-11 AM, Main Buliding E5
Information about the exam.
I reserved the room IFW A32 for Tuesdays 4:15PM. The first session will take place Nov 5.
| Problems | Maximum points | Comments of the grader |
| HW 1. | 1; 1; 1; 1; 1; 1; 1+1; 1+1+1; 2; | No Comment |
| HW 2. | 4; 4; 1+3; 2+2; 4; 8; | No Comment |
| HW 3. | 2+2; 2+2; 2+2; 4; 4; 4; 2+6; | No Comment |
| HW 4. | 4; 4; 2+2+2; 2+2+2; 4; 2+6; | No Comment |
| HW 5. | 1+3; 2+2+2; 4; 8; 4; 4; | Comments 5. |
| HW 6. | 4; 4; 4; 8; 4; 4; | Comments 6. |
| HW 7. | 2+2; 2+2; 1+3; 4; 4; 4; - | No Comment |
| HW 8. | 4; 2+2; 1+3; 8; 4; 8; | No Comment |
| HW 9. | 4; 4; 4; 4; 4; 4; 4; | No Comment |
| HW 10. | 4; 4; 4; 8; 4; 4; | Comments 10. |
| HW 11. | 4; 4; 8; 4; 4; 4; | Comments 11. |
| HW 12. | 4; 4; 4; 4; 4; 8; 6; | No Comment |
| HW 13. | 4; 4; 4; 4; | No Comment |
| HW 14. | 4; 4; 4; 4; 4; 4; 4; | No Comment |
This course is an introduction to the theory of graphs intended for students in mathematics and computer science/engineering students with an interest in theory. We start from basic definitions and examples, but hope to move on quickly and cover a broad range of topics. Some applications and relations to Computer Science will also be discussed. Emphasis will be given to reading, understanding and developing proofs. There is no prerequisite, other than basic mathematics introduced in the Grundstudium. Possible topics include: degrees, paths, trees, cycles, Eulerian circuits, bipartite graphs, extremality, matchings, connectivity, network flows, vertex and edge colorings, Hamiltonian cycles and planarity.
In lecture we will follow the textbook "Introduction to Graph Theory" by Doug West. In recitation we will sample from the great number of excellent exercises related to the topic of the current lecture. I do not require, but highly recommend that you try to solve all the homework exercises and if you do so, write them up. Writing up teaches you to precisely formulate your (maybe vague) ideas and communicate them such that others (in this case me) understand them. This ability is beneficial not just in mathematics but in (almost) any discipline. Whatever you write up I will read and comment on. Another reason to struggle with the homework problems is to prepare yourself for the final exam. Grading will solely be based on this two-hour, written exam.
Lecture 1.
Lecture 2.
Lecture 3.
Lecture 4.
Lecture 5.
Lecture 6.
Lecture 7.
Lecture 8.
Lecture 9.
Lecture 10.
Lecture 11.
Other (more advanced) texts:
|
| Last Modified: January 14th, 2003, by Tibor Szabó. |  |
