How to find us
|
Contacts

Applied Algorithmics 2017/2018

  • 6 ECTS
  • Taught in Portuguese
  • Continuous Assessment

Objectives

i. To evaluate the efficiency and performance of an a algorithm, therefore determining its complexity and execution time
i. To understand the problem solving methods associated to each domain (mathematics, string processing, sorting and searching), creating schemes to represent them as well as the adequate data structures to be used
iii. To be able to develop algorithms to solve advanced problems in several domains (mathematics, string processing, sorting and searching)
iv. To compare and evaluate the different methods and algorithms learned in each domain, so as to evaluate their respective performance.

This CU contributes to the following learning outcomes of the course: Capability of abstraction and to know how to express the logical reasoning needed to solve problems; To program in different environments.

Recommended Prerequisites

Basic knowledge of algorithms and programming in C or Java.

Code of the CU in the Moodle platform: DEGI-254-1746

Teaching Metodology

In TP classes the exposition-active method is used for the topics of the programme, complemented with discussion in classroom, so as to promote the critical thinking of students about the learned topics.
In practical classes, the teaching-learning tutorial methodology is used, based on two pillars: a) training with practical exercises b) application to projects.

Body of Work

1. Analysis of Algorithms
• Determination of T(n)
• Complexity of an algorithm
• Classification of algorithms
2. Mathematical Algorithms
• Polynomials: Polynomial calculation and operations with polynomials
• Integration
• Curve adaptation
• Matrices: Computational representations and operations with matrices
• Solving systems of equations
3. String Processing
• Compression
• Encryption
4. Sorting
• Elementary methods of sorting: Selection Sort, Insertion Sort, Shell-Sort
• Quick-Sort
• Heap-Sort
• Selection operation: main methods
• Merge operation; MergeSort
5. Searching
• Search related operations
• Main methods
o Sequential Search
o Sequential search with threaded lists
o Binary Search
o Binary Search Interpolated
o Search in a Binary Tree
• Hashing
o Hash functions
o Separate threading
o Linear exploration

Recommended Bibliography

• Cormen T H, Leiserson C E, Rivest R L and Stein C (2009) Introduction to Algorithms, 3rd Edition, MIT Press.
• Neto J (2014) Programação, Algoritmos e Estruturas de Dados, 3ª. Edição, Escolar Editora.
• Sedgewick R and Wayne K (2011) Algorithms, 4th Edition, Addison-Wesley.

Complementary Bibliography

• Cormen T H (2013) Algorithms Unlocked, MIT Press.

Weekly Planning

Week 1 – Presentation of the CU. Revisions.
Week 2 – Analysis of Algorithms: Determination of T(n); Complexity of an algorithm; Classification of algorithms
Week 3 – Analysis of Algorithms (cont.)
Week 4 – String Processing: Compression
Week 5 – String Processing: Encryption
Week 6 – String Processing: Encryption (cont.)
Week 7 – Mathematical Algorithms: Polynomials; Polynomial calculation and operations with polynomials
Week 8 – Mathematical Algorithms: Polynomials (cont.); Exam #1.
Week 9 – Mathematical Algorithms: Integration; Curve adaptation
Week 10– Mathematical Algorithms: Matrices; Computational representations and operations with matrices
Week 11– Mathematical Algorithms: Solving systems of equations
Week 12 – Sorting; Elementary methods of sorting
Week 13 – Sorting; Advanced methods of sorting
Week 14 – Searching; Search related operations; Main methods; Hashing
Week 15 – Exam #2; Presentation of the practical projects

Demonstration of the syllabus coherence with the curricular unit's objectives

Objectives (i) and (iv) of the curricular unit are achieved through the contribution of topic (1) of the contents, since it allows the student to understand the essential concepts so as to perform the analysis of an algorithm, thus determining its complexity and execution time.
Topics (2) to (6) of the contents contribute to objectives (ii) and (iii) of the curricular unit, since they allow the student to acknowledge an overview of advanced problem solving methods in the domains of mathematics, string processing, sorting and searching and to be able to make schemes of the methods and data structures used and develop the corresponding algorithms. The focus is mainly in the logical thinking associated to the way of solving the problems and the critical evaluation of the efficiency of the associated algorithms as considered under objective (iv).

Demonstration of the teaching methodologies coherence with the curricular unit's objectives

In TP classes, the exposition-active method will be used to present the main concepts. The use of questions-answers in these presentations and discussion in the classroom will be used for frequent interaction with students, in order to promote their critical thinking, the ability to issue insight opinions and internalize the key concepts. In practical classes, practical exercises solving will be used to check students' ability to apply the knowledge gained in the TP classes in real situations of problem solving and in the development of the associated algorithms and programs. The development of the practical project will be used to enhance these skills, covering the analysis, design, implementation and testing of a software program to address a problem in one of the domains covered in the curricular unit.

relevant generic skillimproved?assessed?
Achieving practical application of theoretical knowledgeYesYes
Adapting to new situationsYes 
Analytical and synthetic skillsYesYes
Commitment to effectivenessYesYes
Commitment to qualityYesYes
CreativityYesYes
Ethical and responsible behaviourYes 
Event organization, planning and managementYesYes
Foreign language proficiencyYes 
Information and learning managementYesYes
IT and technology proficiencyYesYes
Problem Analysis and AssessmentYesYes
Problem-solvingYesYes
Relating to othersYes 
Research skillsYesYes
Self-assessmentYes 
TeamworkYesYes
Written and verbal communications skillsYesYes
This website uses cookies to provide better functionality and for performance measurements (European Union Directive 2009/136/EC)
Please take a few minutes do answer a few quick questions about our website.