Programming Algorithms and Data Structures

The aim of this course is that students acquire the following skills: EURO-ACE SKILLS 1. Basic competences CB5: Learning abilities required to undertake later studies with a high degree of autonomy. 2. Transverse and generic competences CGB3. Ability to understand and control basic concepts of Discrete mathematics, Logics, Algorithms and Computational Complexity, and their application for the resolution of problems related to Engineering. 3. Common competences to Computer Science. CECRI6. Knowledge and application of basic algorithms and procedures of Computer Science to design solutions to problems, and analyze the suitability and complexity of the proposed algorithms. CECRI15. Knowledge and application of basic techniques and principles of intelligent systems and their practical application. ABET SKILLS 1.Transverse (Generic) competences - Ability to analyze and synthesize. PO: a,c,e,g - Problem solving. PO: a,c,e - Critical Reasoning. PO: a,c,e,g,h,k - Teamwork PO: g - Written communication. PO: g - Automate processes. PO: a,c,e,h,k 2.Specific competences for Learning a.Cognitive (To Know). PO: a - Understand the theories to describe formal languages. - Understand the concept of formal grammar and their types, as well as the type of language. - Understand the concept of finite automaton as a regular language recognizer. - Understand the concept of regular expression as a description of a regular language. - Understand the concept of a pushdown automata to recognize any context-free language - Understand the relation between grammars, languages and recognizers. - Understand the principles and operation of a Turing Machine and its different types. - Understand the concept of computational complexity. To know the methods to calculate the computational complexity. - Understand the concept of P and NP complexity classes. - Understand the limits of computation b.Procedural - Assess how to address a problem of recognition of words for a certain grammar. PO: c,e,g - Elaborate correctly the phases for the construction of a recognizer, from the description of the grammar to the design of the automaton. PO: a - Combine and extrapolate the acquired knowledge about developing a lexical or syntactic recognizer for a grammar. PO: a,c,e,g,h,k - Skills to assess the efficiency of a given automaton in the task of recognizing a specific, also to discern whether the automaton is minimal or not. PO: a,c,e,g - Practical application of theoretical models of the exposed computation/calculation devices (Grammars, Finite Automata, Pushdown Automata, and Turing machines) for solving problems or arithmetic computation. PO: a,e,g - To know the methods to calculate the computational complexity of an algorithms, an automaton or a Turing machine. PO: a,e,g - Ability to transform a formal statement into a informal statement. PO: a,e,g 3.- Attitude (To be) - Ability to analyze computational problems and its solutions. - Concern on quality.

1.Introduction to the theory of automata and formal languages. 1.1. Why study Automata Theory. History and Origins 1.2. Relationship with others Areas of Knowledge 1.3. Machines, Languages and Algorithms. 2.- Automata Theory 2.1 Introduction and Definitions. 2.2 Mathematical model of an automaton 2.3 Automata and algorithms. 2.4 Discrete, continuous, and hybrid automata. Classes of automata. 3.Finite Automata 3.1 Definition and Representation of Deterministic Finite Automata (DFA) 3.2. DFA as Recognition Device 3.3. Equivalence and Minimization of DFA 3.4. Theorems of DFA 3.5. Definition and Representation of Nondeterministic Finite Automata (NDFA) 3.6. The Language of a NDFA 3.7. Equivalence of DFA and NDFA 4.Languages and Formal Grammars. 4.1. Operations with Words. Operations with Languages. Derivations. 4.2 Concept of Grammar. Formal Grammar. 4.3. Chomsky Hierarchy and Equivalent Grammar 4.4 Context-Free Grammar 4.5. Language of a Context-Free Grammar. Parse Tree 4.6. Well-Formed Grammar 4.7. Chomsky Normal Form. Greibach Normal Form 5.Regular Languages. 5.1. Definition of Regular Languages 5.2. DFA for a Regular Grammar 5.3. Equivalence of Regular Expressions 5.4. Kleene's Theorem 5.5. Characteristic equations 5.6. Synthesis Problem: Recursive Algorithm 5.7. Derivatives of Regular Expressions 6.Pushdown Automata. 6.1. Definition of Pushdown Automata (PDA). 6.2. Transitions, Movement and Instantaneous Description in PDA. 6.3. Acceptance by Empty Stack. Acceptance by Final State. 6.4. Language Accepted by a PDA. Equivalence of PDA by Empty Stack and PDA by Final State. 6.5. From Context-Free Grammar to Push-Down Automata. 6.6. From Pushdown Automata to Context-Free Grammar. 7.Turing Machine. 5.1. Definition if Turing Machine. 5.2. Variations of Turing Machine. 5.3. Universal Turing Machine. 8.Computational Complexity 8.1.Complexity Theory 8.2.Complexity of algorithms 8.3.P versus NP problems 8.4 Defining complexity classes 8.5 Time complexity 8.6 Hierarchy theorems 8.7 Non-computational problems 8.9 Limits of Computability

Theoretical lectures: 1.5 ECTS. PO: a,c,e,g These clases constitute a guide for students to achieve cognitive skills, and acquire the basic elements to develop procedural skills. A part of the ECTS corresponds to the load of autonomous work carried out by the students. Exercices and practical classes (Exercises, Problems and Practices): 2 ECTS. They contribute to the development of the generic competences and the application of the attitude ones. These classes consist on developing and solving practical cases (exercises, problems and practices) which are aimed at achieving the procedural competences. An important part of the ECTS corresponds to the autonomous work of the student. PO: a,c,e,g,h,k Other academic activities - Present teacher: 0.5 ECTS. Resolution of small questions, exercises, and practical work that will compute for the final grade obtained by the students. Part of the ECTS corresponds to a review of the contents of the field carried out by the student. PO: a,c,e,g,h,k - Absent teacher: 1.5 ECTS. Readings about the field as well as exercises, problems and practices related to the theoretical lectures and practical classes. PO: a,c,e,g,h,k Exam: 0.5 ECTS Preparation and realization of the examination, in which the level achieved by the student in relation to the established competences is assessed.