Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licenţă
Domeniul: Calculatoare şi tehnologia informaţiei
Programul de studii: Ingineria informatiei - in limba engleza
Limba de predare: Engleză

SYLLABUS

I. General data
Code	Subject	
MIG0003	Discrete Mathematics	

Semester	Hours: C+S+L	Category	Status	
1	2+1+0		compulsory	

II. Full status faculty members
Name and	Scientific	Didactic	Chair	Type of activity	
surname	title	title		C	S	L	
LUPSA Radu	Ph.D.	Lect.	Computer Systems	*			

Associated faculty members
Name and	Scientific	Institution	Type of	Type of activity	
surname	title		position	C	S	L	

III. Course objectives
Learning to work with representation and counting of combinatorial objects. Using combinatorial objects in modeling practical problems.	

IV. Course contents
1.	Introductory notions: sets, set operations, equinumerous sets; relations; functions: representations, algorithms.
2.	Set reunion and Cartesian product; inclusion-exclusion principle; lexicographic order, cardinality, numbering elements; characteristic function of a subset; applications.
3.	Permutations, combinations, partial permutations: representations, counting, numbering, applications.
4.	Partitions of an integer: number of partitions, duality.
5.	Stirling and Bell numbers.
6.	Recurrence relations, Fibonacci numbers, obtaining a closed formula from a recurrence, applications.
7.	Rooted trees: representation, applications.
8.	Graph theory fundamentals: definitions, representations, parsing, connected components, finding lowest length and lowest cost paths.	

V. Bibliography
1.	1. Ioan Tomescu: Introducere în combinatorică. Editura tehnică, Bucureşti,	 1972.
2.	Leon Livovschi, Horia Georgescu: Sinteza şi analiza algoritmilor. Editura ştiinţifică şi enciclopedică, Bucureşti, 1986.
3.	Zoltán Kása: Combinatorică cu aplicaţii. Presa universitară clujeană, Cluj-Napoca, 2003.
4.	Teodor Toadere: Grafe. Teorie, Algoritmi si Aplicatii. Ed. Albastra, Cluj-Napoca, 2002.
5.	Thomas Cormen, Charles Leiserson, Roland Rivest: Introducere în algoritmi. traducere, Editura Computer Lipris Agora, 2000.
6.	Kazimierz Kuratowski: Introducere în teoria mulţimilor şi în topologie. traducere, Editura tehnică, Bucureşti, 1969.	

VI. Thematic of didactic activities per weeks
1.	(week 1) Introductory notions: sets, set operations, equinumerous sets; relations; functions: representations, algorithms.
2.	(week 2) Set reunion and Cartesian product; inclusion-exclusion principle; lexicographic order, cardinality, numbering elements; characteristic function of a subset; applications.
3.	(weeks 3-5) Permutations, combinations, partial permutations: representations, counting, numbering, applications.
4.	(weeks 5-6) Partitions of an integer: number of partitions, duality.
5.	(week 7) Stirling and Bell numbers.
6.	(weeks 8-9) Recurrence relations, Fibonacci numbers, obtaining a closed formula from a recurrence, applications.
7.	(week 10) Rooted trees: representation, applications.
8.	(weeks 11-13) Graph theory fundamentals: definitions, representations, parsing, connected components, finding lowest length and lowest cost paths.	

VII. Didactic methods used

VIII. Assessment
•	1/3: homeworks, throughout the semester;
•	1/3: written exam regarding items 1-4 of the content (see above); it will be taken at mid-term and can be re-taken at the end of the semester and in the re-examination session.
•	1/3: written exam regarding items 5-8 of the content; it will be taken in the last week of the semester and can be re-taken in the re-examination session.
See also: http://www.cs.ubbcluj.ro/~rlupsa/edu/2008-discrete-math/requirements.html	

IX. Additional references
1.	http://www.cs.ubbcluj.ro/~rlupsa/edu/2008-discrete-math/	

	Dean,							Chair head,

	Date,							Course responsible,
								Lect. LUPSA Radu, Ph.D.