Enlarging letters   Home   Information   Contacting   Map
Catalŕ   Castellano

Practicals in Programming (PRAP)

Credits Dept. Type Requirements
7.5 (6.0 ECTS) LSI
  • Compulsory for DIE
  • Compulsory for DCSFW
  • Compulsory for DCSYS
 P1 - Prerequisite for DIE , DCSYS , DCSFW

Instructors

Person in charge:  Alberto Rubio Gimeno (albert@lsi.upc.edu)
Borja Valles Fuente (valles@lsi.upc.edu)
Others:Elvira Patricia Pino Blanco (pino@lsi.upc.edu)
Jorge Castro Rabal (castro@lsi.upc.edu)
Juan Luis Esteban Ángeles (esteban@lsi.upc.edu)
M. Luisa Bonet Carbonell (bonet@lsi.upc.edu)
Oriol Costa Lopez (ocosta@lsi.upc.edu)
Renato Alquezar Mancho (alquezar@lsi.upc.edu)

General goals

In this subject, students delve further into structured programming. They are introduced to techniques for designing mid-sized programs, and given further experience in the field of programming through practicals. Finally, their command of recursion as a tool for program construction is broadened.

Specific goals

Knowledges

  1. Understand module and data abstraction techniques.
  2. Learn techniques for the modular decomposition of programmes.
  3. Initial acquaintance with linear and tree data structures.
  4. Learn how to analyse the efficiency of programmes, using this as one more quality criterion.
  5. Learn the basic concepts of object-oriented programming.
  6. Learn the immersion-based recursive design technique, and its link with

    iteration.

Abilities

  1. Ability to create new data types, separating the specification and implementation stages.
  2. Ability to break down largish problems into independent modules.
  3. Ability to produce medium-sized programmes that are reliable, and easy to understand, change, maintain, and re-use.
  4. Coding modular design in an object-oriented language.
  5. Use pre-defined modules.
  6. Ability to write recursive programmes using types that are not necessarily basic, and be able to discern whether they are properly written and efficient.

Competences

  1. Ability to understand problems: given a problem, distinguish between data (or starting elements), unknowns (or what is asked for), hypotheses, and the laws applicable.
  2. Ability to think in abstract terms. Ability to tackle new problems by consciously using strategies that have proved useful in solving previous problems.
  3. Ability to logically argue the decisions taken, work done, or a given viewpoint. Ability to give well-reasoned opinions with a view to convincing others.
  4. Ability to present a well-written report setting out one"s results and document submission of practical work.
  5. Ability to organise one"s work: ability to set priorities for various tasks, plan one"s time, and organise one"s notes.

Contents

Estimated time (hours):

T P L Alt Ext. L Stu A. time
Theory Problems Laboratory Other activities External Laboratory Study Additional time

1. Introduction to modules
T      P      L      Alt    Ext. L Stu    A. time Total 
6,0 0 12,0 0 8,0 3,0 0 29,0
Decomposition of complex problems. Re-usability. Modularity. Representation independence. Module specification: data an operations.



Module hierarchy. Enrichments.



Use of modules. Programming with pre-defined modules. Specification and use of generic data types: stacks, queues, lists, and binary trees.



Implementation of modules. Implementation of new types: Tupla constructor.





  • Laboratory
    Examples of modules that have already been translated into C++ will be demonstrated during the sessions. Students will then go on to solve various exercises.

2. Modular design
T      P      L      Alt    Ext. L Stu    A. time Total 
6,0 0 9,0 0 6,0 3,0 0 24,0
Techniques are presented for breaking programmes down into modules that satisfy the quality requirements dealt with earlier.







Among others, the themes introduced include:







- Decomposition of complex problems.



- Functional abstraction and data



- Successive refinements



- Ascendent/descendent design.







Concepts and techniques will be illustrated with case studies.



Knowledge of algorithms acquired during the Programming 1 course will be reviewed at the same time.





  • Laboratory
    The sessions will take the case studies seen during the theory classes and students will work on translating them into C++.

