Adam Mickiewicz University, Poznań - Central Authentication System

Combinatorial algorithms

General data

Course ID:	06-DALKLI0
Erasmus code / ISCED:	(unknown) / (unknown)
Course title:	Combinatorial algorithms
Name in Polish:	Algorytmy kombinatoryczne
Organizational unit:	Faculty of Mathematics and Computer Science
Course groups:	(in Polish) Moodle - przedmioty Szkoły Nauk Ścisłych
ECTS credit allocation (and other scores):	0 OR 6.00 (depends on study program) Basic information on ECTS credits allocation principles: the annual hourly workload of the student’s work required to achieve the expected learning outcomes for a given stage is 1500-1800h, corresponding to 60 ECTS; the student’s weekly hourly workload is 45 h; 1 ECTS point corresponds to 25-30 hours of student work needed to achieve the assumed learning outcomes; weekly student workload necessary to achieve the assumed learning outcomes allows to obtain 1.5 ECTS; work required to pass the course, which has been assigned 3 ECTS, constitutes 10% of the semester student load. view allocation of credits
Language:	Polish
Short description:	Decision and optimization problems Generation of subsets Generation of permutations Partitions of sets Generation of set partitions RGF functions Integer partitions Trees, Prufer's code Stable marriage problem NP-complete problems Approximation algorithms
Full description:	Objective of this course is to acquaint students with a specific and important class of algorithms in the context of combinatorial problems. The achieved learning outcomes are competences of algorithmic solutions of combinatorial problems which models questions met in practice.
Bibliography:	T.Cormen, Ch.Leiserson, R.Rivest, C.Stein, Introduction to algorithms, The Massachusetts Institute of Technology, 2001 S. Dasgupta, Ch. Papadimitriou, U. Vazirani, Algorithms, McGraw-Hill, New York 2008 D. Knuth, Stable marriage and its relation to other combinatorial problems, American Mathematical Society 1997 D. Knuth, The art of computer programming, Volume 4. Generating all tuples and permutations, Addison-Wesley, 2005 D. Kreher, D. Stinson, Combinatorial algorithms, CRC Press 1999 W. Lipski, Kombinatoryka dla programistów, WNT, Warszawa 2004 (in Polish) E. Reingold, J. Nievergelt, N. Deo, Algorytmy kombinatoryczne, PWN, Warszawa 1985 (in Polish) P. Stańczyk, Algorytmika praktyczna, Nie tylko dla mistrzów, PWN, Warszawa 2009 (in Polish) V. Vazirani, Approximation algorithms, Springer-Verlag, 2003 N.Wirth, Algorithms + data structures = programs, Prentice Hall Inc., 1976

Classes in period "Academic year 2020/2021, summer semester" (past)

Time span:	2021-03-01 - 2021-09-30	Selected timetable range: weekly course term Navigate to timetable MO WYK LAB TU W TH LAB FR
Type of class:	laboratory, 30 hours, 45 places more information lecture, 30 hours, 45 places more information
Coordinators:	(unknown)
Group instructors:	Joanna Berlińska, Zbigniew Palka
Students list:	(inaccessible to you)
Examination:	Course - Exam laboratory - Graded credit lecture - Exam

Course descriptions are protected by copyright.
Copyright by Adam Mickiewicz University, Poznań.