Programming II

Credits
7.5
Types
Compulsory
Requirements
This subject has not requirements, but it has got previous capacities
Department
CS
In this course, modular design and object-oriented design are introduced, using C++ programming language; new data structures are presented, both linear (stacks, queues, lists) and hierarchical (binary, n-ary and general trees); iterative design and recursive design are studied in depth, emphasizing the importance of reasoning about the correctness of a given design, and the detection and improvement of ineficient solutions; finally, implementations of linear and tree data structures are presented, using recursive data types.

Teachers

Person in charge

  • Borja Valles Fuente ( )
  • Conrado Martínez Parra ( )

Others

  • Fernando Orejas Valdés ( )
  • Jordi Delgado Pin ( )
  • Juan Luis Esteban Ángeles ( )
  • Lluis Vila Grabulosa ( )
  • M. Luisa Bonet Carbonell ( )
  • Maria Josefina Sierra Santibañez ( )
  • René Alquezar Mancho ( )
  • Ricard Gavaldà Mestre ( )
  • Xavier Messeguer Peypoch ( )

Weekly hours

Theory
2
Problems
0
Laboratory
3
Guided learning
0.5
Autonomous learning
6.8

Competences

Transversal Competences

Teamwork

  • G5 - 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 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,
  2. 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,
  3. 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,
  4. 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,
  5. To explain the main stages of modular design.
    Related competences: CT5.4, CT5.1, CT5.3, CT1.1B, CT1.1A,
  6. 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,
  7. 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,
  8. 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,
  9. 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,
  10. 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,
  11. 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,
  12. 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,
  13. 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,
  14. 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,
  15. 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,
  16. 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,
  17. 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,
  18. 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,
  19. 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,
  20. 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,
  21. 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,

Contents

  1. 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.
  2. Linear data structures
    Stacks, queues and lists with a point of interest: specification and use (search and traversal operations). Iterators: definition and use.
  3. Tree data structures
    Binary, n-ary and general trees: specification. Use of binary trees: search and traversal operations.
  4. Iterative program correctness
    Loop invariants. Justification of the correctness of iterative algorithms.
  5. 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.
  6. 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.
  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


Introduction to modular design and object-oriented design.

Development of the corresponding topic.
  • Theory: Theory sessions weeks 1 and 2
Objectives: 1 2 3
Contents:
Theory
4h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
4h

C++ review exercises.

Link to PRO1 contents.
  • Laboratory: Laboratory session week 1
Objectives: 3 9
Contents:
Theory
0h
Problems
0h
Laboratory
3h
Guided learning
0h
Autonomous learning
3h

Specification and use of classes of objects in C++.

Exercises from the corresponding topic.
  • Laboratory: Laboratory sessions weeks 2 and 3
Objectives: 1 2 3
Contents:
Theory
0h
Problems
0h
Laboratory
6h
Guided learning
0h
Autonomous learning
6h

Implementing classes of objects in C++.

Exercises from the corresponding topic.
  • Laboratory: Laboratory session week 4
Objectives: 1 2 4
Contents:
Theory
0h
Problems
0h
Laboratory
3h
Guided learning
0h
Autonomous learning
3h

Example of modular design 1

An exercise on the corresponding topic.
  • Laboratory: Laboratory session week 5
Objectives: 1 2 5 6 7 8 9
Contents:
Theory
0h
Problems
0h
Laboratory
3h
Guided learning
0h
Autonomous learning
3h

Linear data structures.

Development of the corresponding topic and laboratory exercises.
  • Theory: Theory session week 3.
  • Laboratory: Laboratory session week 6 and first hour of laboratory session week 7
Objectives: 11
Contents:
Theory
2h
Problems
0h
Laboratory
4h
Guided learning
0h
Autonomous learning
6h

Tree data structures.

Development of the corresponding topic and laboratory exercises.
  • Theory: Theory session week 4.
  • Laboratory: Last two hours of laboratory session in week 7.
Objectives: 12
Contents:
Theory
2h
Problems
0h
Laboratory
2h
Guided learning
0h
Autonomous learning
4h

Iterative program correctness

Development of the corresponding topic.
  • Theory: Theory session week 5.
Objectives: 13
Contents:
Theory
2h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
2h

Example of modular design 2

An exercise on the corresponding topic.
  • Laboratory: Laboratory session week 8
Objectives: 1 2 5 6 7 8 9
Contents:
Theory
0h
Problems
0h
Laboratory
3h
Guided learning
0h
Autonomous learning
3h

Delivery of the specification for the practical

The students will deliver a document with the specification of their solution to the practical.
  • Laboratory: Laboratory session week 9.
Objectives: 1 2 5 6 7 8
Contents:
Theory
0h
Problems
0h
Laboratory
3h
Guided learning
0h
Autonomous learning
6h

Recursive programming

Development of the corresponding topic.
  • Theory: Theory session week 6 and first hour of theory session week 7.
Objectives: 15 16 14
Contents:
Theory
3h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
3h

Example of modular design 3 + Review of the specification for the practical

An exercise on the corresponding topic.
  • Laboratory: Laboratory session week 10
Objectives: 1 2 5 6 7 8 9
Contents:
Theory
0h
Problems
0h
Laboratory
3h
Guided learning
0h
Autonomous learning
5h

Efficiency enhancements for recursive and iterative programs.

