Discrete Structures

Code:

CC1001

Acronym:

CC1001

Level:

100

Keywords
Classification	Keyword
OFICIAL	Computer Science

Instance: 2020/2021 - 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	2	Official Study Plan	3	-	6	56	162
L:CC	89	Plano de estudos a partir de 2014	1	-	6	56	162
L:F	0	Official Study Plan	2	-	6	56	162
			3
L:G	0	study plan from 2017/18	2	-	6	56	162
			3
L:M	1	Official Study Plan	2	-	6	56	162
			3
L:Q	0	study plan from 2016/17	3	-	6	56	162
MI:ERS	113	Plano Oficial desde ano letivo 2014	1	-	6	56	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.
John O.Donnell; Discrete mathematics using a computer. ISBN: 1-84628-241-1

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 (%)
Participação presencial	0,00
Teste	100,00
Total:	100,00

Amount of time allocated to each course unit

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

Eligibility for exams

Students are required a minumum of 6 (out of 20) in each test. All the studens can take the resit exam.

Calculation formula of final grade

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