| 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.
|
|
Teaching Methodologies and Assessment Criteria |
- P1 - Project I: 17.5% (individual work)
- P2 - Project II: 32.5% (individual work)
- F - Attendance: 50% (individual computer-based test with partial consultation of content)
The final grade for the course unit results from the weighted average of the grades obtained in the defined assessment components. The student obtains approval for the course unit, being exempt from the exam, if they obtain a grade equal to or higher than 9.5.
Assessment by Exam
- Exam: 50% (written test)
Practical assignments count towards the final exam grade, with the exam only changing the attendance grade.
Admission requirements for attendance and exam:
- Minimum of 70% attendance in classes during the teaching-learning period (except for working students);
- Minimum grade of 6 in AE, where AE = ((P1 * 17.5%) + (P2 * 32.5%) + (F * 50%))
Failure to meet any of the requirements will result in failing the course unit and ineligibility for the exam.
|
|
Language |
Portuguese. Tutorial support is available in English.
|