Algorithm Design26212
- Centre
- Faculty of Science and Technology
- Degree
- Bachelor's Degree In Mathematics
- Academic course
- 2024/25
- Academic year
- 4
- No. of credits
- 6
- Languages
- Spanish
- Code
- 26212
TeachingToggle Navigation
Teaching guideToggle Navigation
Description and Contextualization of the SubjectToggle Navigation
Esta asignatura se imparte sólo en castellano.
The main objective of the course is to study the principles of the algorithm design. Students will learn the main goal and functionality of each proposed technique for problem solving. Its general scheme, common implementations, the involved computational resources as well as their applications will be studied.
The starting points are the basic computation knowledge and programming skills acquired so far during the grade course, particularly, but not only, in the first-year subjects "Introduction to Computing" and "Programming Foundations". In this framework, the foundations of algorithm design are introduced using an algorithmic language. Comparative analyzes are performed based on specifications, costs and constraints. In addition, effective implementations of the techniques presented are also studied. The computer analysis of resrouces really used will also be carried out.
The expertise and skills acquired in this course will support the student in the computer resolution of any algorithmic problem arising in the other subjects.
Skills/Learning outcomes of the subjectToggle Navigation
COMPETENCIES
M09CM07 - To select the most appropriate algorithm design techniques for solving each problem.
M09CM08 - To study the computational costs of algorithms.
M09CM09 - To propose valid alternatives based on the problem specifications and / or on the limitations on the algorithms.
M09CM10 - To propose effective implementations.
LEARNING OUTCOMES
The student must know the fundamental methods of algorithm design and be able to choose the appropriate algorithmic techniques for solving the proposed problems, as well as carry out comparative analysis based on specifications and objectives. He/she must also be capable of designing efficient implementations as well as estimating and analyzing their computational costs. The students must also be able to perform analyses of real costs on a computer. Finally, they must communicate ideas and results related to the subject both orally and in writing.
Theoretical and practical contentToggle Navigation
1. INTRODUCTION: efficiency of algorithms, spatial and temporal complexities, analysis of recursive algorithms, review of basic techniques.
2. STATE-SPACE SEARCH ALGORITHMS: general schema, Depth First Search, Backtracking, Branch and Bound.
3. INFORMED SEARCH: heuristics and evaluation functions, optimal search, A* algorithm.
4. GREEDY ALGORITHMS: general schema, Prim algorithm, Kruskal algorithm, Dijkstra algorithm, applications to technological problems.
5. DYNAMIC PROGRAMMING: general recursive and iterative schemas, Principle of Optimality, Minimum Paths, Applications to technological problems.
COMPUTER PRACTICES
P0.- Selection and verification of the programming environment
P1.- Analysis of Iterative and recursive algorithms.
P2.- Depth first search (backtracking); branch and bound
P3.- Decision algorithms in zero-sum games.
P4.- Optimization problems: A* algorithm, greedy algorithms and dynamic programming.
MethodologyToggle Navigation
The theoretical content will be exposed in master classes that follow basic references that appear in the Bibliography and in the material of obligatory use. These master classes will be complemented with problem classes (classroom practices) in which students will be asked to solve questions and exercises and thus the knowledge acquired in the theoretical classes will be applied. In the seminars, the students will make presentations of questions and examples related to the content of the course. In addition, there will be computer practices aimed at achieving the practical skills defined in the subject.
Assessment systemsToggle Navigation
- Continuous Assessment System
- Final Assessment System
- Tools and qualification percentages:
- . (%): 100
Ordinary Call: Orientations and DisclaimerToggle Navigation
Continuous assessment:
- Presentations in Seminars: 15%
- Algorithmic resolution of proposed problems: individual exercises to be delivered along with a written exam (15%) and a final exam (45%).
- Individual Practice Work (Computer Practices): reports to be delivered and an additional verification on the computer 25%
A minimum score of 4/10 is required at each evaluation element.
Final Evaluation in the Ordinary Call:
- Algorithmic resolution of proposed problems (exam): 75%
- Individual Practice Work (Computer Practices): reports to be delivered and an additional verification on the computer 25%
A minimum score of 4/10 is required at each evaluation element.
If the sanitary conditions recommend to remove in-person exams then distance procedures will be activated. Students will be informed through the eGela platform.
Extraordinary Call: Orientations and DisclaimerToggle Navigation
Final Evaluation in the Extraordinary Call:
- Algorithmic resolution of proposed problems (exam): 75%
- Individual Practice Work (Computer Practices): reports to be delivered and an additional verification on the computer 25%
A minimum score of 4/10 is required at each evaluation element.
If the sanitary conditions recommend to remove in-person exams then distance procedures will be activated. Students will be informed through the eGela platform.
Compulsory materialsToggle Navigation
Phyton programming language.
Course slides and some basic books.
BibliographyToggle Navigation
Basic bibliography
- Gilles Brassard, Paul Bratley. Fundamentos de algoritmia. Prentice-Hall, 2006.
- Ian Parberry. Problems on Algorithms (Second Edition). Prentice Hall, 2002.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorit ms (Third Edition). The MIT Press, 2009.
- Ellis Horowitz, Sartaj Sahni, and Sanguthevar Rajasekaran. Computer algorithms (second Edition). Universities Press, 2007.
- Francesc J. Ferri, Jesús v. Albert, Gregorio Martín, Introducció a l'anàlisi i disseny d'algorismes, Universitat de Valencia, 1998
- Robert Sedgewick an Kevin Wayne: Algorithms (Fourth Edition).
- Steven S. Skiena. The Algorithm Design Manual (Second Edition). Springer, 2008.
In-depth bibliography
- Jason Brownlee: Clever Algorithms: Nature-Inspired Programming Recipes. lulu.com, 2012
- Weixiong Zhang: State-Space Search. Algorithms, Complexity, Extensions and Applications. Springer 1999,
- Bo Xing and Wen-Jing Gao. Innovative Computational Intelligence: A Rough Guide to 134 Clever Algorithms. Springer 2014.
Web addresses
- Wikipedia (English version) [en.wikipedia.org]
- Clever Algorithms: http://www.cleveralgorithms.com/nature-inspired/index.html
- Algorithm language in Latex
- Algorithm2e: http://www.ctan.org/pkg/algorithm2e
- Use of Algorithm2e in Spanish: http://tex.stackexchange.com/questions/146050/how-to-write-pseudo-code-in-other- languages-spanish
- Python Programming Language
- Official Website: http://python.org/
- The Python Tutorial: https://docs.python.org/3/tutorial/
- Python 3 documentation: https://docs.python.org/3/
- Problem Solving with Algorithms and Data Structures Using Python
- Official Website: http://interactivepython.org/runestone/static/pythonds/index.html
GroupsToggle Navigation
01 Teórico (Spanish - Mañana)Show/hide subpages
Weeks | Monday | Tuesday | Wednesday | Thursday | Friday |
---|---|---|---|---|---|
16-30 | 09:30-10:30 (1) | 09:30-10:30 (2) |
01 Seminar-1 (Spanish - Mañana)Show/hide subpages
Weeks | Monday | Tuesday | Wednesday | Thursday | Friday |
---|---|---|---|---|---|
19-28 | 08:30-09:30 (1) |
01 Applied classroom-based groups-1 (Spanish - Mañana)Show/hide subpages
Weeks | Monday | Tuesday | Wednesday | Thursday | Friday |
---|---|---|---|---|---|
16-19 | 08:30-09:30 (1) | ||||
21-29 | 08:30-09:30 (2) | ||||
30-30 | 08:30-09:30 (3) |
01 Applied computer-based groups-1 (Spanish - Mañana)Show/hide subpages
Weeks | Monday | Tuesday | Wednesday | Thursday | Friday |
---|---|---|---|---|---|
16-16 | 15:00-16:00 (1) | ||||
17-29 | 15:00-17:00 (2) |