| Code |
16671
|
| Year |
1
|
| Semester |
S2
|
| ECTS Credits |
6
|
| Workload |
PL(30H)/T(30H)
|
| Scientific area |
Informatics
|
|
Entry requirements |
This course has no prerequisites. A level I programming maturity is recommended, but not required.
|
|
Learning outcomes |
The objectives of this UC focus on providing students with algorithmic complexity analysis techniques, different complex data structures, and a set of algorithms for solving computational problems.
At the end of this curricular unit, the student must be able to:
- Explain the usefulness and complexity of different data structures, as well as being able to combine different data structures to solve problems.
- Analyze the computational complexity (temporal and spatial) of a given algorithm.
- Implement different algorithms and data structures to solve complex problems.
|
|
Syllabus |
This course unit covers the following topics: (1) Recursion: definition, recursive calls, recurrence relations, and analysis of recursive algorithms. (2) Temporal and spatial complexity analysis: asymptotic notation (O, T, O), cycle analysis, average and worst-case scenarios, and introduction to recurrences. (3) Sorting algorithms: Bubble Sort, Insertion Sort, Selection Sort, Merge Sort, and Quick Sort, with comparison of efficiency and stability. (4) Data structures: vectors, dynamic vectors, singly and doubly linked lists, stacks, queues, priority queues, binary trees, search trees, and graph representation by matrix and adjacency list. (5) Search and traversal algorithms in trees and graphs (DFS and BFS).
|
|
Main Bibliography |
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms (Fourth Edition), The MIT Press, 2022.
Brad Miller and David Ranum. Problem Solving with Algorithms and Data Structures using Python, Luther College, 2006.
|
|
Language |
Portuguese. Tutorial support is available in English.
|