ECTS @ IUE ECTS @ IUE ECTS @ IUE ECTS @ IUE ECTS @ IUE ECTS @ IUE ECTS @ IUE

ucuncuduzeymenu.asp

Syllabus ( CSE 623 )


   Basic information
Course title: Graph Algorithms and Applications
Course code: CSE 623
Lecturer: Assoc. Prof. Dr. Didem GÖZÜPEK
ECTS credits: 7.5
GTU credits: 3 (3+0+0)
Year, Semester: 1/2, Fall and Spring
Level of course: Second Cycle (Master's)
Type of course: Area Elective
Language of instruction: English
Mode of delivery: Face to face
Pre- and co-requisites: none
Professional practice: No
Purpose of the course: To introduce the students the basic concepts of graph algorithms and approximation algorithms
   Learning outcomes Up

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.

    Type 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.

    Type 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

    Type of Assessment

    1. Written exam
    2. Homework assignment
    3. Seminar/presentation
    4. Term paper
   Contents Up
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 Up
Type 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 Up
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)
-->