CS 571 Topics in Graph Theory & Algorithms Spring 2010 Instructor: Ugur Dogrusoz Office, Hours: EA-528, Tue, Fri PM Classroom, Hours: EA-502, Tue 15:40, Fri 13:40 & 14:40

Announcements	HW 4 grades are now available. Averages for the homework assignments are 80, 71, 64, and 59 / 100, respectively. Presentation guidelines is now available. Here is the LaTeX template to be used for the notes to be prepared. [May 7] Section 1.9: Onur Sumer and Alper Karacelik [May 7] Section 2.3: Muhsin Can Orhan and Seher Acer [May 7] Section 2.4: Emre Varol and Cafer Yildirim [May 14] Section 5.4: Emre Sermutlu and Yilmaz Degirmenci [May 14] Section 5.5: Abdullah Atmaca and Mert Cetinkaya [May 14] Section 6.1 and 6.2: Sefa Kilic [May 14] Section 12.3: Enver Kayaaslan Check here at least once a week!
Description	This is normally a course on special topics in graph theory and algorithms, presenting a detailed study of certain research topics in these areas. This year fundamentals of graph theory will be covered along with certain graph theory applications as review topics if time permits.
Prerequisite	Prior knowledge of fundamentals of computer science and graph theory required. Permission from the instructor required for undergraduates.
Objectives	Become accomplished in formal / mathematical theorem proving using the fundamental techniques of construction, induction, and contradiction (as opposed to traditional/informal proof methods). Learn the fundamentals of graph theory, which is an important mathematical tool in a wide variety of subjects from operational research and chemistry to genetics and linguistics, and from electrical engineering and geography to sociology, architecture, and computer science. Become acquainted with the structure of graphs, and how to determine the relationship between graph invariants (such as order, size, or minimum degree) and a graph property (like being hamiltonian, containing a perfect matching). Relate theory to practice through the study of certain graph theory applications.
Textbooks	Required Graph Theory by Reinhard Diestel, Springer, QA166.D51413 1997, ISBN 0-387-98211-6. electronic copy Recommended Introduction to Graph Theory, 4th Edition by Robin J. Wilson, Logman Group Ltd., ISBN 0-582-24993-7. Graph Theory by Ronald Gould, Benjamin-Cummings, QA166.G66 1988. Supplementary Graphs, Networks and Algorithms by Dieter Jungnickel, Springer, 1999, ISBN 3-540-63760-5. Graph Theory Applications by L.R. Foulds, Springer-Verlag, 1991, ISBN 3-540-97599-3.
Outline & Lecture Notes	Concepts Textbook Foundations - Basics Chapter 1 Matching Chapter 2 Connectivity Chapter 3 Planarity Chapter 4 Coloring Chapter 5 Hamilton Cycles Chapter 10
Grading	Grading Criteria: Component Weight Date/Due Homework 50 - Final 30 in-class (EA 502, May 21, 13:30 - 16:30) Presentation 20 (April 16, May 7 & 14)
Assignments & Exams	Homework Exams HW 4 Solutions HW 3 Solutions HW 2 Solutions HW 1 Solutions