Programming II

Credits
7.5
Types
Compulsory
Requirements
This subject has not requirements , but it has got previous capacities
Department
CS
Web
https://pro2.cs.upc.edu
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

Others

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
    0h
    Autonomous learning
    0h

    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
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    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
    0h

    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
    0h
    Autonomous learning
    0h

    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
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    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.3*PRAC + 0.1*DELIVERY

    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. Moreover, EXAM2 will contain at least a problem related to the project, whose mark will count towards the project's mark.

    * 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 the elaboration, in teams of students, of special group exercises during the course.


    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.3*PRAC * 0.10*DELIVERY >= 2.

    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 (REEVAL), and the outcome will be "Pass" if 0.6*REEVAL + 0.3*PRAC + 0.10*DELIVERY >= 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.