Development of the corresponding topic.
  • Theory: Second hour of theory session week 7 and theory session week 8.
Objectives: 13 15 16 17 18 14 19
Contents:
Theory
3h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
3h

Supervision of practical 1

Supervision of the design and implementation of the practical.
  • Laboratory: Laboratory session week 11.
Objectives: 11 12 17 18 1 2 4 6 7 8 9
Contents:
Theory
0h
Problems
0h
Laboratory
3h
Guided learning
0h
Autonomous learning
7h

Supervision of practical 2

Supervision of the design and implementation of the practical.
  • Laboratory: Laboratory session week 12.
Objectives: 11 12 17 18 1 2 4 6 7 8 9 10
Contents:
Theory
0h
Problems
0h
Laboratory
3h
Guided learning
0h
Autonomous learning
7h

Recursive data types.

Development of the corresponding topic.
  • Theory: Theory sessions weeks 9, 10, 11, 12 and 13
  • Laboratory: Laboratory sessions weeks 13 and 14
Objectives: 17 18 20 21 2 4 19
Contents:
Theory
10h
Problems
0h
Laboratory
6h
Guided learning
0h
Autonomous learning
16h

Review of theory and exam problems.

Questions can be asked about the topics covered in theory classes.
  • Theory: Theory session week 14.
  • Autonomous learning: Solve past exam problems

Theory
2h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
2h

Consolidation

Consolidation (week 15)
  • Theory: Theory session week 15
  • Guided learning: Final exam
  • Autonomous learning: Final exam study
Objectives: 11 12 13 15 16 17 18 20 21 14 19
Contents:
Theory
2h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
6h

C

Mid-term laboratory exam
Objectives: 1 2 3 4 8 9
Week: 6 (Outside class hours)
Type: lab exam
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
1h
Autonomous learning
1h

ESP_PRAC

Specification of the most important classes and main program of the programming project.
Objectives: 1 2 5 6 7 8
Week: 9 (Outside class hours)
Type: assigment
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
1h

EX_PAR1_TP

Mid-term theory/problems exam.
Objectives: 11 12 13 15 16 17 18 1 2 3 4 6 7 8 9 14 19
Week: 10 (Outside class hours)
Type: theory exam
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
2h
Autonomous learning
2h

CODI_DOC_PRAC

Delivery of the programming project code and documentation.
Objectives: 11 12 13 15 17 18 1 2 6 7 8 9 10 14 19
Week: 12 (Outside class hours)
Type: assigment
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
2h

EX_PRAC

Programming project exam.
Objectives: 11 12 13 15 16 17 18 1 2 3 4 6 7 8 9 14 19
Week: 13 (Outside class hours)
Type: lab exam
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
2h
Autonomous learning
2h

EX_PAR2_TP

Final theory/problems exam.
Objectives: 11 12 13 15 16 17 18 20 21 1 2 3 4 6 7 8 9 14 19
Week: 15 (Outside class hours)
Type: final exam
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
2h
Autonomous learning
2h

Supervisión del diseño e implementación de la práctica.

Supervision of the design and implementation of the practical.
Objectives: 11 12 17 18 1 2 4 6 7 8 9 19
Contents:
Theory
0h
Problems
0h
Laboratory
3h
Guided learning
0h
Autonomous learning
3h

Teaching methodology

Topics will be explained in a practical way by using many examples.

Theory classes introduce knowledge, techniques and concepts that will be used in laboratory sessions. They also include the presentation and discussion of the solutions of a set of problems.

The two-hour theory classes and the three-hour laboratory sessions will take place weekly.

The programming project integrates knowledge and skills of the entire course, except for the topic (recursive data types) which will be assessed in the final theory exam.

Evaluation methodology

The technical competence mark (NCTEC) is calculated as follows:

NCTEC = 0.10*C + 0.25* EX_PAR1_TP + 0.15*EX_PRAC + 0.25*PRAC + 0.25*EX_PAR2_TP

where

* C is the mark of the mid-term laboratory exam; to be able to take this exam solving a subset of the exercices of the first three sessions of laboratory might be required.

* EX_PAR1_TP and EX_PAR2_TP are the marks of the mid-term and final theory exams

* EX_PRAC is the mark of the programming project exam

* PRAC is the mark of the programming project

Nevertheless, NCTEC will be NP if the weight of the assessment activities with an NP mark is greater than or equal to 70%.

The assessment of the generic competence Teamwork will be carried out as follows. In a previously appointed laboratory session, teams of students will be formed. Each team should generate and deliver a number of cases (i.e. a set of examples consisting of pairs of correct input and the corresponding output) for testing the full functionality of the programming project C++ code. The evaluation of the competence Teamwork for each student in a team will be based on a document delivered by the team which will contain a description of the test cases generated and a detailed explanation of the participation of each team member in their development.

Bibliography

Basic:

Complementary:

Web links

Previous capacities

Students are expected to have been trained in imperative programming techniques based on:
- basic instructions (assignment, alternative and iteration)
- actions and functions, parameter passing and recurrence
- vectors, tuples and sequences
- sequential search and traversal schemes
- basic algorithms (binary search, vector sorting, matrix arithmetics).

They are also expected to know how to use at least one imperative language, preferably C++, and they should have some
experience in implementing of C++ programs in the Linux environment.

Furthermore, they should be able to assimilate information from a statement, discuss the correctness of an algorithm and compare algorithmic solutions.