Programming II

• Teachers
• Weekly hours
• Competences
• Objectives
• Contents
• Activities
• Teaching methodology
• Evaluation methodology
• Bibliography
• Web links
• Previous capacities

Teachers

Person in charge

• Borja Valles Fuente ( )
• Guillem Godoy Balil ( )
• Juan Luis Esteban Ángeles ( )

Others

• Albert Calvo Ibañez ( )
• Alejandro Ivan Paz Ortiz ( )
• Alfonso Valverde Ruiz ( )
• Jorge Castro Rabal ( )
• Jose Carmona Vargas ( )
• M. Luisa Bonet Carbonell ( )
• Maria Josefina Sierra Santibañez ( )
• Pau Fernandez Duran ( )
• Santiago Marco Sola ( )
• Xavier Messeguer Peypoch ( )

Weekly hours

Competences

Transversal Competences

Teamwork

• G5 [Avaluable] - To be capable to work as a team member, being just one more member or performing management tasks, with the finality of contributing to develop projects in a pragmatic way and with responsibility sense; to assume compromises taking into account the available resources.
  • G5.1 - Capacity to collaborate in a unidisciplinary environment. To identify the objectives of the group and collaborate in the design of the strategy and the working plan to achieve them. To identify the responsibilities of each component of the group and assume the personal compromise of the assigned task. To evaluate and present the own results. To identify the value of the cooperation and exchange information with the other components of the group. To exchange information about the group progress and propose strategies to improve its operation.

Technical Competences

Common technical competencies

• CT1 - To demonstrate knowledge and comprehension of essential facts, concepts, principles and theories related to informatics and their disciplines of reference.
  • CT1.1A - To demonstrate knowledge and comprehension about the fundamentals of computer usage and programming, about operating systems, databases and, in general, about computer programs applicable to the engineering.
  • CT1.1B - To demonstrate knowledge and comprehension about the fundamentals of computer usage and programming. Knowledge about the structure, operation and interconnection of computer systems, and about the fundamentals of its programming.
  • CT1.2B - To interpret, select and value concepts, theories, uses and technological developments related to computer science and its application derived from the needed fundamentals of mathematics, statistics and physics. Capacity to understand and dominate the physical and technological fundamentals of computer science: electromagnetism, waves, circuit theory, electronics and photonics and its application to solve engineering problems.
• CT3 - To demonstrate knowledge and comprehension of the organizational, economic and legal context where her work is developed (proper knowledge about the company concept, the institutional and legal framework of the company and its organization and management)
  • CT3.6 - To demonstrate knowledge about the ethical dimension of the company: in general, the social and corporative responsibility and, concretely, the civil and professional responsibilities of the informatics engineer.
• CT4 - To demonstrate knowledge and capacity to apply the basic algorithmic procedures of the computer science technologies to design solutions for problems, analysing the suitability and complexity of the algorithms.
  • CT4.1 - To identify the most adequate algorithmic solutions to solve medium difficulty problems.
  • CT4.2 - To reason about the correction and efficiency of an algorithmic solution.
• CT5 - To analyse, design, build and maintain applications in a robust, secure and efficient way, choosing the most adequate paradigm and programming languages.
  • CT5.1 - To choose, combine and exploit different programming paradigms, at the moment of building software, taking into account criteria like ease of development, efficiency, portability and maintainability.
  • CT5.2 - To know, design and use efficiently the most adequate data types and data structures to solve a problem.
  • CT5.3 - To design, write, test, refine, document and maintain code in an high level programming language to solve programming problems applying algorithmic schemas and using data structures.
  • CT5.4 - To design the programs¿ architecture using techniques of object orientation, modularization and specification and implementation of abstract data types.
• CT8 - To plan, conceive, deploy and manage computer projects, services and systems in every field, to lead the start-up, the continuous improvement and to value the economical and social impact.
  • CT8.6 - To demonstrate the comprehension of the importance of the negotiation, effective working habits, leadership and communication skills in all the software development environments.

Objectives

1. To design a class of data with a clear independence between specification and implementation. To justify why an object of the class can only be created, consulted or modified using the operations in the class specification.
   Related competences: CT5.4, CT5.3, CT1.1B, CT1.1A,
