Discrete Structures

Code:

CC1001

Acronym:

CC1001

Level:

100

Keywords
Classification	Keyword
OFICIAL	Computer Science

Instance: 2024/2025 - 1S

Active?	Yes
Responsible unit:	Department of Computer Science
Course/CS Responsible:	Bachelor in Computer Science

Cycles of Study/Courses

Acronym	No. of Students	Study Plan	Curricular Years	Credits UCN	Credits ECTS	Contact hours	Total Time
L:B	0	Official Study Plan	3	-	6	48	162
L:CC	135	study plan from 2021/22	1	-	6	48	162
L:F	0	Official Study Plan	2	-	6	48	162
			3
L:G	3	study plan from 2017/18	2	-	6	48	162
			3
L:IACD	106	study plan from 2021/22	1	-	6	48	162
L:M	2	Official Study Plan	2	-	6	48	162
			3
L:Q	1	study plan from 2016/17	3	-	6	48	162

Teaching language

Portuguese

Objectives

Study of the fundamental discrete structures that serve as a theoretical basis for the area of Computer Science/Informatics.  

Learning outcomes and competences

After taking the course the students should be capable of:

• Work with mathematical notation and common concepts in discrete mathematics;
• Construct and understand mathematical proofs;
• Use mathematical concepts to formalise and solve problems in Computer Science/Informatics.

 

Working method

Presencial

Program

1. Set theory: sets and subsets, set operations, Veen diagrams.


2. Mathematical induction: mathematical induction, recursive definitions.


3. Elementary topics in logic: propositional calculus, boolean algebra, logic equivalence, inference rules, brief introduction to predicate calculus.


4. Integer numbers: the division algorithm, prime numbers, the greatest comum divisor and Euclid’s algorithm, the fundamental theorem of arithmetic.


5. Relations: cartesian products and relations, properties, functions, computational representations of relations, partial orders, equivalence relations and partitions, modular arithmetic.


6. Counting:  sums and products, permutations and combinations, binomial coefficients.


7. Graphs: definitons and examples, sub-graphs, complement and isomorphic graphs, degree of a vertex, planar graphs, Eulerian paths and Hamiltonian cicles in graphs. 

Mandatory literature

Grimaldi Ralph P.; Discrete and combinatorial mathematics. ISBN: 978-0-201-54983-6 hbk
Kenneth H. Rosen; Discrete Mathematics and its Applications, McGraw-Hill, Inc.

Teaching methods and learning activities

Lectures: exposition of the elements in the syllabus as well as of examples and case studies.
Tutorial classes: resolution of exercises proposed each week.

Evaluation Type

Distributed evaluation without final exam

Assessment Components

designation	Weight (%)
Teste	100,00
Total:	100,00

Amount of time allocated to each course unit

designation	Time (hours)
Estudo autónomo	114,00
Frequência das aulas	48,00
Total:	162,00

Eligibility for exams

Students are required a minumum of 6 (out of 20) in each test. To be admited to exam  a student must attend at least of 3/4 of all lab classes. All the studens with sufficient attendency can take the resit exam.

Calculation formula of final grade

The final grade (FT - firts test, ST - second test)
F = FT*(1/2) + ST*(1/2)
FT,ST >= 6 e F >= 9.5

Special assessment (TE, DA, ...)

final exam

Classification improvement

Final exam