Data Structures and Algorithms

The training objective of this subject is to develop the necessary skills for the student to be able to assess the computational complexity of a given algorithm and develop the skills to choose the most appropriate combination of data structures and resolution strategy to solve efficiently (in terms of space and time resources) a particular problem. In addition, this subject completes the student training in data structures presenting nonlinear data structures and their use to represent and solve complex problems.

Item 1. Problem solving: algorithms + data structures

Item 2. Nonlinear data structures: Trees
* Basic concepts and properties
* Search Trees
* Balanced Search Trees
* Applications

Item 3. Nonlinear data structures: graphs
* Basic concepts and properties
* Fundamental graph algorithms
* Applications

Item 4. Hash tables

Item 5. Algorithmic strategies
* Divide and conquer
* Greedy algorithms
* Dynamic programming
* Backtracking
* Branch and bound

Basic Bibliography:
HEILEMAN, G.L. Estructuras de Datos, Algoritmos y Programación Orientada a Objetos. Madrid: McGraw-Hill, 2001. ISBN 84-481-1173-7.
JOYANES AGUILAR, L., ZAHONERO MARTÍNEZ, I. Algoritmos y Estructuras de Datos: Una perspectiva en C. Madrid: McGraw-Hill, 2010. ISBN 9788448140779.
JOYANES AGUILAR, L. et al. Estructura de Datos. Libro de Problemas. Madrid: McGraw-Hill, 1999. ISBN 84-481-2298-4.
Complementary Bibliography:
BOWMAN, C.F. Algoritmos y Estructuras de Datos. Aproximación en C. Oxford University Press, 2001. ISBN: 978-9706134592.
CAIRÓ, O., GUARDATI BUERMO, S. Estructuras de Datos. México: McGraw-Hill, 2006. ISBN 970-10-3534-8.
MARTÍ OLIET, Narciso, ORTEGA MALLÉN, Yolanda, VERDEJO LÓPEZ, José A.: Estructuras de Datos y Métodos Algorítmicos. Ejercicios resueltos. 2ª edición: 213 ejercicios resueltos. Ibergarceta Publicaciones S.L., 2013. ISBN 978-8415452652.

This subject helps to achieve the following competences, gathered in the description of the Degree in Computer Engineering from the USC, for the module Programming:
- Ability to develop programs with a good programming style, documentation and the appropriate comments.
- Ability to calculate the computational complexity of an algorithm and evaluate the most appropriate implementation of a given algorithm in accordance to the available resources (memory and runtime).
- Use of editing, compiling and executing tools for program development. Ability to implement strategies for the debugging, testing and correction of programs.
- Ability to choose the most correct and efficient data structure to solve a problem.
- Ability to manage different levels of abstraction to structure the software to develop.
- Ability to design algorithms with a certain complexity and deploy applications using the principles of structured and modular programming.
- Ability to understand the concepts related to algorithm development.
- Ability to use error management, exception handling and fault tolerance tools.
- Use of software repositories.
- Motivation and self-learning ability.
- Self-esteem and self-improvement.

In addition, the subject contributes to the development of general and specific skills contained in the relevant tables in the report previously referred to:
* General Skills:
CG1: Ability to develop projects in the field of computer engineering whose purpose, according to the acquired knowledge, is the design, development or exploitation of computer systems, services and applications.
CG3: Ability to design, develop, assess and ensure the usability of computer systems, services and applications, as well as the information that they manage.
CG8: Knowledge of the basic topics and technologies that enable the learning and development of new methods and technologies, as well as those which equip them with great versatility to adapt to new situations.
CG9: Ability to solve problems with initiative, decision making, autonomy and creativity. Ability to communicate and transmit the knowledge, skills, and abilities of the profession in Computer Engineering.
* Cross-curricular skills:
TR1 (Instrumental): Capacity for analysis and synthesis. Ability to organize and plan. Oral and written communication. Ability to manage information. Troubleshooting. Decision making.
TR2 (Personal): Teamwork. Interpersonal relationship skills. Critical thinking.
TR3 (Systemic): Autonomous learning. Adapting to new situations. Creativity. Initiative. Motivation for quality.
* Basic Training:
FB3: Ability to understand and master the basic concepts of algorithmic and computational complexity, and their application for solving problems in engineering.
FB4: Basic knowledge of the using and programming of computers.
FB5: Knowledge of the fundamentals of computer systems programming and their application for solving problems in engineering.
* Common to the branch of Computer Science:
RI6: Knowledge and application of basic algorithmic procedures of computer technology to design solutions to problems, analysing the suitability and complexity of the proposed algorithms.
RI7: Knowledge, design and efficient use of the data types and structures more suited to solving a problem.

