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 (
)
Guillem Godoy Balil (
)
Juan Luis Esteban Ángeles (
)
Others
M. Luisa Bonet Carbonell (
)
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
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,
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,
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,
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,
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,
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,
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,
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,
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,
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,
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,
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,
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,
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,
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,
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,
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,
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,
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,
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
Linear data structures
Stacks, queues, lists, maps and sets: specification and use (search and traversal operations). Iterators: definition and use.
Tree data structures
Binary trees.
Iterative program correctness
Loop invariants. Justification of the correctness of iterative algorithms.
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.
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.
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.
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.
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:10111617192023567818 Week:
8 (Outside class hours) Type:
assigment
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
2h
Autonomous learning
2h
EX_PAR1_TP
Mid-term theory/problems exam. Objectives:10111617192023567818 Week:
9 (Outside class hours) Type:
theory exam
Theory
2h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
5h
CODI_DOC_PRAC1
Delivery of the programming project code and documentation. Objectives:101112141617211567891318 Week:
12 (Outside class hours) Type:
assigment
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
10h
EX_SIMUL2
Mock exam for midterm exam 2 Objectives:10111617192023567818 Week:
13 (Outside class hours) Type:
assigment
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
2.5h
Autonomous learning
2.5h
EX_PAR2_TP
Final theory/problems exam. Objectives:10111617192023567818 Week:
15 (Outside class hours) Type:
theory exam
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:
* 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.
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 some of the deliveries carried out along the course (DELIVERY) which will be done in teams.
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
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.