Enlarging letters   Home   Information   Contacting   Map
Català   Castellano

Programming and Data Structures (PRED)

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

Instructors

Person in charge:  Elvira Patricia Pino Blanco (pino@lsi.upc.edu)
Others:Ana Cristina Zoltan Torres (zoltan@lsi.upc.edu)
Ana Edelmira Pasarella Sanchez (edelmira@lsi.upc.edu)
Nicolas Eduardo Mylonakis Pascual (nicos@lsi.upc.edu)

General goals

Firstly, this subject aims to give students a better idea of what programming languages are, and, in particular, object-oriented programming languages. With this goal in mind, students study aspects such as type structure, data control, memory management and the abstraction mechanisms of languages that display these characteristics. Secondly, students also learn new programming techniques. In particular, the subject focuses on the use of dynamic memory and linked data structures, which are behind many applications.

Specific goals

Knowledges

  1. Data types in programming languages.
  2. Data control in programming languages.
  3. Data abstraction. Specification and implementation.
  4. Implementacions with pointers, chained nodes, and dynamic memory.
  5. Dynamic memory management. Garbage collection.
  6. Implementations of basic ADTs: lists, queues, stacks, trees, hash tables.
  7. Inheritance

Abilities

  1. Learn the nature of programming languages in greater depth.
  2. Acquaintance with some advanced programming techniques.
  3. Acquire a methodology for drawing up a specification and identifying use, design and implementation of ADTs.
  4. Learn implementation techniques based on pointers and dynamic memory.
  5. Knowledge of generic ADT techniques, and how to use and modify them to yield the solutions required.

Competences

  1. Ability to solve problems through the application of scientific and engineering methods.
  2. Ability to create and use models of reality.
  3. Ability to design systems, components and processes meeting certain needs, using the most appropriate methods, techniques and tools in each case.
  4. Ability to think in abstract terms. Ability to tackle new problems by consciously using strategies that have proved useful in solving previous problems.
  5. Know-how to apply the solution cycle to common scientific and engineering problems: specification, coming with ideas and alternatives, design solution strategies, carrying out the strategy, validation, interpretation and evaluation of results. Ability to analyse the process on completion.
  6. Ability to analyze and summarise issues.
  7. Ability to learn on one"s own.

Contents

Estimated time (hours):

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

1. Data abstraction: specification and implementation
T      P      L      Alt    Ext. L Stu    A. time Total 
7,0 3,0 0 0 0 10,0 0 20,0
Concept of data abstraction types:







Informal description of the concept of data abstraction types. Reasons for and advantages of programming employing ADTs. Contracted programming. Decomposition by functions and decomposition of data in the descendent design.







ADT specification:







Specification construction methodology. Operation types: (constructors, generators, modifiers).







ADTs and object-oriented programming:







ADTs as a basic object-oriented programming concept. Objects. Classes. Methods. Management functionality: construction, destruction and assignment. Ways of hiding information and functions.







Genericity:







Parameterised ADTs. Instancing. Containers. Iterators implementing ADTs.





Specific data structures. ADT implementation concept. Representation invariance. Abstraction function.

2. Linear structures
T      P      L      Alt    Ext. L Stu    A. time Total 
4,0 2,0 2,0 0 12,0 6,0 0 26,0
Stacks







Specification. Applications. Implementation with static tables. Implementation with dynamic tables. Implementation with chained nodes.







Queues. Specification. Applications. Implementation with circular tables. implementation with chained nodes.



Lists. Specification. Applications. Implementation with chained nodes. Variations.







  • Laboratory
    Planning and discussion of forthcoming practical work. The teacher will not be present during this exercise.

  • Additional laboratory activities:
    Carry out a short practical assignment/exercise on linear structures. Basically, this will involve implementation of a list variant.

3. Tree structures
T      P      L      Alt    Ext. L Stu    A. time Total 
4,0 2,0 2,0 0 8,0 6,0 0 22,0
General trees, binary and m-ary trees:







Specification of general trees. Specification of m-ary trees. Specification of binary trees. Examples: expression trees. Implementation linking binary trees. Linked implementation of m-ary trees. Isomorphism between general and binary trees. Implementing general trees using pointers to first and child and sibling.



Tree schemes: Pre-ordered, post-ordered, and unordered walks, and by levels.



Application: Evaluation of expressions, formal derivation of expressions.







  • Laboratory
    Presentation and discussion of practical work to be performed. This assignment is performed without the teacher being present.
  • Additional laboratory activities:
    Carry out a short practical assignment/exercise on tree structures. Basically, this will involve implementation of a tree variant.

4. Programming languages
T      P      L      Alt    Ext. L Stu    A. time Total 
2,0 0 0 0 0 2,0 0 4,0
Design criteria for a programming language.



Implementation of a programming language. Abstract machines.

5. Data types
T      P      L      Alt    Ext. L Stu    A. time Total 
6,0 2,0 0 0 0 0 0 8,0
Concept of type.





Data types and the features of a programming languages.





Polymorphism and overload.







Definition of a type system using inference rules.







Type checking.

6. Dynamic memory
T      P      L      Alt    Ext. L Stu    A. time Total 
5,0 2,0 0 0 7,0 0 0 14,0
Pointers, new and delete.
Destructor, copy constructor, and assignment operator.
Dynamic assignment of memory.
Garbage collection algorithms.

7. Data control
T      P      L      Alt    Ext. L Stu    A. time Total 
3,0 2,0 0 0 0 5,0 0 10,0
Names and entities.







Entity visibility and life.







Static and dynamic environments. Access to entities: static and dynamic chains.







Passing parameters.

8. Hashing
T      P      L      Alt    Ext. L Stu    A. time Total 
6,0 2,0 2,0 0 6,0 8,0 0 24,0
Specifying tables and dictionaries.





Implementation with hash tables: open hashing, closed hashing, and other variations.





Hash functions







  • Laboratory
    Planning and discussion of forthcoming practical work. This assignment is performed without the teacher being present.
  • Additional laboratory activities:
    Carry out a short practical assignment/exercise on hash tables. Basically, this will involve implementation of a table variant.

9. Inheritance
T      P      L      Alt    Ext. L Stu    A. time Total 
3,0 1,0 0 0 0 4,0 0 8,0
Inheritance and subtypes.







Inheritance as a design tool.







Inheritance and programme modifiabilty.


Total per kind T      P      L      Alt    Ext. L Stu    A. time Total 
40,0 16,0 6,0 0 33,0 41,0 0 136,0
Avaluation additional hours 6,0
Total work hours for student 142,0

Docent Methodolgy

The subject will be set forth in a highly practical fashion and will be illustrated with many examples.







There will be three kinds of classes:



theory sessions, problem sessions, and lab sessions. The breakdown of these sessions throughout the course is as follows:



4 hours a week of theory and problems.



2 or 3 lab sessions. The remaining lab work is devoted to students" individual work.

Evaluation Methodgy

Two exams will be held: one will cover the more theoretical side of the course and involve short questions (NT grade), and the other will cover data structuring problems (NP grade).







The lab grade (NL grade) will be the product of two equally-weighted individual programming exercises. The first exercise (linear structures) must be submitted by the sixth week of the course. The second exercise (hash tables) must be submitted by the last week of the course.







The final grade (N grade) is calculated as follows: N = 0.4 NT + 0.4 NP + 0.2 NL

Basic Bibliography

  • B. Meyer Object oriented software construction (2nd edition), Prentice Hall, 2000.
  • J. Mitchell Concepts in programming languages, Cambridge University Press, 2001.
  • B. Pierce Types and programming languages, MIT Press, 2002.
  • M. Weiss Estructuras de datos en Java, Prentice Hall, 2000.
  • R. Peña Diseño de programas, formalismo y abstracción, Prentice Hall, 2004.

Complementary Bibliography

  • N. Martí, Y. Ortega, J.A. Verdejo Estructuras de datos y métodos algorítmicos - Ejercicios resueltos, Prentice Práctica, 2003.

Web links

(no available informacion)

Previous capacities

PREREQUISITES: Prap



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