The methodology makes use of the Virtual Campus of USC. On the website of the subject, the student will have all the information (material for theory lessons, class slides, practice sessions scripts, TADs libraries, etc.).
Theoretical lectures (20hours) will be given in 1-hour sessions throughout the course. There will be a weekly session of two and a half hours of practical work (problem solving, programming).
The students may at any time to check their progression, since the marks for exercises and projects to be delivered, following the model of continuous assessment, will be provided in a regular basis.
The skills of type FB3, FB4, FB5, RI6, RI7, CG1, CG3, and CG9 CG8 and the indicated module programming content partners have the theoretical and practical part of the course and evaluated explicitly in tests that are performed throughout the course.
The skills of type TR1 is mainly working in the appearance of organizational capacity and planning, decision making and problem solving in the deliveries they have to perform in practical classes.
Skills of TR2 type work mainly critical thinking, evaluating the different possibilities to solve problems, both in theory and in practice.
TR3 group creativity skills, adapting to new situations, and motivation for quality, particularly in practical classes where these skills to develop problems with changing situations are proposed and evaluated in qualifying the work is mainly problem at hand.

The assessment consists of two separate individual parts, theory, and practice, being necessary to pass both parts independently. It will be mandatory to pass all practice modules and all theory tests also.

The practical part of the subject will be assessed through a process of CONTINUOUS EVALUATION:
-30% of the global mark: delivery of practical projects during the term, with timelines and delivery standards / correction pre-set by teachers.
It is used to evaluate the CG1, CG3, CG8, CG9, TR1, TR3, FB4, FB5, RI6 and RI7 skills, in addition to the programming module indicated by periodically delivering practical proposals during the semester.

The theoretical part (70% of the total grade) will be evaluated in two parts:
-10% of the mark: Texts throughout the semester.
-60% of the mark: Global exam at the end of the semester
It is used to evaluate CG8, CG9, TR2, FB3, FB4, FB5, RI6 and RI7 skills, plus the specified in the programming module, using different questions in the theory test and evaluation exercises that are delivered during the semester.

The delivery of any work (project or exercise) after November 1st will imply a qualification of PRESENTED in the final qualification, regardless of attendance or not to the final exam.

RESIT OR 2nd OPPORTUNITY (JULY)
This exam may be taken by students who did not exceed any of the parts in the continuous assessment, or those who directly choose this option of qualifications.
- Theory (70% of the final grade): repetition of failed tests and final written exam.
- Practical (30% of the final grade): development of failed practice modules through new exercises to be delivered before the data of the final exam.

In application of the norm for practical work authorship approved by the ETSE (Xunta de Escola 01/03/2012), total or partial copy of any practical or theoretical exercise will imply a fail in both assessment opportunities (January and July), with a 0,0 mark in both cases.

For students repeating the course: We retain only the results of theoretical or practical assessment that has been surpassed (mark above 6) in the immediately preceding year. Otherwise, students will repeat the entire subject.

The assessment system for students after the course is removed from the teaching offer will be the same as in the resit opportunity.

This subject has 6 ECTS credits, corresponding to a total workload of 150 hours. This time can be broken down into the following sections:
ON-SITE WORK (IN THE CLASSROOM):
* Lectures: 20 hours
* Problem- or case-based learning in small groups: 15 hours
* Programming sessions in small groups: 15 hours
* Assessment activities: 15 hours
Total classroom time: 55 hours
STUDENT'S PERSONAL WORK:
This course has 6 ECTS, corresponding to a student's personal workload of 90 hours. This time can be broken down into the following sections:
* Autonomous study: 35 hours
* Writing exercises, papers, etc.: 15 hours
* Programming / testing in computer: 35 hours
* Evaluation of work, projects, exams: 15 hours
Total personal work time: 95 hours

Sufficient knowledge of C programming language and the fundamentals of graphs is assumed. These topics are dealt with in the subjects Programming I and II, and Discrete Mathematics, all of them corresponding to the first year.
It is recommended to follow the continuous assessment model, requiring that the student attends and follows the theoretical classes and the practical classes regularly, which does the subject more bearable.
It is also earnestly recommended that the student uses the tutorial hours to clarify any doubt that could arise in the development of the subject.

The USC Virtual Campus will be used for all the teaching, publishing of the material, practice scripts and delivery of works.
The operative system to use in practice sessions can be either Windows or Linux.
The software will be basically the IDE Netbeans or CLion with the cygwin C compiler installed for Windows or the gcc compiler for Linux.
The subject will be taught mainly in Spanish.