Course Information


Course Information
Course Title Code Semester L+U Hour Credits ECTS
GRAPH THEORY AND ALGORITHMS 802600715120 3 + 0 3.0 8.0

Prerequisites None

Language of Instruction Turkish
Course Level Graduate Degree
Course Type Compulsory
Mode of delivery Theory+Application
Course Coordinator
Instructors
Assistants
Goals The aim of this course is to comprehend the graphs that model relationships between objects and the developed algorithms for various problems.
Course Content Principles of Graph theory, trees, basic graph algorithms (BFS /DFS, Dijkstra and BF algorithms), minimum spanning trees, flow networks and algorithms, graph coloring problems, NP-class problems and approximation algorithms (node-coverage, set-coverage, Hamilton path, vertex-cover, set-cover, a Hamiltonian path, traveling-salesman problem)
Learning Outcomes 1) Comprehends the graph structures and uses them for modelling problems
2) Study the theoretical basis of graph theory
3) Gains the ability to use graph algorithms for solving problems such as finding the shortest path
4) Learning of algorithms on the graphs
5) Gains the ability to use graph algorithms for solving problems such as finding the shortest path
6) Learning of using of graph algorithms to solve problems such as matching, maximum flow

Weekly Topics (Content)
Week Topics Teaching and Learning Methods and Techniques Study Materials
1. Week Introduction to graphs Lecture

 Presentation (Including Preparation Time)
2. Week Subgraphs, paths and connected graphs Lecture

 Presentation (Including Preparation Time)
3. Week Euler graphs and Hamiltonian paths Lecture

 Presentation (Including Preparation Time)
4. Week Trees Lecture

 Presentation (Including Preparation Time)
5. Week Algorithms on graphs Lecture

 Presentation (Including Preparation Time)
6. Week Matrix representation Lecture

 Presentation (Including Preparation Time)
7. Week Cut sets Lecture

 Presentation (Including Preparation Time)
8. Week Colouring Lecture

 Presentation (Including Preparation Time)
9. Week Planar and dual graphs Lecture

 Presentation (Including Preparation Time)
10. Week Network flows Lecture

 Presentation (Including Preparation Time)
11. Week Project Lecture

 Project (Including Preparation and presentation Time)
12. Week Project Lecture

 Project (Including Preparation and presentation Time)
13. Week Project Lecture

 Project (Including Preparation and presentation Time)
14. Week Project Lecture

 Project (Including Preparation and presentation Time)

Sources Used in This Course
Recommended Sources
Douglas B. West, Introduction to graphs theory, Pearson 2001
Graph Theory with Algorithms and its Applications: In Applied Science and Technology by Santanu Saha Ray

Relations with Education Attainment Program Course Competencies
Program RequirementsContribution LevelDK1DK2DK3DK4DK5
PY1500000
PY2500000
PY3500000
PY4500000

*DK = Course's Contrubution.
0 1 2 3 4 5
Level of contribution None Very Low Low Fair High Very High
.

ECTS credits and course workload
Event Quantity Duration (Hour) Total Workload (Hour)
Course Duration (Total weeks*Hours per week) 14 3
Homework 4 10
Project (Including Preparation and presentation Time) 2 20
Report (Including Preparation and presentation Time) 2 20
Activity (Web Search, Library Work, Trip, Observation, Interview etc.) 8 3
Midterm Exam 1 2
Time to prepare for Midterm Exam 1 20
Final Exam 1 2
Time to prepare for Final Exam 1 30
Total Workload
Total Workload / 30 (s)
ECTS Credit of the Course
Quick Access Hızlı Erişim Genişlet
Course Information
  • Course Information
  • Weekly Topics (Content)
  • Sources Used in This Course
  • Relations with Education Attainment Program Course Competencies
  • ECTS credits and course workload