Algorithms and Data Structures
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.
General characterization
Code
3742
Credits
6.0
Responsible teacher
Artur Miguel de Andrade Vieira Dias, Carla Maria Gonçalves Ferreira
Hours
Weekly - 4
Total - 84
Teaching language
Português
Prerequisites
Mandatory pre-requisite: Microprocessors programming (LEEC)
Bibliography
Mark Allen Weiss.
Data Structures and Algorithm Analysis in C (second edition).
Addison-Wesley, 1997.
ISBN 0-201-49840-5 (Hard cover)
On the C Programming Language
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
Student assessment consists of a handwritten component and a laboratory component carried out throughout the semester.
The handwritten component consists of 2 individual tests (1 small project and 1 written test), and the laboratory component consists of 1 group work (practical work).
All assessment elements (test, project, practical work and exam) are classified on a scale of 0 to 20 with values rounded to the nearest tenth.
Laboratorial Component
The students must carry out 1 practical work (TP) with a weight of 40% in the final grade. This practical work will be carried out in a group of 2 students from the same practical shift.
The laboratory component grade (NCL) will be awarded according to the following formula:
NCL = 0.40 * TP
Some students may have to give an oral discussion of the work, which influences the practical work grade.
Frequência
To obtain "frequência" (minimal grade), the practical work grade (TP) must be greater than or equal to 9.5 out of 20 values. There may be an individual written test to validate each student''s contribution to the work. Frequency also depends on passing this written test.
Theoretical Component
Students should do 1 individual test (T) and a small project (P) on-campus or an exam (EX) in the exam period.
The project P weights 15% and the test T weights 45% in the final grade. The grade of this component is obtained using the folowing formula:
NCT = 0.15 * P + 0.45 * T
The exam EX weights 60% of the final grade. It might be used to aprove or to improve the grade.To have access to it, a student needs to have "frequência" (a minimal grade on the assignment). The grade of the theoretical component is obtained with the following formula:
NCT = 0.6 * EX
Approval
To obtain approval it is necessary and sufficient:
NCL >= 0.40 * 9.5
e
NCT >= 0.60 * 9.5
Final Grade
For approved students, the final grade (NF) is obtaind with the following formula, rounded to units:
NF = NCL + NCT
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.