Identifying Data 2022/23
Subject (*) Design and Analysis of Algorithms Code 614G02011
Study programme
Grao en Ciencia e Enxeñaría de Datos
Descriptors Cycle Period Year Type Credits
Graduate 1st four-month period
 Second Obligatory 6
Language
Spanish
Teaching method Face-to-face
Prerequisites
Department Ciencias da Computación e Tecnoloxías da Información
Coordinador
Hernandez Pereira, Elena Maria
 E-mail
elena.hernandez@udc.es
Lecturers
Cancela Barizo, Brais
Gómez Rodríguez, Carlos
Hernandez Pereira, Elena Maria
Vilares Calvo, David
 E-mail
brais.cancela@udc.es
carlos.gomez@udc.es
elena.hernandez@udc.es
david.vilares@udc.es
Web http://campusvirtual.udc.es
General description Cando se traballa con datos, sobre todo en gran volume, é fundamental que os algoritmos que se utilizan para manipulalos sexan eficientes, tanto para minimizar o uso de recursos como, en ocasións, para garantir a propia viabilidade do procesado. Nesta materia trátanse os fundamentos necesarios tanto para analizar a eficiencia de algoritmos existentes sobre un caso dado, permitindo así elixir o máis adecuado, como para deseñar novos algoritmos. O primeiro enfócase mediante a análise de custo espacial e temporal coa notación O grande. O segundo trátase a través dos diferentes paradigmas xenéricos de deseño de algoritmos, como algoritmos voraces, programación dinámica ou divide e vencerás; ademais dun tratamento máis específico para ámbitos típicos de interese para o científico ou enxeñeiro de datos, como son a procura, ordenación ou a exploración de grafos. Veranse tamén fundamentos de complexidade computacional e algoritmos aproximados para aqueles casos nos que unha implementación eficiente non é viable.

Esta materia pon broche final ao bloque de "Programación e Algoritmos" do Grao, e por iso deberían cursarse anteriormente as materias de Fundamentos de Programación I e II, cuxos conceptos se utilizan aquí. Fóra do bloque, tamén son necesarios os conceptos de Matemática Discreta. Á súa vez, e dado que os algoritmos son pedra angular de calquera procesado de datos, esta materia proporciona conceptos que se usarán en materias posteriores, incluíndo as de Aprendizaxe Automática, Recuperación de Información, Procesamento de Imaxe, Vídeo e Audio, Procesamento da Linguaxe Escrita, Procesamento Paralelo, así como outras posteriores no plan de estudos.

Study programme competencies
Code Study programme competences
A4 CE4 - Coñecemento e aplicación dos fundamentos de programación e técnicas algorítmicas básicas para deseñar solucións a problemas, utilizando as linguaxes de programación máis relevantes no ámbito da ciencia e enxeñaría de datos.
A5 CE5 - Coñecemento de estruturas de datos e algoritmos básicos e capacidade para utilizalos eficientemente na resolución dun problema.
A6 CE6 - Capacidade para deseñar e programar algoritmos robustos e eficientes e saber analizar a idoneidade e complexidade dos mesmos.
B2 CB2 - Que os estudantes saiban aplicar os seus coñecementos ao seu traballo ou vocación dunha forma profesional e posúan as competencias que adoitan demostrarse por medio da elaboración e defensa de argumentos e a resolución de problemas dentro da súa área de estudo
B3 CB3 - Que os estudantes teñan a capacidade de reunir e interpretar datos relevantes (normalmente dentro da súa área de estudo) para emitir xuízos que inclúan unha reflexión sobre temas relevantes de índole social, científica ou ética
B7 CG2 - Elaborar adecuadamente e con certa orixinalidade composicións escritas ou argumentos motivados, redactar plans, proxectos de traballo, artigos científicos e formular hipóteses razoables.
B8 CG3 - Ser capaz de manter e estender formulacións teóricas fundadas para permitir a introdución e explotación de tecnoloxías novas e avanzadas no campo.
B9 CG4 - Capacidade para abordar con éxito todas as etapas dun proxecto de datos: exploración previa dos datos, preprocesado, análise, visualización e comunicación de resultados.
B10 CG5 - Ser capaz de traballar en equipo, especialmente de carácter multidisciplinar, e ser hábiles na xestión do tempo, persoas e toma de decisións.
C1 CT1 - Utilizar as ferramentas básicas das tecnoloxías da información e as comunicacións (TIC) necesarias para o exercicio da súa profesión e para a aprendizaxe ao longo da súa vida.

