Algorithms and Data Structures
Code
3742
Academic unit
Faculdade de Ciências e Tecnologia
Department
Departamento de Informática
Credits
6.0
Teacher in charge
Fernanda Maria Barquinha Tavares Vieira Barbosa, Luís Manuel Marques da Costa Caires
Weekly hours
5
Total hours
70
Teaching language
Português
Objectives
Knowledge: Basic techniques for solving problems: fundamental abstract data types (list, set, stack, queue, dictionary, ordered dictionary) and abstract data types of the problem domain; basic algorithm design techniques: fundamental data structures (vector, single and double linked list, hash table, binary trees); basic techniques of algorithm analysis: spatial and temporal complexity.
Know-how: Model programs using abstract data types; define and implement abstract data types in the problem domain; calculate the spatial and temporal complexity of algorithms; implement fundamental abstract data types, using the most adequate data structures; design and implement efficient solutions to concrete problems.
Soft-skills: Ability to evaluate solutions; ability to select the suitable techniques to solve a problem; skills in writing communication: reports of discipline projects.
Subject matter
- Modeling programs, using abstract data types
- Method for the analysis and design of a solution
- Definition and implementation of abstract data types in the problem domain
- Introduction to Algorithm Analysis
- Formal specification of abstract data types:
- Queue (LIFO)
- Stack (FIFO)
- List
- Set
- Dictionary
- Ordered Dictionary
- Study of the fundamental data structures, including the analysis of the algorithmic in the best, worst and expected case:
- Circular Vector,
- Singly and Doubly Linked Lists,
- Open and Closed-Hash Tables,
- Search Trees and Binary Trees.
Bibliography
Mark Allen Weiss.
Data Structures and Algorithm Analysis in C (second edition).
Addison-Wesley, 1997.
ISBN 0-201-49840-5 (Hard cover)
Linguagem de Programação C
Brian Kernighan and Dennis Ritchie
The C Programming Language (second edition).
Prentice-Hall, 1988.
ISBN 0-13-110362-8 (Paperback)
Pedro Guerreiro.
Elementos de Programação com C (3ª edição).
FCA - Editora de Informática, 2005.
Luis Damas.
Linguagem C (12ª edição).
FCA - Editora de Informática, 2005.
Teaching method
There are one lecture and a lab session each week.
In the lectures, all course contents are presented using concrete practical examples. In the laboratory, students design, analyse and implement programs for specific problems by applying the knowledge gained.
Students will be evaluated by practical works and a test.
Evaluation method
The student assessment consists of a theoretical component and a laboratory component held throughout the semester.
The theoretical component consists of 1 single test (test or exam), and laboratory component by 2 individual works and 1 group work (practical works).
All assessment (test, pratical works and exam) are rated on a scale of 0 to 20.
Laboratory component
During the lessons, students should realize 3 practical works (tp1, tp2 and tp3) with weights 15%, 20% and 25% on final grade, respectively. Practical work tp1 and tp2 will be conducted individually, while tp3 will be done in groups of 2 students.
Theoretical Component
Students must realize an individual test (t1), or an exam (ex). Any of these assessments will have a weight of 40% on the final grade.
Final Grade (Continuous Assessment)
- For students with a test score greater or equal to 9.0 values, the final grade (NF) will be awarded according to the following formula, rounded to the unit:
NF = 0.15 * tp1 + 0.2 * tp2 + 0.25 * tp3 + 0.4 * t1.
- For students with a grade lower than 9.0 values, the final grade will be the test score, rounded to the unit:
NF = t1.
Final Grade (Exam)
- For students with an exam score greater or equal to 9.0 values, the final grade (NF) will be awarded according to the following formula, rounded to the unit:
NF = 0.15 * tp1 + 0.2 * tp2 + 0.25 * tp3 + 0.4 * ex.
- For students with a grade lower than 9.0 values, the final grade will be the exam score, rounded to the unit:
NF = ex.