3. Lab project
T      P      L      Alt    Ext. L Stu    A. time Total 
0 0 21,0 0 42,0 0 0 63,0
This is an individual assignment where the student has to solve a problem of middling complexity. Students have to apply both their knowledge of



modular object-oriented design in the light of contents 1 and 2, and the knowledge of small-scale Programming (studied in the previous course).







The themes helping students develop their projects and dealt with in the lab sessions will be the following:







1. C++ coding.



2. Libraries.



3. Programme debugging and testing.



4. Input/output with text files.







  • Laboratory
    The project will be structured so that students can work in incremental steps over various weeks of the course. Students will be supervised on a weekly basis and make partial submissions.
  • Additional laboratory activities:
    Students have to spend time outside the classroom to prepare documentation for submission, and for the supervisory sessions. Students can consult faculties members by appointment. The translation to C++ can also be done in students' own time.

4. Recursive programming
T      P      L      Alt    Ext. L Stu    A. time Total 
4,0 0 0 0 0 4,0 0 8,0
Generalising a function. How and when to generalise functions in a recursive design. Relationship between new parameters in generalized recursive functions and local variables in iterations.

5. Efficiency improvements en recursive and iterative programmes
T      P      L      Alt    Ext. L Stu    A. time Total 
4,0 0 0 0 0 4,0 0 8,0
The problem of repeating calculations in a programme. How to avoid repeated calculations. Recursiveness: new parameters and/or resultats (immersions for efficiency reasons). Iteration: new local variables.

6. Recursive types
T      P      L      Alt    Ext. L Stu    A. time Total 
4,0 0 0 0 0 4,0 0 8,0
Introduction to the use of recursive types. Recursive type definitions. Implementation of abstract data types through recursive types. Implementation of basic operations.

7. Combination of recursiveness and iteration
T      P      L      Alt    Ext. L Stu    A. time Total 
4,0 0 0 0 0 4,0 0 8,0
Exhaustive search algorithms. Combinatorial algorithms.


Total per kind T      P      L      Alt    Ext. L Stu    A. time Total 
28,0 0 42,0 0 56,0 22,0 0 148,0
Avaluation additional hours 6,0
Total work hours for student 154,0

Docent Methodolgy

The teacher presents new concepts in theory classes, setting out their usefulness and illustrating them with examples.







Students solve short problems in the first part of lab classes.







The second part of the class involves tackling a slightly longer programming problem, which students solve under the teacher"s supervision.







This process involves interim submissions of parts of the solution



in order to ensure students are working on the right lines.

Evaluation Methodgy

The grade awarded for the course as a whole is calculated as follows:

65% practical exam + 35% final exam

The grade for practical work is based on marks for the following:

- Development of the practical work, reflected in the C++ Coding and the Solving Report. The two activities will make up 55% of the marks.
- A test on the contents of the practical work will make up the remaining 45% of the marks. This test is held as if it were a part exam.

Any attempt of fraud during the course will entail the application of the UPC's general academic normative and the beginning of a disciplinary process.

Basic Bibliography

  • Rubio, Albert, Valles, Borja Apunts de PRAP, web de l'assignatura, 2004.
  • Valles, Borja Laboratori de PRAP , Web de l'assignatura, 2004.
  • Cortadella J., Rubio A., Valentín L. Programació 1 (notes de curs), CPET, 2001.

Complementary Bibliography

  • Castro J., et al. Curs de programació (tambe en castella), McGraw Hill, 1992.
  • Balcázar, José Luis Programación Metódica, McGraw-Hill, 1993.
  • Liskov, B., Guttag, J. Abstraction and Specification in Program Development, McGraw-Hill, 1986.
  • Roura, Salvador Normes de Programació de P1, Pŕgina web de l'assignatura P1, .
  • Pozo, Salvador y otros C más más con clase, http://www.conclase.net/c/index.php, .

Web links

  1. Obrir nova finestra http://www.lsi.upc.es/~prap/prap.html


Previous capacities

Basic knowledge of and skills in C++ programming.



 
logo FIB © Barcelona school of informatics - webmaster@fib.upc.edu - RSS RSS