Applied Algorithmics 2017/2018
- 6 ECTS
- Taught in Portuguese
- Continuous Assessment
- relevant skillset
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.
Basic knowledge of algorithms and programming in C or Java.
Code of the CU in the Moodle platform: DEGI-254-1746
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
• Curve adaptation
• Matrices: Computational representations and operations with matrices
• Solving systems of equations
3. String Processing
• Elementary methods of sorting: Selection Sort, Insertion Sort, Shell-Sort
• Selection operation: main methods
• Merge operation; MergeSort
• 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
o Hash functions
o Separate threading
o Linear exploration
• 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.
• Cormen T H (2013) Algorithms Unlocked, MIT Press.
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 skill||improved?||assessed?|
|Achieving practical application of theoretical knowledge||Yes||Yes|
|Adapting to new situations||Yes|
|Analytical and synthetic skills||Yes||Yes|
|Commitment to effectiveness||Yes||Yes|
|Commitment to quality||Yes||Yes|
|Ethical and responsible behaviour||Yes|
|Event organization, planning and management||Yes||Yes|
|Foreign language proficiency||Yes|
|Information and learning management||Yes||Yes|
|IT and technology proficiency||Yes||Yes|
|Problem Analysis and Assessment||Yes||Yes|
|Relating to others||Yes|
|Written and verbal communications skills||Yes||Yes|