🔗 project 1 | 🔗 project 2 | 🔗 SYLLABUS | MARKS |
http://graphonline.ru/en/ |
|
|
|
Session/Timeline | Tutorial/Oral exam | Idea/Concept | Video |
none | none | 🔗 Decision making/motivation | |
| | | |
1 | 🔗 Tutorial 1 | Complexity | |
→ 🔗 Big oh notation | 🔗 |
→ 🔗 Termination and correctness | 🔗 |
| |
2 | 🔗 Tutorial 2 | Graph theory’s basics | |
→ 🔗 Un/directed graph | |
→ Degree | |
→ Path/cycle | |
→ Complete graph | 🔗 |
→ Subgraph | |
→ 🔗 Tree | |
3 | 🔗 Tutorial 3 | → 🔗 Eulerian circuit | 🔗 |
→ Hamiltonian circuit | 🔗 |
→ 🔗 Graph coloring | 🔗 |
| |
4 | 🔗 Tutorial 4 | Spanning tree | |
→ 🔗 Kruskal’s algorithm | 🔗 |
→ Prim’s algorithm | 🔗 |
End of project 1 | how to solve : | 🔗 |
|
5 & 6 | 🔗 Tutorial 5 | Shortest path problem | |
→ 🔗 Linear program | 🔗 |
→ Dynamic program | 🔗 |
→ 🔗 Dijkstra’s algorithm | 🔗 |
→ 🔗 DAG algorithm | 🔗 |
→ 🔗 Bellman-Ford’s algorithm | 🔗 |
→ 🔗 Floyd-Warshall’s algorithm | 🔗 |
how to solve : | 🔗 |
7 & 8 | 🔗 Tutorial 6 | Flow problem | |
→ 🔗 Max flow problem | 🔗 |
→ Flows and cut | ˄ |
→ Augmenting path | ˄ |
→ Min cut problem | ˄ |
→ 🔗 Ford-Fulkerson’s algorithm | 🔗 |
how to solve : | 🔗 |
9 & 10 | 🔗 Tutorial 7 | Transportation problem | |
→ 🔗 Definition and special cases | 🔗 |
→ Initial solution | 🔗 |
→ 🔗 Stepping stone algorithm | |
→ Degeneracy | |
End of project 2 | how to solve : | 🔗 |
|
|
|
REFERENCES |
Introduction to Algorithms: Cormen, T et Leiserson, C |
The Algorithm Design Manual: Steven S. Skiena |
Electric Power System Applications of Optimization, Second Edition: James A. Momoh |