Computational Methods
Code
11574
Academic unit
Faculdade de Ciências e Tecnologia
Department
Departamento de Informática
Credits
9.0
Teacher in charge
Pedro Manuel Corrêa Calvente Barahona
Weekly hours
3
Total hours
69
Teaching language
Português
Objectives
Knowledge:
The tools of a software development environment.
The essential constructs of an imperative programming language.
Introduction to algorithm design and analysis.
Fundamental notions of relational databases.
Introduction to SQL Language
Application:
Break down a problem into simpler problems.
Write a program in an imperative programming language (Python).
Test a program in a particular programming environment.
Design and test algorithms in an imperative language (Python)
Design a simple relational database
Formulate SQL queries.
Soft-Skills:
Ability to achieve goals.
Time management ability and meeting deadlines.
Prerequisites
None.
Subject matter
1. Introduction to Programming in Python
a. Data Types
• Basic Data Types (Numbers, Characters)
• Data Structures
Lists, Vectors, Arrays
Strings
Dictionaries
b. Imperative Programming
• Execution Control
• Sequential, Conditional and Repeated Execution
• Functions
• Nested and Recursive Functions
• Input-Output
• Operation Systems and File Types
• Text Files (Reading from / Writing to)
• Basic Text Processing
2. Algorithms
a. Search in Arrays
• Sequential vs. Bipartite
b. Sorting algorithms
• Bubble, Insertion, Quick and Merge Sort
• Correctness and Complexity
c. Simulation
• Random Variables and Processes
• Automata (State and Transitions)
d. Graph Properties and Algorithms
• Polynomial:
• Minimum Spanning Trees (Prim)
• Shortest Distances (Floyd-Wrashall)
• Nondeterministic
• Graph Colouring
• Hamiltonian Circuit
• Correctness and Complexity
3. Introduction to Databases
a. Relational Databases
• History and Applications
b. Modelling and Design
• Entities, Attributes and Keys
• Entity-Relational Model
• Relational Algebra (Brief Introduction)
c. Normalisation
• Functional Dependencies
• Closures
• Normal Forms
d. Querying Relational Databases
• SQL - Structured Query Language (DDL and DML)
• Queries - Joins, Aggregation Functions, Views
• Consistency; Triggers
Bibliography
Main references:
Introduction to Programming (in Python):
• Allen B. Downey. Think Python: How to Think Like a Computer Scientist (version 2.0.17).
http://greenteapress.com/wp/think-python-2e/
• John V. Guttag. Introduction to Computation and Programming Using Python, MIT PRESS,
• Ernesto Costa. Programação em Python - Fundamentos e Resolução de Problemas, FCA, 2015
Algorithms (in Python):
• Data Structures and Algorithms in Python, by Michael T. Goodrich, Roberto Tamassia, and Michael H. Goldwasser, Wiley, 2013
https://doc.lagout.org/programmation/python/Data%20Structures%20and%20Algorithms%20in%20Python%20[Goodrich,%20Tamassia%20&%20Goldwasser%202013-03-18].pdf
Databases (primers):
• http://www.sqlitetutorial.net/sqlite-python/
• https://www.pythoncentral.io/introduction-to-sqlite-in-python/
Teaching method
The (theoretical) concepts are explained in the first part of the classes, which is immediately followed by application exercises in the second part of the classes (theoretical-practical). In this way students can immediately grasp the concepts taught and check the difficulties they may experience in their exploration.
Evaluation method
Evaluation Rules
Continuous Assessment
Continuous assessment is done through 2 projects and 2 tests.
The 1st test and project (T1 and P1) cover the topics of Programming, Data Structures and Algorithms;
The 2nd test and project (T2 and P2) cover the topics of Databases.
Grades
The grade of the continuous assessment, Nca, is the weighted mean of the theory and practice grades (all grades in the range 0 to 20)
Nca = 40% T + 60% P
The theory grade, NT, is the weighted mean of tests, T1 and T2.
T = (2•T1 + T2) / 3
The practice grade, NP, is the arithmetic mean of projects, P1 and P2.
P = (P1 + P2) / 2
Approval
A student with a positive continuous assessment grade (Nca> = 9.5) obtains approval with a final mark (Nf) equal to Nca, rounded to the units.
Frequency
A student gets frequency if his/her practice grade exceeds 8 valuesafter rounding (i.e. P > = 7.5)
Exam
Students failed in the continuous assessment, but having obtained frequency, can take a final exam, covering the topics of the tests.
The theory grade after the exam, NTe, is the maximum of the tests and exam grades.
Nte = max ((2•T1 + T2) / 3, E)
After the exam, the final grade, Nf, is is the weighted mean of the final theory and practice grades .
Nf = 40% Nte + 60% P
Students who obtained approval in continuous evaluation, can improve their final grade in the exam. Their final grade is obtained with the same rules.