2. To solve any exercise which requires the application of a simple algorithm to a vector of objects of a class of data in C++.
   Related competences: CT4.1, CT4.2, CT5.2, CT5.4, CT5.3,
3. Given an implementation for a simple class of data, make improvements in its representation and its operations.
   Related competences: CT5.2, CT5.4, CT5.1, CT5.3, CT1.2B,
4. To explain the main stages of modular design.
   Related competences: CT5.4, CT5.1, CT5.3, CT1.1B, CT1.1A,
5. To identify in a textual statement of a problem data abstractions that may be represented by classes of data which could be used to solve the problem. To check whether any of the abstractions identified has been previously detected, in order to reuse the corresponding class of data.
   Related competences: CT5.2, CT5.4, CT5.1, CT5.3,
6. To individually design a modular program in C++ from the data abstractions identified by analysing the statement of a problem. To modify or add some functionality to a given modular program written in C++.
   Related competences: CT3.6, CT4.1, CT4.2, CT5.2, CT5.4, CT5.3, CT1.2B, CT1.1A,
7. To implement a modular program in C++ elegantly and in such a way that other programmers can understand what it does and modify it. To write documentation that facilitates the use of a modular program written in C++ by other programmers.
   Related competences: CT8.6, CT3.6, CT5.4, CT5.3,
8. Prepare a C++ program which uses simple data types and C++ classes (some of the predefined and others defined by the student) to be executed. Thw student should be able to do this in two ways: 1) compiling and linking the program using the g++ command; and 2) writing a makefile file, and using it to compile and link the program.
   Related competences: CT1.1B, CT1.1A,
9. To design in teams a modular program in C++ and/or a set of cases (i.e. a set of examples of correct input and corresponding output) to test the full functionality of the program. To debug this program systematically, so that small implementation errors are removed in a reasonable period of time.
   Related competences: CT8.6, G5.1, CT3.6, CT5.3,
10. To know the data types typically used to represent and manage linear data structures and their specification. To design iterative and recursive algorithms for solving search and traversal problems on stacks, queues and lists, using the operations of the corresponding data type and iterators (when appropriated).
    Related competences: CT4.1, CT4.2, CT5.2, CT1.1A,
11. To know data types used to represent and manage tree data structures and their specification. To design recursive algorithms for solving search and traversal problems about binary, n-ary and general trees, using the operations of the corresponding data type.
    Related competences: CT4.1, CT4.2, CT5.2, CT1.1A,
12. To describe the main steps in the design of iterative algorithms. To justify the correctness of relatively simple iterative algorithms.
    Related competences: CT3.6, CT4.2, CT5.3, CT1.1A,
13. To describe the main steps in the design of recursive algorithms. To justify the correctness of relatively simple recursive algorithms.
    Related competences: CT3.6, CT4.2, CT5.3, CT1.1A,
14. To know what a generalization of a function is, and to be able to explain the difference between specification gneralisations and efficiency generalisations. To know the different types of specification generalizations and the different types of efiiciency generalisations.
    Related competences: CT4.2, CT5.3, CT1.1A,
15. Given a simple recursive algorithm, to determine whether there is a straightforward way to obtain an equivalent iterative algorithm, and write it if there exists such a straightforward transformation.
    Related competences: CT4.2, CT5.3, CT1.1A,
16. To distinguish whether the cost of a given iterative or recursive simple algorithm which works on vectors, stacks, queues, lists or trees is linear or if it is quadratic (assuming that the cost is of one of these two types).
    Related competences: CT4.1, CT4.2, CT5.2, CT1.1A,
17. To determine if the efficiency of a given simple recursive algorithm can be improved and, if it is possible, to design a more efficient recursive algorithm that solves the same problem using efficiency generalizations.
    Related competences: CT4.1, CT4.2, CT5.2, CT1.1A,
18. To determine if the efficiency of a given simple iterative algorithm can be improved and, if it is possible, to design a more efficient iterative algorithm that solves the same problem.
    Related competences: CT4.1, CT4.2, CT5.2, CT1.1A,
