Computational Methods

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.

General characterization

Code

11574

Credits

9.0

Responsible teacher

Pedro Manuel Corrêa Calvente Barahona

Hours

Weekly - 4

Total - 69

Teaching language

Português

Prerequisites

None.

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 Structures and Algorithms in Python [Goodrich, Tamassia & Goldwasser 2013-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 1 test.
The 1st test and project (T1 and P1) cover the topics of Programming, Data Structures and Algorithms;
The 2nd project (P2) covers 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 grade of the test, T = T1.

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 values​after rounding (i.e. P > = 7.5)

Exam
Students failed in the continuous assessment, but having obtained frequency, can take a final exam.
The theory grade after the exam, is the maximum of the test and exam grades, Nte = max(T1, 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.

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

Programs

Programs where the course is taught: