107131 - DATA STRUCTURE AND ALGORISMS

Subject type: Mandatory

Coordinator: Adso Fernández Baena

Trimester: Third term

Credits: 4

Practice and / or exam statements may be in English.

This subject closes the block of the programming subjects of the first course. It is divided into four: the first part studies the use of the most frequent volatile data stores (in memory): queues and stacks, lists, sets, maps, ... while continuing the OO approach initiated in the subjects previews. The second part is a brief introduction to recursive programming techniques. The third part shows the use of files as a non-volatile storage tool. The last part is an introduction to algorithmic complexity. 

If, for reasons related to COVID-19, the subject should be taught in a non-contact mode or in a mode that represents a significant decrease in attendance, the methodology of the sessions will be adapted to these. of this adaptation will be the one to preserve to the maximum the achievement of the knowledges and of the competitions specified in this educational plan.
 

At a general level, this subject contributes to the following learning outcomes specified for the subject to which it belongs (Algorithmic and Programming)

• Demonstrate knowledge and understanding of essential facts, concepts, principles and theories related to computer science and its reference disciplines.
• Apply basic techniques of modular problem decomposition
• Design program architecture using object orientation, modularization, and specification and implementation techniques for abstract data types.
• Build correct and efficient algorithms for small difficulty problems.
• Implement simple algorithms in an imperative reference programming language for the initial level
• Identify the most appropriate algorithmic solutions to solve problems of medium difficulty
• Reason about the correctness and efficiency of an algorithmic solution.
• Design, write, test, debug, document, and maintain code in a high-level language to solve programming problems by applying algorithmic schemas and using data structures. 
• Use the tools of a software development environment to create and develop applications

At a more specific level, at the end of the course the student must be able to:

• LO1: Apply recursive techniques to solve problems. Coding programs of a recursive nature.
• LO2: Understand the high-level specification of data collections such as stacks, queues, lists, sets, and dictionaries (associative collections). Make use of these collections in programs, applying appropriate algorithms.
• LO3: Select the most appropriate data collections for a given problem
• LO4: Store and retrieve information from files.
• LO5: Show knowledge about the different classes of computational complexity

All the theoretical concepts of the subject will be exposed in theory classes (large groups). In these classes, and at the discretion of the teachers, exercises and problems of a more practical nature will also be solved. Likewise, and always at the discretion of the teachers, students may be asked to solve, individually or in groups, short problems and / or exercises. These activities, brief and optional, will serve the student as a tool for self-assessment of their achievement of the contents of the subject and can be used by the teacher to make decisions about the final grade of the student good and never to the detriment of the numerical grade calculated according to the grading system specified by the subject.

Students should attend all classes with a laptop with the ability to run the appropriate software for the subject. Teachers will report on what this software is and how it can be obtained.

Concepts of a more practical nature and everything that can essentially be considered the practical application of theoretical concepts will be worked on more intensively in small (laboratory) groups. In the sessions scheduled for this purpose, the appropriate tools will be given to solve the scheduled activities well and it is expected that these will be extended from a temporal point of view, beyond the laboratory hours and that, consequently, , students must complete them during the time of autonomous learning.

Totally optional activities will be made available to students to help them prepare and prepare for the compulsory ones.

1.- Data collections

• Sequential collections (stacks, queues, lists)
• Sets
• Associative collections (maps or dictionaries)

2.- Recursion

• Recursive Algorithms Vs. iterative algorithms
• Recursive sequence treatment. Strategies

3.- Permanent warehouses: archives

• I / O to and from files. Channels
• Text files
• Data files (binary)

4.- Introduction to algorithmic complexity

A series of activities of an eminently practical nature (short exercises, problems ...) are made available to students, which are the basis of the learning activities of the subject. These activities will have to be solved by the students, often in a non-contact way, following the instructions of the teachers and will also be worked in class, either as examples in the theory sessions, or in the laboratory sessions. Although these activities will be optional (teachers will not individually verify the performance by students), they will be essential to achieve the theoretical and practical knowledge of the subject.

In order to gather evidence of the achievement of the expected learning outcomes, the following evaluative activities will be carried out:

Two written tests (using, when appropriate, an IDE tool)

• The first test will focus on the first content (data collections) and will provide evidence of learning outcomes RA2 and RA3. This test asks students to properly develop software from a pre-established basis. This has to do with the following common and specific competences (in brackets the most relevant aspects of each competence to which the subject contributes)
  • CIN1 (software development),
  • CIN5 (maintain software),
  • CIN6 (apply algorithmic procedures),
  • CIN7 (using data structures),
  • CIN8 (build and maintain applications),
  • EFB3 (understand and master the concepts of algorithms) i
  • EFB4 (use of computer programs)

