Course: 2020/2021

Algorithms and data structures

(13873)

Students are expected to have completed

- Programming
- Calculus

Competences and skills that will be acquired and learning results. Further information on this link

Competences
CECRI1 (1 ECTS) Evidence Assessment: LAB CASE
CECRI6 (Algorithms) (1.5 ECTS) Evidence Assessment: TESTING, LAB CASE, GROUP AND INDIVIDUAL WORK
CECRI7 (TYPES AND DATA STRUCTURES) (2.5 ECTS) Evidence Assessment: TESTING, LAB CASE, GROUP AND INDIVIDUAL WORK
CGB4 (0.50 ECTS) Evidence Assessment: TESTING, LAB CASE
GGB5 (0.50 ECTS) Evidence Assessment: LAB CASE
- Capacity to analyze and synthesize (PO e).
- Capacity to organize and plan the work (PO d).
- Resolution of problems (PO e).
- Working as a team (PO d).
- Capacity to put in practice theory knowledge (PO e).
2. Specific Competences.
a. Cognitive (to know).
- General knowledge about algorithms (PO a).
- Understanding of basic data structures (PO k).
- Familiarity with advanced data structures (PO k).
b. Procedural/instrumental (to be able to do).
- To be able to design and analyze the algorithms complexity (PO a).
- To be able to understand and use different data structures (PO k).
- To be able to implement program solutions to specific problems using these tools (PO e).
c. Attitude (Being)
- Ability to solve problems through algorithms (PO e).
- Ability to clarify, simplify and efficiency of solving problems (PO e and k).
- Ability to question and conclude various solutions to any problem (PO e and k).
The learning outcomes are:
- Resolution by students of problems that must prove they have the ability to combine theory and practice. (PO a, e, k)
- Implementation and design of a data structures and their algorithms to develop a lab case (PO a, d, e, k)

Description of contents: programme

1. Introduction to Abstract Data Type
2. Linear Abstract Data Types
b. Stacks
c. Queues.
d. Singly and doubly linked lists
3. Analysis of Algorithms.
a. Empirical Analysis.
b. Theoretical Analysis. Big-O functions. Best and worst cases.
4. Recursion I.
5. Trees
a. General concepts
b. Binary Trees
c. Tree Traversals
d. Search Binary Trees.
e. How to balance a tree.
6. Graphs
a. Implementations
d. Graph trasversals.
e. Dijkstra's algorithm (shortest path)
7. Recursion II: Divide and Conquer

Learning activities and methodology

1. Theory Lectures with the objective of acquire the cognitive specific competences (PO a and k).
2. Academic activities guided by the teacher:
2.1. With the teacher: to solve exercises devoted to analyze, design and implement cases with different level of complexity in collaboration with students (PO a and k). Some of the exercises will be carried out in computer laboratories (PO k).
2.2. Student work: Homework, individually or cooperatively, with exercises, implementation cases and basic readings from bibliography proposed by the teacher (PO k and e).
Moreover, these activities can be performed as:
a. Individual work consisting on developing solutions to the problems and exercises posed by the teacher.
b. Working cooperatively developing solutions to the problems proposed by the teacher (PO d).
3. Mid-term partial exams and final exam (PO a, e, k).
4. There will be a group tutorship for each small group to solve the queries and doubts of students.

Assessment System

- % end-of-term-examination 40
- % of continuous assessment (assigments, laboratory, practicals...) 60

Basic Bibliography

- Karumanchi, N. Data Structure and Algorithmic Thinking with Python: Data Structure and Algorithmic Puzzles. . CareerMonk Publications. 2015
- Michael T. Goodrich and Roberto Tamassia. Data Structures and Algorithms in Python, . John Wiley & Sons. 2013

- Isabel Segura Bedmar, Harith AlJumaily, Julian Moreno Schneider, Juan Perea & Nathan D. Ryan · ALGORITHMS AND DATA STRUCTURES : http://ocw.uc3m.es/ingenieria-informatica/algorithms-and-data-structures

Additional Bibliography

- Isabel Segura Bedmar, Harith AlJumaily, Julian Moreno Schneider, Juan Perea & Nathan D. Ryan. Algorithms and Data Structures. OCW-UC3M: http://ocw.uc3m.es/ingenieria-informatica/algorithms-and-data-structures. 2011

(*) Access to some electronic resources may be restricted to members of the university community and require validation through Campus Global. If you try to connect from outside of the University you will need to set up a VPN