Discrete Structures

Code:

CC1001

Acronym:

CC1001

Level:

100

Keywords
Classification	Keyword
OFICIAL	Computer Science

Instance: 2014/2015 - 1S

Active?	Yes
Web Page:	http://www.dcc.fc.up.pt/~sandra/Home/ED1415.html
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:CC	77	Plano de estudos a partir de 2014	1	-	6	56	162
MI:ERS	124	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. 
   

   Elementary topics in logic: propositional calculus, logic equivalence, inference rules, breve introduction to predicate calculus.

 

1. 
   

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

 

1. 
   

   Mathematical induction: mathematical induction, recursive definitions.

 

1. 
   

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

 

1. 
   

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

 

1. 
   

   Elementary topics in algebra: rings and modular arithmetic, boolean algebra.

 

1. 
   

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

 

1. 
   

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

 

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.
Lab 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 taking an improving exam, and for students that have not obtained a minimum of 3 points in the first test);
• the students can only answer the component of the test corresponding to the topics evaluated in the second test, in which case the final mark is determined using the formula indicated for the distributed evaluation.