Person in charge: | (-) |
Others: | (-) |
Credits | Dept. | Type | Requirements |
---|---|---|---|
7.5 (6.0 ECTS) | CS |
|
P1
- Prerequisite for DCSFW PRAP - Prerequisite for DCSFW |
Person in charge: | (-) |
Others: | (-) |
This subject aims to instil students with the ability to design, implement and assess data structures, as well as with the ability to design, implement and assess algorithms within these structures.
Estimated time (hours):
T | P | L | Alt | Ext. L | Stu | A. time |
Theory | Problems | Laboratory | Other activities | External Laboratory | Study | Additional time |
|
T | P | L | Alt | Ext. L | Stu | A. time | Total | ||
---|---|---|---|---|---|---|---|---|---|---|
6,0 | 6,0 | 3,0 | 0 | 3,0 | 12,0 | 0 | 30,0 | |||
Review of the concept of sequence. Lists with points of interest. Stacks and queues. Vector implementation and linked linear structure lists. Iterators.
|
|
T | P | L | Alt | Ext. L | Stu | A. time | Total | ||
---|---|---|---|---|---|---|---|---|---|---|
2,0 | 2,0 | 1,0 | 0 | 1,0 | 4,0 | 0 | 10,0 | |||
Review of the tree concept. Basic properties. Pre-ordered paths, post-ordered paths, disordered paths, by levels. Implementation of trees with vector pointers to children. Implementation of trees with pointers to parent-to-sibling.
|
|
T | P | L | Alt | Ext. L | Stu | A. time | Total | ||
---|---|---|---|---|---|---|---|---|---|---|
8,0 | 8,0 | 4,0 | 0 | 4,0 | 16,0 | 0 | 40,0 | |||
Dictionaries. Techniques for implementing simple dictionaries. Advanced implementation techniques. Binary search trees. Balanced search binary trees. Dispersion tables. Ordering algorithms: quicksort, mergesort, heapsort.
|
|
T | P | L | Alt | Ext. L | Stu | A. time | Total | ||
---|---|---|---|---|---|---|---|---|---|---|
8,0 | 8,0 | 8,0 | 0 | 8,0 | 16,0 | 0 | 48,0 | |||
review of the concept of abstract data types. Classes, methods, objects. Constructors, destructors, copy assignment and constructor. Implementation of ADTs using classes. Inheritance. Hierarchy of classes. Abstract classes. Polymorphism. Dynamic linking. Genericity. Classes and parameterised methods. Instancing.
|
Total per kind | T | P | L | Alt | Ext. L | Stu | A. time | Total |
28,0 | 28,0 | 16,0 | 0 | 16,0 | 56,0 | 0 | 144,0 | |
Avaluation additional hours | 4,0 | |||||||
Total work hours for student | 148,0 |
A highly practical approach is adopted, based on the presentation of a host of examples.
There will be three kinds of classes: theory sessions, problem sessions, and lab sessions. On average, three hours a week will be dedicated to theory classes, two hours a week to problems, and one hour a week to lab sessions. The teacher will schedule these classes in accordance with the needs of the theme taught.
The theory classes take the form of lectures in which the teacher sets out new concepts or techniques and examples illustrating them.
Practical classes focus on exercises and case studies. Teachers set the problems to be solved. The purpose of the exercises is to present and discuss fairly straightforward problems requiring little theory or technical knowledge. As a rule, they cover exercises that illustrate the concepts introduced in the most recent theory sessions. The problems dealt with in the case studies are more complex than those covered in the exercises. Furthermore, they involve different theoretical concepts, which need to be combined in order to come up with a good solution.
A set of practical exercises will be carried out in the lab classes. The teacher will set the practical exercises. Students will solve the exercise under the teacher"s close supervision.
Both continuous assessment tests (P) and a final exam (F) will be used. The latter covers the whole of the course material and lab practical work (L).
The course grade is calculated as follows:
0.3 L + 0.7 * max(F, 0.6 * F + 0.4 * P)
Mastery of object-oriented programming techniques: Knowledge of at least one imperative programming language and/or object-oriented language. Recursiveness. Basic knowledge of discrete mathematics. Ability to follow mathematically and formally-stated arguments. Some basic knowledge of statistics and probability.