Learning aims
Learning outcomes Study programme competences
Saber analizar problemas e deseñar, programar e depurar algoritmos que os resolvan utilizando unha linguaxe de programación imperativa. A4
A5
 B2
B9
B10
 C1
Saber elixir e utilizar as estratexias de resolución de problemas máis relevantes. A4
A6
 B2
B3
B7
B8
B9
B10
 C1
Comprender os principios básicos do almacenamento de datos e a súa manipulación. A5
 B2
B8
B9
 C1
Coñecer e saber utilizar as estruturas de datos estándar en computación e os algoritmos máis relevantes para manipulalas. A5
 B2
B8
B9
 C1
Analizar a complexidade espacial e temporal dos algoritmos e recoñecer os aspectos chave da súa ineficiencia. A6
 B2
B3
B7
B8
B9
 C1

Contents
Topic Sub-topic
Análisis do coste de algoritmos Coste espacial e temporal
Regras e limitacións do análisis O
Paradigmas do deseño algorítmico Divide e vencerás
Programación dinámica
Algoritmos voraces
Estructuras de datos, algoritmos básicos e complexidade Procura en memoria principal e secundaria
Ordenación interna e externa
Exploración de grafos
Problemas NP-Completos NP-Completo e NP-Difícil
Heurísticas e algoritmos aproximados

Planning
Methodologies / tests Competencies Ordinary class hours Student’s personal work hours Total hours
Laboratory practice A4 A5 A6 B2 B3 B7 B9 B10 C1 20 36 56
Problem solving A4 A5 A6 B2 B7 B10 C1 10 17.5 27.5
Objective test A4 A5 A6 B2 B3 B8 B9 3 7.5 10.5
Guest lecture / keynote speech A5 A6 B2 B3 B8 B9 30 24 54
 
Personalized attention 2 0 2
 
(*)The information in the planning table is for guidance only and does not take into account the heterogeneity of the students.

Methodologies
Methodologies Description
Laboratory practice Nas prácticas de laboratorio, os alumnos terán que solucionar problemas mediante a implementación e análise de algoritmos nunha linguaxe de alto nivel. As prácticas organizaranse en entregas periódicas para fomentar o estudo continuo e a avaliación continua. Ademais do código fonte, as entregas incluirán informes onde os alumnos deberán expor as conclusións obtidas sobre os algoritmos, en relación cos conceptos da materia, e que serán avaliados xunto cos propios programas entregados.
Problem solving Desenvolveranse exemplos e exercicios nos que os alumnos terán que aplicar os coñecementos teóricos da materia a casos concretos. Garantirase a interactividade, resolvendo dúbidas por parte dos alumnos e animándoos a contrastar as súas solucións e a expor cuestións relevantes. Parte dos problemas realizados serán avaliados.
Objective test Levarase a cabo unha avaliación da materia mediante unha proba que incluirá tanto preguntas sobre os contidos teóricos, como supostos prácticos e exercicios de aplicación relacionados cos distintos temas vistos na materia.
Guest lecture / keynote speech Clases maxistrais onde se exporán os conceptos teóricos da materia, sen perder nunca de vista exemplos de aplicación para motivar e contextualizar os contidos. Fomentarase a interactividade en clase mediante a formulación de preguntas e utilizaranse distintos recursos como encerado, transparencias ou demostracións.