• The second test will include all the contents and will give evidence of all the expected learning outcomes. This test asks students to properly develop software from a pre-established basis and includes the use of recursion and files. At the level of common and specific competencies, all the above will be relevant for the first test, adding:
  • CIN13 (knowledge and application of the necessary tools for storage)

There will also be four practices:

• In the first two internships, students will be required to code, test, debug, and document programs that make use of data collections. With this it will be possible to collect evidence of the learning outcomes RA2 and RA3.
• The third practice will work, above all, on the coding, testing, debugging and documentation of programs of a recursive nature. With this it will be possible to collect evidence of the learning outcome RA1.
• The fourth practice will work, above all, the coding, testing, debugging and documentation of programs that make use of data collections and archives, thus collecting evidence of learning outcomes RA2, RA3 and RA4.  

At the competence level, the four internships, which will mostly have to be developed in non-contact time, cover all the common and specific competencies of the subject:

• CIN1 (software development),
• CIN3 (effective work habits in software development environments)
• CIN5 (maintain software),
• CIN6 (apply algorithmic procedures),
• CIN7 (using data structures),
• CIN8 (build and maintain applications),
• CIN13 (knowledge and application of the necessary tools for storage)
• EFB3 (understand and master the concepts of algorithms) i
• EFB4 (use of computer programs)

In order to pass (pass) the assessment activities, students will have to demonstrate

• That they have acquired the theoretical knowledge related to the contents of the subject and that their understanding allows them to put them into practice [MECES-2 point a, point c]
• That they can develop solutions to problems that, although they are similar to others seen above, present aspects that are new [MECES-2 point f]

In relation to the basic competences assigned to the subject, these are covered especially with regard to the aspects that are explained:

• CB2: problem solving within their area of ​​study.
• CB5: development of learning skills needed for further studies (autonomous access to documentation, effective work habits)

Finally, and with regard to the transversal competence associated with the subject (CT1: third language knowledge), this is worked on from the documentary sources that students must consult, since all of them are in English. Sometimes the statements of some of the practices of the subject are also provided in English (only).

For each activity, teachers will be informed of the particular rules and conditions that govern them.

One-person activities presuppose the student's commitment to carry them out individually and without any collaboration with other people. All activities in which the student does not comply with this commitment to individuality will be considered suspended (grade 0), regardless of their role (sender or receiver) and without this excluding the possible application of other sanctions in accordance. with the current Disciplinary Regime.

Likewise, the activities to be carried out in groups presuppose the commitment on the part of the students who make it up to carry them out within the group and without any kind of collaboration with other groups or people who are alien (group individuality). All activities in which the group has not respected this commitment regardless of its role (sender or receiver) and without this excluding the possible application of other sanctions in accordance with the current Disciplinary Regime will be considered suspended (rating 0).

In the particular case of internships, when in any of them the commitment of individuality is not respected and / or fraudulent means are used in its realization, the qualification of practices (Pr) will be, for all the members of the group, of 0 points (Pr = 0) regardless of the qualification of the other practices and without this excluding the possible application of other sanctions in accordance with the current Disciplinary Regime.

Any undelivered activity will be considered scored with zero points

It is optional for teachers to accept or not deliveries outside the deadlines indicated. In the event that these late deliveries are accepted, it is up to the teacher to decide whether to apply a penalty and the amount thereof.

The final grade of the subject (QF) will be calculated as detailed below

pe1: qualification of the first written test

pe2: qualification of the second written test

Teo: qualification of theory

Pr_i: qualification of the i-th practice

Pr: internship qualification

QPT: weighted qualification theory + practices

QF: final grade of the subject

Teo = max ((Pe1 + Pe2) / 2, Pe2)

Pr = average (Pr_i)

QPT = Pr ·0.35 + Teo ·0.65

QF = Teo and Teo <4

QF = QPT and Teo ≥ 4

It is the student's responsibility to prevent plagiarism in all its forms. In the case of detecting a plagiarism, regardless of its scope, in any activity, it will correspond to have a note of 0. In addition, the professor will communicate to the Head of Studies the situation so that it takes applicable measures in the matter of regime. sanctioning. In the context of this subject, plagiarism also means using and / or adapting code that has not been developed entirely individually (or within the group in the case of group activities). Facilitating the code that leads to plagiarism is also a form of plagiarism and will be treated the same way. In summary, we can say that the evaluation activities must be solved in a strictly non-collaborative way (in the case of group activities, collaboration cannot transcend the heart of the group). 

Recovery

The internship part of the subject (Pr grade) is NOT recoverable.

For students attending the resit exam their Teo grade will be that obtained in this test and their final grade will be calculated using the formulas detailed above and in no case will it exceed 5.

Sesa and Nogueras. EDA: class notes, examples and exercises. Internal publication of the TCM.

Oracle Java Collections Tutorial  https://docs.oracle.com/javase/tutorial/collections/

Java 8 API Documentation. https://docs.oracle.com/javase/8/docs/api/