Algorithms and Data Structures
- Details
- Category: Discipline
- Sedgewick R., Wayne K. (2011). Algorithms. Addison-Wesley.
- IT Engineering
- 587
- 13558
- Algorithms and Data Structures
- ISMAT587-13558
- 2
- 6
- 0
- 12
- Não
- Português
- The content taught is applied using programming. Active, problem-solving-oriented methodologies (PBL) are used. At the end of each part, projects are developed integrating all the content taught.
- Mandatory
- LO1. Understand and apply the methods of analysis of iterative and recursive algorithms. LO2. Understand and identify essential strategies for the design of algorithms. LO3. Master advanced data structures and fundamental algorithms on them. LO4. Understand the influence of the design / choice of an algorithm and / or data structure on the performance of solving a problem. LO5. Know and identify intractable problems, as well as algorithms that present an approximate solution to them.
- S1. Sequential search. S2. Binary search. S3. Fundamentals of algorithm analysis. Analysis of the best case, worst case, average case. Growth of functions. Asymptotic complexity. Notations. Recurrences and respective resolution. Recursion trees. Master method. S4. Review of simple sorting methods: selection, insertion and bubble. S5. Sorting methods merge sort and quicksort (recursive). S6. Division and conquest. S7. Heapsort ordering method. Min and Max-heap. S8. Linear time ordering methods. Counting sort, Radix sort, Bucket sort. S9. Algorithm design strategies. Division and conquest (revisited). "Greedy" algorithms. Dynamic programming. S10. Amortized Analysis. S11. Advanced Data Structures. Priority Queues (Min and Max-Priority) Binary Search Trees. Balanced BSTs. Graphs. Hashing.
Descrição dos instrumentos de avaliaão (individuais e de grupo): testes, trabalhos práticos e ponderação na nota final.
Descrição
Data limite
Ponderação
Teste de avaliação
a marcar
60%
TP1
a marcar
20%
TP2
a marcar
20%
O teste de avaliação é individual e os trabalhos práticos são em grupo (no máximo 2 elementos). O TP1 consiste num desafio sobre estratégias e concepção de algoritmos.
O TP2 consiste num desafio que inclue a aplicação dos conceitos sobre estruturas de dados.
O teste de avaliação inclui toda a matéria leccionada.
- Semestral
- In programming, the themes are repeated and the solutions too, so it is essential to understand and know how to apply the studied methods that present the best solution to well-known problems. The UC Algorithms and Data Structures addresses the study of fundamental data structures and classic algorithms, used in programming. The correct use of algorithms and data structures allows to obtain programs written in a better way, with fewer errors and optimized the execution time and allocated memory.