Personalized attention
Methodologies
Problem solving
Laboratory practice
Description
O desenvolvemento, tanto das clases maxistrais coma das de resolución de problemas e os laboratorios de prácticas, realizarase atendendo ao progreso dos alumnos nas capacidades de comprensión e asimilación dos contidos impartidos. O avance xeral da clase compaxinarase cunha atención específica a aqueles alumnos que presenten maiores dificultades na tarefa da aprendizaxe e cun apoio adicional a aqueles outros que presenten maior desenvoltura e desexen ampliar coñecementos.

No que respecta ás titorías individuais, dado o seu carácter personalizado, non deben dedicarse a estender os contidos con novos conceptos, senón a aclarar os conceptos xa expostos. O profesor utilizaraas como unha interacción que lle permita extraer conclusións respecto ao grao de asimilación da materia por parte dos alumnos.

Assessment
Methodologies Competencies Description Qualification
Problem solving A4 A5 A6 B2 B7 B10 C1 Valoraránse os resultados, forma e condicións de realización de diversos traballos puntuables que se detallarán durante o curso. 20
Laboratory practice A4 A5 A6 B2 B3 B7 B9 B10 C1 Realizadas segundo as condicións establecidas no enunciado de cada práctica. A entrega en tempo e forma das prácticas é condición necesaria para aprobar a materia na primeira oportunidade. 20
Objective test A4 A5 A6 B2 B3 B8 B9 Realización obrigatoria. Avaliarase o dominio dos coñecementos teóricos e operativos da materia. 60
 
Assessment comments

Traballos prácticos e solución de problemas

- Dado que se trata de actividades de avaliación continua, non se reavaliarán nin se admitirán entregas na segunda oportunidade. As cualificacións dos traballos prácticos e solución de problemas da primeira oportunidade conservaranse para a segunda oportunidade. 

- De acordo
ao artigo 14, apartado 4, da normativa*,a realización fraudulenta das probas ou actividades de avaliación,
unha vez comprobada, implicará directamente a cualificación de suspenso
"0" na materia na convocatoria correspondente, invalidando así calquera
cualificación obtida en todas as actividades de avaliación de cara a
convocatoria extraordinaria.

- Se as probas ou actividades de avaliación se realizaren en grupo, todos os membros do grupo
responderán de forma solidaria do traballo realizado e entregado e das
súas posibles consecuencias.

Matrícula a tempo parcial

-
Os alumnos matriculados a tempo parcial terán que entregar as
actividades avaliables nas condicións e prazos específicos que se
establecerán. Será obriga do estudante comunicar a súa situación ao
profesorado.

Non presentado

- Quen non concurra á proba obxectiva no período oficial de avaliación terá a condición de “Non presentado” (NP). Na primeira oportunidade, esto será extensible a quen non entregue todas as prácticas en tempo e forma.


*
Normativa de avaliación, revisión e reclamación das cualificacións dos
estudos de grao e máster universitario, aprobada polo Consello de
Goberno da Universidade da Coruña o 19 de decembro de 2013.


Sources of information
Basic Goodrich, Michael T. (2013). Data structures and algorithms in Python. John Wiley and Sons
Brassard, G., Bratley, P. (1996). Fundamentals of Algorithmics. Prentice Hall

Complementary Bhargava, Aditya (2018). Algoritmos : una guía ilustrada para programadores y curiosos. Anaya Multimedia
Cormen, Thomas H. (2009). Introduction to Algorithms. The MIT Press
Fortnow, Lance (2013). The golden ticket: P, NP, and the search for the impossible. Princeton University Press


Recommendations
Subjects that it is recommended to have taken before
Discrete Mathematics/614G02002
Fundamentals of Programming II/614G02009
Fundamentals of Programming I/614G02004

Subjects that are recommended to be taken simultaneously

Subjects that continue the syllabus
Written Language Processing/614G02029
Parallel Processing/614G02023
Information Retrieval/614G02027
Image, Video and Audio Processing/614G02028
Machine Learning I/614G02019

Other comments


(*)The teaching guide is the document in which the URV publishes the information about all its courses. It is a public document and cannot be modified. Only in exceptional cases can it be revised by the competent agent or duly revised so that it is in line with current legislation.