Discrete Structures

Code:

CC1001

Acronym:

CC1001

Level:

100

Keywords
Classification	Keyword
OFICIAL	Computer Science

Instance: 2017/2018 - 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	68	Plano de estudos a partir de 2014	1	-	6	56	162
L:F	0	Official Study Plan	2	-	6	56	162
			3
L:G	8	study plan from 2017/18	2	-	6	56	162
			3
L:M	0	Official Study Plan	2	-	6	56	162
			3
L:Q	1	study plan from 2016/17	3	-	6	56	162
MI:ERS	101	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, 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. Elementary topics in algebra: rings and modular arithmetic, boolean algebra.


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


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


8. 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

Makinson David 1941-; Sets, logic and maths for computing. ISBN: 978-1-84628-844-9
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.

keywords

Technological sciences

Evaluation Type

Distributed evaluation without final exam

Assessment Components

designation	Weight (%)
Exame	50,00
Participação presencial	0,00
Teste	50,00
Total:	100,00

Calculation formula of final grade

Mid semester test (50% of the final mark).
Final exam (50% of the final mark).
If MT is the mark obtained in the mid semester test and FE the mark
obtained in the final exam, then the final mark is given by:
F = MT*(0.5) + FE*(0.5) 
MT,FE >= 6 and F >= 9.5
To get approval in the distributed evaluation, students must obtain a minimum of 6 points (in a total of 20) in each test and a minimum of 9.5 as final mark.
The students not obtaining approval, can take a resit exam. The resit exam will have two different components (clearly indicated) corresponding to the topics evaluated in the mid term test and the final exam, allowing for two different scenarios to determine the final mark:

• the students can answer the two components of the resit exam, in which case the final mark is determined exclusively by the mark obtained in the exam (this option is mandatory for students that have not obtained a minimum of 6 points in the first test);
• the students can answer only one component of the test, in which case the final mark is the arithmetic mean between the mark obtained in the component answered in the resit exam and the mark obtained before for the complementary component.