Advanced Programming Laboratory

Year
3
Academic year
2017-2018
Code
01000301
Subject Area
Computer Science
Language of Instruction
Portuguese
Mode of Delivery
Face-to-face
Duration
SEMESTRIAL
ECTS Credits
6.0
Type
Compulsory
Level
1st Cycle Studies

Recommended Prerequisites

Basic knowledge of algorithms, procedural and object orientered programming, data structures and mathematics (course units Introduction to Programming and Problem Solving, Algorithms and Data Structures, Principles of Procedural Programming, Object Oriented Programming and Discrete Structures).

Teaching Methods

The goal of theory classes is to deliver theoretical concepts by the teacher, to present and discuss case-studies, to present the programming problems and to solve less complex problems, in a team. The aim of lab classes is to help students to solve the programming problems, to accompany the students in their project and to perform defenses.

Work Placement(s)

No

Syllabus

  1. Introduction
    1. Problem modelling and problem solving
    2. Computational complexity
    3. Algorithm paradigms
      1. Recursive search
      2. Backtracking
      3. Dynamic programming
      4. Greedy algorithms
      5. Branch-and-bound
      6. Applications
        1. Graphs
        2. Network flow
        3. Computational geometry

(optional) Other problems such as: numerical problems, matching problems, scanning and parsing problems, bioinformatics problems, cryptography, etc.

Head Lecturer(s)

Luís Filipe dos Santos Coelho Paquete

Assessment Methods

Assessment
1) Solving, individually, the programming problems 2) Practical assessments; 3) Project; 4) Individual defenses of the grades obtained.: 100.0%

Bibliography

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed., 2009.
S.Skiena and M.Revilla, Progamming Challenges, 2003.
D. Knuth, The Art of Computer Programming.
S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani,  Algorithms (draft)
J. Kleinberg, and E. Tardos, Algorithm Design, 2005
R. Sedgewick and K. Wayne, Algorithms, 4rd ed, 2011
B. Vöcking, H. Alt, M. Dietzfelbinger, R. Reischuk, C. Scheideler, H. Vollmer, D. Wagner (eds),  Algorithms Unplugged, 2011