Saltar al contingut Menu
Map
  • Home
  • Information
  • Contact
  • Map

Programming and Data Structures (PRED)

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

Instructors

Person in charge:  (-)
Others:(-)

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 course focuses on the use of dynamic memory and linked data structures, which are basic for 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. Exposure to some advanced programming techniques.
  3. Acquire a methodology for specifying, using, designing, and implementating 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 presented in a highly practical way and will be illustrated with many examples.

There will be three kinds of classes: theory sessions, problem sessions, and lab sessions. There will be weekly 4 hours of theory and problem classes. There will be only 2 or 3 guided lab sessions. The remaining lab time is devoted to students autonomous work.

Evaluation Methodgy

A partial exam (NP grade), of practical nature, will be held arround mid course. It will cover the topics of lineal structures and memory management.

The final exam (NF grade) covers the whole course. This exam has a more conceptual nature, and includes again the topics already covered in the partial exam.

The lab grade (NL grade) is computed from two two equally-weighted programming exercises, which are solved in couples. The first exercise (linear structures) will be proposed around the third or fourt week of classes, and the second one about three weeks before classes end. In both cases there are about four weeks to solve them.

The total grade (NT grade) is computed as:

NT = max(0,2*NP + 0,6*NF, 0,8*NF) + 0,2*NL

Basic Bibliography

  • Bertrand Meyer Object-oriented software construction, Prentice Hall, 1997.
  • John C. Mitchell. Concepts in programming languages, Cambridge University Press, 2003.
  • B. Pierce Types and programming languages, MIT Press, 2002.
  • Mark Allen Weiss Estructuras de datos en Java : compatible con Java 2, Addison Wesley, 2000.
  • Ricardo Peña Marí Diseño de programas : formalismo y abstracción, Prentice Hall, 2005.

Complementary Bibliography

  • Narciso Martí Oliet, Yolanda Ortega Mallén, José Alberto Verdejo López. Estructuras de datos y métodos algorítmicos : ejercicios resueltos, Pearson Educación, 2001.

Web links

(no available informacion)

Previous capacities

PREREQUISITES: Prap


Compartir
Share

 
logo FIB © Barcelona school of informatics - Contact - RSS
This website uses cookies to offer you the best experience and service. If you continue browsing, it is understood that you accept our cookies policy.
Classic version Mobile version