• Basic information
• Learning outcomes
• Contents
• Assessment
• Workload

Learning outcomes

Upon successful completion of this course, students will be able to:

1. Gain fundamental knowledge and problem solving skills about graph algorithms.

   Contribution to Program Outcomes

   1. Define and manipulate advanced concepts of Computer Engineering
   2. Use advanced knowledge of mathematics, science, and engineering
   3. Acquire scientific knowledge
   4. Continuously develop their knowledge and skills in order to adapt to a rapidly developing technological environment,
   5. Find out new methods to improve his/her knowledge.
   6. Effectively express his/her research ideas and findings both orally and in writing
   7. Demonstrate professional and ethical responsibility.

   Method of assessment

   1. Written exam
   2. Homework assignment
   3. Seminar/presentation
   4. Term paper
2. Gain fundamental knowledge and problem solving skills about approximation algorithms

   Contribution to Program Outcomes

   1. Define and manipulate advanced concepts of Computer Engineering
   2. Use advanced knowledge of mathematics, science, and engineering
   3. Acquire scientific knowledge
   4. Continuously develop their knowledge and skills in order to adapt to a rapidly developing technological environment,
   5. Find out new methods to improve his/her knowledge.
   6. Effectively express his/her research ideas and findings both orally and in writing
   7. Demonstrate professional and ethical responsibility.

   Method of assessment

   1. Written exam
   2. Homework assignment
   3. Seminar/presentation
   4. Term paper
3. Gain fundamental knowledge and problem solving skills about advanced graph theory

   Contribution to Program Outcomes

   1. Define and manipulate advanced concepts of Computer Engineering
   2. Use advanced knowledge of mathematics, science, and engineering
   3. Acquire scientific knowledge
   4. Continuously develop their knowledge and skills in order to adapt to a rapidly developing technological environment,
   5. Find out new methods to improve his/her knowledge.
   6. Effectively express his/her research ideas and findings both orally and in writing
   7. Demonstrate professional and ethical responsibility.
   8. Develop awareness for new professional applications and ability to interpret them

   Method of assessment

   1. Written exam
   2. Homework assignment
   3. Seminar/presentation
   4. Term paper

Contents
Week 1:	Paths, cycles, and trails. Vertex degrees and counting. Directed graphs.
Week 2:	Trees and Distance: Distance in trees and graphs.
Week 3:	Maximum matchings. Hall's matching condition. Matching algorithms and applications: Maximum (weighted) bipartite matching
Week 4:	Stable matchings. Tutte's 1-factor theorem,
Week 5:	f-factors of graphs, Edmond's blossom algorithm
Week 6:	Coloring of Graphs: Vertex colorings and upper bounds. Structure of k-chromatic graphs. Line graphs and edge coloring. Vizing's theorem.
Week 7:	Midterm
Week 8:	Integer programming
Week 9:	Integer programming
Week 10:	Approximation algorithms: Definitions and approximation classes
Week 11:	Inapproximability proof for traveling salesman problem, Steiner tree problem
Week 12:	Metric traveling salesman problem and Christophides algorithm
Week 13:	Minimum makespan scheduling and k-center problem
Week 14:	Paper presentations
Week 15*:	General assessment
Week 16*:	Final Exam
Textbooks and materials:	1. "Introduction to Graph Theory" by Douglas B. West 2. "The Design of Approximation Algorithms" by David P.Williamson and David B. Shmoys
Recommended readings:	1. "Modern Graph Theory" by Bella Bollobas (available in GTU library) 2. "Algorithmic Graph Theory and Perfect Graphs" by Martin Charles Golumbic (available in GTU library) 3. "Graph Theory with Applications" by J.A.Bondy and U.S.R.Murty 4. "Approximation Algorithms" by Vijay V. Vazirani 5. "Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties" by G.Ausiello, P.Crescenzi, G.Gambosi, V.Kann, A.Marchetti-Spaccamela, M.Protasi
	* Between 15th and 16th weeks is there a free week for students to prepare for final exam.

Assessment
Method of assessment	Week number	Weight (%)
Mid-terms:	7	25
Other in-term studies:		0
Project:	14	25
Homework:	3,6,9,12	20
Quiz:		0
Final exam:	16	30
	Total weight:	(%)

Workload
Activity	Duration (Hours per week)	Total number of weeks	Total hours in term
Courses (Face-to-face teaching):	3	14
Own studies outside class:	5	12
Practice, Recitation:	0	0
Homework:	5	4
Term project:	5	8
Term project presentation:	2	1
Quiz:	0	0
Own study for mid-term exam:	9	1
Mid-term:	3	1
Personal studies for final exam:	9	1
Final exam:	3	1
		Total workload:
		Total ECTS credits:	*
	* ECTS credit is calculated by dividing total workload by 25. (1 ECTS = 25 work hours)