Algorithmic Strategies

Recommended Prerequisites

Basic knowledge of algorithms, computation theory procedural and object oriented programming, data structures and mathematics (course units Introduction to Programming and Problem Solving, Algorithms and Data Structures, Principles of Procedural Programming, Object Oriented Programming, Computation Theory 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 and written exercises about topics of algorithmic paradigms, to accompany the students in their project and to perform defenses.  The assessment consist of: 1) Written individual assessments; 2) Programming assessments in a team environment; 3) Programming projects in a team environment; 4) Individual defenses of the grades obtained. The system Mooshak is used as a tool for automatic judging in programming assessments and programming projects. The test cases for each problem are generated in order to test different scenarios. Hence, students can refine their implementation to make it correct and more efficient according to the grade given. The exam applies only to the written assessments.

Learning Outcomes

  To strengthen the ability to solve programming problems by algorithmic paradigms in different problem domains. Starting from a verbal problem descrition, the student must be able, himself or within a group:

• To understand the problem and relate it to other known problems;
• To identify algorithmic paradigms that are suitable for the problem at hand;
• To design particular algorithms for solving the problem at hand, based on the paradigms that are taught in class;
• To implement algorithms in a modular way, using appropriate data structures;
• To understand the complexity bounds of the algorithms;
• To explain and justify the options that were taken during the problem solving process.

Main skills to acquire are:

• Analysis and synthesis, problem solving
• Critical reasoning
• Autonomous learning, application of theory into practice.

Secondary skills are:

• Decision making
• Teamwork

Creativity and adaptability to new scenarios

Work Placement(s)

No

Syllabus

1. Introduction

▪       Problem modeling and problem solving

▪       Computational complexity

2. Algorithm paradigms

▪       Recursive search

▪       Backtracking

▪       Dynamic programming

▪      Greedy algorithms

▪       Branch-and-bound

3. Applications

▪       Graphs

▪       Network flow

▪       Computational geometry

4. (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
Project: 20.0%
Frequency: 40.0%
Exam: 40.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.

• 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