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

Systems Programming (PS)

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

Instructors

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

General goals

This subject aims to instil students with the ability to design, implement and assess data structures, as well as with the ability to design, implement and assess algorithms within these structures.

Specific goals

Knowledges

  1. Abstract data types: specification, use, design, implementation.
  2. Object-oriented programming: classes, objects, methods, inheritance, polymorphism, dynamic linking.
  3. Analysis of algorithms: efficiency, costs, cases, asymptotic notation, solution of simple recurrences.
  4. Basic data structures: stacks, queues, lists.
  5. Advanced data structures: trees, dictionaries.
  6. Dynamic memory: dynamic memory management, destructors, copy construction, assignation, garbage collection.
  7. Ordering algorithms: quicksort, mergesort, and heapsort

Abilities

  1. Acquire the methodology for drawing up the specification, use, and implementation of abstract data types.
  2. Knowledge of and know-how in various techniques for implementing efficient data structures.
  3. Knowledge of generic ADT techniques, and how to use and modify them to yield the solutions required.
  4. Know-how in checking the correctness and efficiency of abstract data types and the algorithms which they employ.
  5. Criteria for choosing the most appropriate design and implementation options during the specification stage, and the ability to set forth a reasoned argument for the choices made.
  6. Knowledge of basic object-oriented methods for developing large-scale software that functions properly and is modular, robust, efficient.

Competences

  1. Critical, logical-mathematical reasoning.
  2. Ability to solve problems through the application of scientific and engineering methods.
  3. Ability to design systems, components and processes meeting certain needs, using the most appropriate methods, techniques and tools in each case.
  4. 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.
  5. Ability to relate and structure information from various sources and thus integrate ideas and knowledge.

Contents

Estimated time (hours):

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

1. Analysis of algorithms
T      P      L      Alt    Ext. L Stu    A. time Total 
4,0 4,0 0 0 0 8,0 0 16,0
Efficiency in terms of time and space. Worst case, middle case, best case. Asymptotic notation. Properties. Analysis of algorithms. Recurrences. Solving recurrences.

2. Linear structures
T      P      L      Alt    Ext. L Stu    A. time Total 
6,0 6,0 3,0 0 3,0 12,0 0 30,0
Review of the concept of sequence. Lists with points of interest. Stacks and queues. Vector implementation and linked linear structure lists. Iterators.

3. Trees
T      P      L      Alt    Ext. L Stu    A. time Total 
2,0 2,0 1,0 0 1,0 4,0 0 10,0
Review of the tree concept. Basic properties. Pre-ordered paths, post-ordered paths, disordered paths, by levels. Implementation of trees with vector pointers to children. Implementation of trees with pointers to parent-to-sibling.

4. Searching and ordering
T      P      L      Alt    Ext. L Stu    A. time Total 
8,0 8,0 4,0 0 4,0 16,0 0 40,0
Dictionaries. Techniques for implementing simple dictionaries. Advanced implementation techniques. Binary search trees. Balanced search binary trees. Dispersion tables. Ordering algorithms: quicksort, mergesort, heapsort.

5. Object-oriented programming and Abstract Data Types (ADT)
T      P      L      Alt    Ext. L Stu    A. time Total 
8,0 8,0 8,0 0 8,0 16,0 0 48,0
review of the concept of abstract data types. Classes, methods, objects. Constructors, destructors, copy assignment and constructor. Implementation of ADTs using classes. Inheritance. Hierarchy of classes. Abstract classes. Polymorphism. Dynamic linking. Genericity. Classes and parameterised methods. Instancing.







  • Additional laboratory activities:
    Prior study of the guidelines and documentation for the lab session. Preliminary development of solutions for exercises prior to computer coding and testing.


Total per kind T      P      L      Alt    Ext. L Stu    A. time Total 
28,0 28,0 16,0 0 16,0 56,0 0 144,0
Avaluation additional hours 4,0
Total work hours for student 148,0

Docent Methodolgy

A highly practical approach is adopted, based on the presentation of a host of examples.







There will be three kinds of classes: theory sessions, problem sessions, and lab sessions. On average, three hours a week will be dedicated to theory classes, two hours a week to problems, and one hour a week to lab sessions. The teacher will schedule these classes in accordance with the needs of the theme taught.







The theory classes take the form of lectures in which the teacher sets out new concepts or techniques and examples illustrating them.







Practical classes focus on exercises and case studies. Teachers set the problems to be solved. The purpose of the exercises is to present and discuss fairly straightforward problems requiring little theory or technical knowledge. As a rule, they cover exercises that illustrate the concepts introduced in the most recent theory sessions. The problems dealt with in the case studies are more complex than those covered in the exercises. Furthermore, they involve different theoretical concepts, which need to be combined in order to come up with a good solution.







A set of practical exercises will be carried out in the lab classes. The teacher will set the practical exercises. Students will solve the exercise under the teacher"s close supervision.

Evaluation Methodgy

Both continuous assessment tests (P) and a final exam (F) will be used. The latter covers the whole of the course material and lab practical work (L).







The course grade is calculated as follows:



0.3 L + 0.7 * max(F, 0.6 * F + 0.4 * P)

Basic Bibliography

  • Mark Allen Weiss Data structures and problem solving using C++, Pearson Education International, 2003.
  • Robert Sedgewick Algorithms in C++ : Parts 1-4: Fundamentals, data structures, sorting, searching, Addison-Wesley, 1998.

Complementary Bibliography

  • Mark Allen Weiss Data structures and algorithm analysis in C++, Pearson Education, 2006.

Web links

  1. http://www-assig.fib.upc.edu/~ps


Previous capacities

Mastery of object-oriented programming techniques: Knowledge of at least one imperative programming language and/or object-oriented language. Recursiveness. Basic knowledge of discrete mathematics. Ability to follow mathematically and formally-stated arguments. Some basic knowledge of statistics and probability.


Compartir

 
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