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

  • M. Luisa Bonet Carbonell ( )
  • Pau Fernandez Duran ( )

Others

  • Albert Calvo Ibañez ( )
  • Alejandro Ivan Paz Ortiz ( )
  • Alfonso Valverde Ruiz ( )
  • Borja Valles Fuente ( )
  • Guillem Godoy Balil ( )
  • Jorge Castro Rabal ( )
  • Jose Carmona Vargas ( )
  • Juan Luis Esteban Ángeles ( )
  • Maria Josefina Sierra Santibañez ( )
  • Santiago Marco Sola ( )
  • Xavier Messeguer Peypoch ( )

Weekly hours

Theory
2
Problems
0
Laboratory
3
Guided learning
0.3
Autonomous learning
7.2

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


C++ review exercises.

Link to PRO1 contents.
  • Laboratory: Laboratory session week 1
Objectives: 2 8
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: 10
Contents:
Theory
2h
Problems
0h
Laboratory
6h
Guided learning
0h
Autonomous learning
9h

Recursive programming

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

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: 11
Contents:
Theory
2h
Problems
0h
Laboratory
9h
Guided learning
0h
Autonomous learning
16h

Iterative program correctness

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

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: 12 14 15 16 17 13 18
Contents:
Theory
3h
Problems
0h
Laboratory
9h
Guided learning
0h
Autonomous learning
12h

Introduction to modular design and object-oriented design.

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

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

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

Implementing classes of objects in C++.

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

Supervision of practical

Supervision of the design and implementation of the practical.
  • Laboratory: Laboratory session week 11.
Objectives: 3 5 6 7 8 10 11 16 17 21 1
Contents:
Theory
0h
Problems
0h
Laboratory
3h
Guided learning
0h
Autonomous learning
6h

Recursive data types.

Development of the corresponding topic.
  • Theory: Theory sessions weeks 10, 11, 12 and 13
  • Laboratory: Laboratory sessions weeks 13 and 14
Objectives: 16 17 19 20 1 3 18
Contents:
Theory
7.5h
Problems
0h
Laboratory
9h
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

EX_SIMUL1

Mock exam for midterm exam 1
Objectives: 10 11 16 17 19 20 2 3 5 6 7 8 18
Week: 8 (Outside class hours)
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
2h
Autonomous learning
2h

EX_PAR1_TP

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

CODI_DOC_PRAC1

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

EX_SIMUL2

Mock exam for midterm exam 2
Objectives: 10 11 16 17 19 20 2 3 5 6 7 8 18
Week: 13 (Outside class hours)
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
2.5h
Autonomous learning
2.5h

EX_PAR2_TP

Final theory/problems exam.
Objectives: 10 11 16 17 19 20 2 3 5 6 7 8 18
Week: 15 (Outside class hours)
Theory
2.5h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
6.5h

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 maybe 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.3*EXAM1 + 0.3*EXAM2 + 0.25*PRAC + 0.1*DELIVERY + 0.05*VERIF

where

* EXAM1 and EXAM2 are the marks of the mid-term and final theory exams

* PRAC is the mark of the programming project; it may have an automatic part, derived from code testing, and a manual part.

* DELIVERY is the mark arising from the deliveries from students of solutions to exercises requested over the course.

* VERIF is the mark of a small quiz about formal verification of iterative and recursive algorithms done during theory class.

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 is obtained from the elaboration, in groups of students, of input tests for the course project.

PRO2 RE-EVALUATION

There is a re-evaluation in this course, which consists in an intensive, 12-hour in person course with its corresponding evaluation. This course is scheduled in the days after the final exams and before the next semester begins. It is estimated that the re-evaluation requires about 50 hours of dedication by the student, counting class sessions, personal study time and the evaluation itself. Only students which satisfy certain criteria are allowed to enroll in this course. Moreover, each student can only enroll in one of the re-evaluation courses offered for the subjects in the initial phase of the degree.

Minimum requirements to qualify for re-evaluation

To qualify for the re-evaluation course, it is mandatory to be enrolled in the PRO2 course and to have obtained a final grade ranging from 3.5 and 4.9. Additionally, the other grades must satisfy 0.25*PRAC * 0.10*DELIVERY >= 1.5.

Minimum requirements for the re-evaluation exam

To be able to attend the exam, it is mandatory:
- Attend to all the in-person classroom sessions.
- Do all the exercises or activities that the professor asks.

Pre-registraton and admission

The registration process will be published in the Racó website. A student being admitted and not attending the course might entail not being admitted in future intensive courses.

Evaluation of the re-evaluation course

The evaluation is an exam (REVAL), and the outcome will be "Pass" if 0.6*REVAL + 0.25*PRAC + 0.10*DELIVERY + 0.05*VERIF >= 5, and "Fail" otherwise. The final grade of the PRO2 subject will be:

FINAL_GRADE = 5, if outcome is "Pass"
FINAL_GRADE = SEMESTER_GRADE if outcome is "Fail",

where SEMESTER_GRADE is the grade out of 10 obtained in the semester course.

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.