Graph Theory and Algorithms
Computer Engineering (Ph.D.)
Institute of Natural and Applied Sciences
Third Cycle (Doctorate Degree)
| Course Unit Title | Course Unit Code | Type of Course Unit | Level of Course Unit | Year of Study | Semester | ECTS Credits |
|---|---|---|---|---|---|---|
| Graph Theory and Algorithms | BLM602 | Elective | Doctorate degree | 1 | Spring | 8 |
Name of Lecturer(s)
Assistant Prof. Dr. Alpaslan Burak İNNER
Learning Outcomes of the Course Unit
1) To be able to use mathematical tools for algorithm analysis (such as logic and proof methods)
2) Graf veri yapıları ve algoritmalarını mühendislik problemlerine uygulayabilmek
3) To be able to use mathematical tools for algorithm analysis (such as logic and proof methods)
4) To be able to use graph presentations and related data structures
5) To be able to develop graph algorithms for the solutions of graph problems such as Yapay zeka, Fark Denklemleri, Öğrenebilen Algoritmalar vs.
Program Competencies-Learning Outcomes Relation
| Program Competencies | |||||||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | ||
| Learning Outcomes | |||||||||||||
| 1 | Low | No relation | High | No relation | No relation | No relation | No relation | No relation | No relation | No relation | No relation | No relation | |
| 2 | Middle | No relation | High | No relation | No relation | No relation | No relation | No relation | No relation | No relation | No relation | No relation | |
| 3 | No relation | Middle | High | No relation | No relation | No relation | No relation | No relation | No relation | Middle | Middle | No relation | |
| 4 | Low | High | High | No relation | No relation | High | No relation | Middle | Middle | Middle | Middle | Low | |
| 5 | Middle | High | High | Middle | Middle | Middle | Middle | Middle | Middle | Middle | Middle | Middle | |
Mode of Delivery
Face to Face
Prerequisites and Co-Requisites
None
Recommended Optional Programme Components
Not Required
Course Contents
This course discusses graph representations and graphs algorithms for searching (depth-first search, breadth-first search), topological sorting, graph components and strongly connected components, minimal spanning trees, single-source and all-pairs shortest paths, maximal bipartite matching, Euler graphs, and graph coloring. The basic principles and complexities of all presented algorithms are discussed. Also the implementation of these algorithms are discussed.
Weekly Schedule
1) Data types and Abstract Data Types and C++ Classes2) Fundamentals (Logic, sets, graph theory, proof methods)
3) Graphs and their representations. Time and space complexity ?Asymptotic analysis: Big Oh, Little oh, Theta ?Worst case and average case analysis
4) Topological Sorting, State-Space Search and Graphs,
5) Artificial Intelligence and Graphs, A* Algorithm
6) Depth-first search and its applications
7) Directed Graphs, breadth-first search
8) Dijkstra`s algorithm. All-pairs shortest paths.
9) Minimum Spanning Trees (MST).
10) Shortest paths and MST
11) Graph Colorings. Cliques.
12) Matchings in bipartite graphs. Maximal matchings. Vertex cover.
13) Combinatorial problems and algorithms
14) Graph Searching Problem and related algorithmic solutions.
15) Hard problems: Traveling salesman problem, Longest path, Hamilton cycle.
16) Final
Recommended or Required Reading
Planned Learning Activities and Teaching Methods
1) Lecture
2) Discussion
3) Drill and Practice
4) Simulation
5) Problem Solving
Assessment Methods and Criteria
Contribution of Semester Studies to Course Grade |
50% |
|||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
||||||||||||
Contribution of Final Examination to Course Grade |
50% |
|||||||||||
Total | 100% | |||||||||||
Language of Instruction
Turkish
Work Placement(s)
Not Required