|
|
| BILB3018 | Graph Theory | 4+0+0 | ECTS:4 | | Year / Semester | Spring Semester | | Level of Course | First Cycle | | Status | Elective | | Department | COMPUTER SCIENCE | | Prerequisites and co-requisites | None | | Mode of Delivery | | | Contact Hours | 14 weeks - 4 hours of lectures per week | | Lecturer | Dr. Öğr. Üyesi Özge TEZEL | | Co-Lecturer | | | Language of instruction | Turkish | | Professional practise ( internship ) | None | | | | The aim of the course: | | In this course, it is aimed to introduce the graph theory to the students and to teach how to use the concepts of graph theory to solve current problems in mathematics and computer science. |
| Learning Outcomes | CTPO | TOA | | Upon successful completion of the course, the students will be able to : | | | | LO - 1 : | Learns the basic concepts of graph theory. | 1,2 | 1,4, | | LO - 2 : | Recognizes the concepts of edge, corner, path and circuit. | 1,2 | 1,4, | | LO - 3 : | Learns to model problems with graphs. | 1,2,12 | 1,4, | | LO - 4 : | Learns to establish relationships with other fields where graph theory is used. | 1,2 | 1,4, | | LO - 5 : | Learns the concept of optimization. | 1,2 | 1,4, | | LO - 6 : | Knows the uses of graph theory in computer science. | 2 | 1,4, | | CTPO : Contribution to programme outcomes, TOA :Type of assessment (1: written exam, 2: Oral exam, 3: Homework assignment, 4: Laboratory exercise/exam, 5: Seminar / presentation, 6: Term paper), LO : Learning Outcome | | |
| History of Graph Theory, Usage Areas of Graph Theory, Paths, Trees and Cycles, Shortest Path Problem, Connectivity, Eulerian Tours, Hamiltonian Cycles, Networks, Minimum and Maximum Network Flow Problems, Graph Decomposition, Combinatorial Applications. |
| |
| Course Syllabus | | Week | Subject | Related Notes / Files | | Week 1 | Introduction to Graph Theory | | | Week 2 | Basic concepts in graph theory | | | Week 3 | Paths, Trees, Cycles | | | Week 4 | Algorithm Analysis and Complexity | | | Week 5 | Shortest Path Problem | | | Week 6 | Minimum Spanning Tree Problem | | | Week 7 | Maximum Flow Problem | | | Week 8 | Minimum Cost Network Flow Problem | | | Week 9 | Midterm Exam | | | Week 10 | Connectivity, Eulerian graphs | | | Week 11 | Hamiltonian graphs | | | Week 12 | Planarity and planar graphs | | | Week 13 | Graph Decomposition and Graph Colouring | | | Week 14 | Combinatorial Applications, Graph Theory Problem, | | | Week 15 | NP-Complete Problems | | | Week 16 | Final Exam | | | |
| 1 | West, D.B. 2000, Introduction to Graph Theory, Second Edition, Pearson, Prentice Hall, | | | |
| 1 | Wilson, R. J. 2010, Introduction to Graph Theory 5th Edition, Pearson,Prentice Hall, | | | |
| Method of Assessment | | Type of assessment | Week No | Date | Duration (hours) | Weight (%) | | Mid-term exam | 9 | | 2 | 50 | | End-of-term exam | 16 | | 2 | 50 | | |
| Student Work Load and its Distribution | | Type of work | Duration (hours pw) | No of weeks / Number of activity | Hours in total per term | | Yüz yüze eğitim | 4 | 14 | 56 | | Sınıf dışı çalışma | 2 | 14 | 28 | | Arasınav için hazırlık | 10 | 1 | 10 | | Arasınav | 2 | 1 | 2 | | Dönem sonu sınavı için hazırlık | 10 | 1 | 10 | | Dönem sonu sınavı | 2 | 1 | 2 | | Total work load | | | 108 |
|