Lecturer: Peter Náther. Office: I-42 Phone: 0915700078 e-mail: nather@ii.fmph.uniba.sk
Teaching Assistant: Ján Pastorek, e-mail: jan.pastorek@fmph.uniba.sk
Consultations: by agreement
Textbooks:
- A. Stanoyevitch: Discrete Structures with Contemporary Applications
- Ralph Grimaldi: Discrete and Combinatorial Mathematics
- Douglas West: Introduction to Graph Theory
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms, 3rd Edition. MIT Press (2009)
Information about the course, meetings, homework, tests, and projects will be in MOODLE.
Course Description: Graphs, Graph Algorithms, and Optimization is a course where we will cover basic concepts from Graph Theory and then focus on the most well-known graph algorithms, such as graph traversals, finding the optimal spanning tree of a graph, finding the shortest path, and flows and cuts in graphs. Besides describing and analyzing these algorithms, we will also deal with their computational complexity, and some of them will be practically implemented.
Evaluation:
Projects: The most crucial part of the evaluation will be the home projects. I will assign three in total (each for 50 points). The submission deadline will always be clearly stated in the assignment. Along with standard routine problems, the project will include some more challenging questions that may require additional independent reading, self-study, and possibly a longer time for discussion and resolution. However, they should be fun. I will expect you to also write proofs. You must argue your solutions in detail. Expect that you will need more than the last night before the submission deadline for the homework. I dont mind if you discuss the problems from the homework with your colleagues, but please, write the solutions independently; dont write anything you dont fully understand. We will provide enough comments and feedback on your projects. We may ask you to discuss some of your solutions with us individually and possibly redo them for some partial points.
For the exercises, you are advised to bring both pen, paper and notebook with you.
From the exercises, you can earn a total of 50 points for the semester.
- Your activity will be evaluated,
- you will write smaller tests during the exercises,
- and also receive homeworks.
- there will three homeworks assigned on GitHub classroom platform (each for 10 points).
- there will be one group project for 20 points.
This means that in total, from the course and exercises, you can gain a total of 200 points. To be admitted to the exam, you should get more than 100 points.
Final Exam: It will consist of an oral and written part and will be from the material from the entire semester. The written part, which will be for 100 points, and you must get more than 50 points. The final grade for the course will be calculated based on your performances during the semester and on the final exam according to the standard scale (90% and more A, 80 - 90% B, 70 - 80% C, 60 - 70% D, 55 - 60% E, less than 55% Fx.)