19. To implement a data structure with specific requirements for its operations and/or the efficiency of such operations, using recursive data types (linked data structures).
    Related competences: CT4.1, CT4.2, CT5.2, CT5.4, CT1.1A,
20. To design iterative and recursive algorithms for solving search and traversal problems in linked data structures by using directly their representation.
    Related competences: CT4.1, CT4.2, CT5.2, CT5.4, CT1.1A,
21. To distinguish the roles of user, specifier and implementer of data classes. To know the main components of the specification of a class of data. To know the main components of the implementation of a class of data.
    Related competences: CT8.6, CT5.4, CT1.1B, CT1.1A,

Contents

1. Linear data structures
   Stacks, queues, lists, maps and sets: specification and use (search and traversal operations). Iterators: definition and use.
2. Tree data structures
   Binary trees.
3. Iterative program correctness
   Loop invariants. Justification of the correctness of iterative algorithms.
4. Recursive programming and correctness of recursive algorithms
   Inductive design of recursive algorithms. Justification of the correctness of recursive algorithms. Generalisation of a function . Specification immersions by weakening the postcondition and strengthening the precondition. Relationship between tail-recursive algorithms and iterative algorithms.
5. Efficiency enhancements for recursive and iterative programs
   Detection of repeated calculations in recursive and iterative programs. Efficiency generalisations: new data (input parameters) and/or results (return values or output parameters) in recursive operations to improve efficiency. New local variables that use their previous values in iterative operations to improve efficiency.
6. Modular design and object-oriented design
   Abstraction and the need for abstraction. Functional and data decomposition. Modules. Information hiding. Encapsulation. Modular design phases: difference between specification and implementation. Types of modules and their use. Libraries.
   
   Basic principles of object-oriented design: classes and objects; fields and methods.
   
   Implementing modular designs in C++. Separate compilation and linking. Debugging, testing and documentation of modular programs.
7. Recursive data types
   Introduction to the use of recursive data types. Pointer type constructor and dynamic memory management. Implementation of linked data structures by means of recursive data types. Iterative and recursive algorithms for solving search and traversal problems in linked data structures by directly accessing the representation based on nodes and node pointers.

Activities

Activity Evaluation act

Teaching methodology

Evaluation methodology

Bibliography

Basic:

• Apunts de teoria de PRO2 - Alquezar, René; Valles, Borja; [et al.],
  http://www.lsi.upc.es/~pro2/index.php?id=material-docent
• Sessions de Laboratori de PRO2 - Valles, Borja; [et al.],
  http://www.lsi.upc.es/~pro2/index.php?id=material-docent
• Iniciació a la Programació (notes de curs) - Cortadella, Jordi; Rubio, Albert; Valentin, Luis, 2001.
  http://www.lsi.upc.es/~pro2/index.php?id=material-docent
• Data structures and problem solving using C++ - Weiss, M.A, Pearson Education International, 2003. ISBN: 0321205006
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991002579369706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• STL tutorial and reference guide: C++ programming with the standard template library - Musser, D.R.; Derge, G.J.; Saini, A, Addison-Wesley publishing company, 2000. ISBN: 0201379236
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991003780719706711&context=L&vid=34CSUC_UPC:VU1&lang=ca

Complementary:

• Curs de programació - Castro, J. [et al.], McGraw-Hill , 1992. ISBN: 844810031X
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991000672229706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Programación metódica - Balcazar, J.L, McGraw-Hill , 1993. ISBN: 8448119576
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991000866429706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Problem solving with C++ - Savitch, Walter J; Mock, Kenrick, Pearson , [2018]. ISBN: 9780134448282
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004158189706711&context=L&vid=34CSUC_UPC:VU1&lang=ca

Web links

• Curs de C++. Ideal com a manual de referència. http://c.conclase.net/curso/index.php
• Manual de referència sobre els containers de la llibreria STL de C++. http://www.cplusplus.com/reference/stl/
• Pàgina web dels professors de l'assignatura. Conté tota la documentació rellevant: apunts, col·leccions d'exercicis, enunciat de la pràctica. http://www.cs.upc.edu/~pro2

Previous capacities