Understanding advanced concepts of discrete mathematics from both theoretical and algorithmic perspectives.
Prerequisites
Discrete Mathematics 1
Scope
Lecture/classes:
Selected graph classes: interval graphs, k-trees, chordal graphs, edge graphs, and their properties.
Various types of domination in graphs.
Directed graphs, definitions, and notations.
Strongly connected, transitive, and acyclic directed graphs, their properties.
Selected algorithms for directed graphs.
Definition of a matroid. Examples and basic properties.
Teaching methods
Lecture: conventional, conversational.
Classes: classical problem-solving method.
Learning outcomes and methods of theirs verification
Outcome description
Outcome symbols
Methods of verification
The class form
Assignment conditions
Conditions for passing classes and lectures:
Checking students' level of preparedness and their activity during exercises.
A test with tasks of varying difficulty levels, allowing assessment of whether and to what extent a student has achieved the mentioned learning outcomes, mainly in terms of skills and competencies.
Conversation during the lecture to verify higher levels of learning outcomes in terms of knowledge and skills.
Exam.
The final grade for the course consists of the exercise grade (50%) and the lecture grade (50%). The condition for passing the course is obtaining positive passing grades for both exercises and the lecture.
Recommended reading
J. Bang-Jensen, G.Gutin, Digraphs, Theory and Algorithms, 2001.
A. Brandstadt, V.B. Le, J.P.Spinrad, Graph Classes: a survey, SIAM 2004
R. Distel, Graph Theory, Springer-Verlag, New York 1997
D. J. A. Welsh, Matroid theory, Academic Press, Inc., New York, 2010.
Further reading
H. L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth,Theoretical Computer Science 209 (1998) 1-45.
Notes
Modified by dr hab. Elżbieta Sidorowicz, prof. UZ (last modification: 12-01-2024 18:36)
