Advanced Data Structures

Credits
6
Types
Specialization compulsory (Advanced Computing)
Requirements
This subject has not requirements , but it has got previous capacities
Department
CS
Mail
duch@cs.upc.edu
Efficient strategies and techniques for "structured data" are key in modern computer science to design fast algorithms useful in a variety of every day applications (like web archiving, mail servers, network routers, video games).
This course explores selected topics on fundamental data structures that may be multidimensional, metric, geometric, kinetic, self-adjusting, concurrent, distributed, etc.
The tour covers, for each topic, major results and characteristic ways of analysis as well as possible directions of research.

Teachers

Person in charge

Others

Weekly hours

Theory
4
Problems
0
Laboratory
0
Guided learning
0.16
Autonomous learning
7.84

Competences

Technical Competences of each Specialization

Advanced computing

  • CEE3.1 - Capability to identify computational barriers and to analyze the complexity of computational problems in different areas of science and technology as well as to represent high complexity problems in mathematical structures which can be treated effectively with algorithmic schemes.
  • CEE3.2 - Capability to use a wide and varied spectrum of algorithmic resources to solve high difficulty algorithmic problems.

    • Generic Technical Competences

    Generic

  • CG1 - Capability to apply the scientific method to study and analyse of phenomena and systems in any area of Computer Science, and in the conception, design and implementation of innovative and original solutions.
  • CG3 - Capacity for mathematical modeling, calculation and experimental designing in technology and companies engineering centers, particularly in research and innovation in all areas of Computer Science.

    • Transversal Competences

    Information literacy

  • CTR4 - Capability to manage the acquisition, structuring, analysis and visualization of data and information in the area of informatics engineering, and critically assess the results of this effort.

    • Reasoning

  • CTR6 - Capacity for critical, logical and mathematical reasoning. Capability to solve problems in their area of study. Capacity for abstraction: the capability to create and use models that reflect real situations. Capability to design and implement simple experiments, and analyze and interpret their results. Capacity for analysis, synthesis and evaluation.

    • Basic

  • CB6 - Ability to apply the acquired knowledge and capacity for solving problems in new or unknown environments within broader (or multidisciplinary) contexts related to their area of study.
  • CB8 - Capability to communicate their conclusions, and the knowledge and rationale underpinning these, to both skilled and unskilled public in a clear and unambiguous way.
  • CB9 - Possession of the learning skills that enable the students to continue studying in a way that will be mainly self-directed or autonomous.

    • Objectives

    1. Become acquainted with the main and classic data structures of central areas of computer science and identify their major properties.
      Related competences: CB8, CB9, CTR4,
    2. Become familiar with the mathematical tools usually used to analyze the performance of data structures.
      Related competences: CG3, CEE3.1, CEE3.2, CB9, CTR6,
    3. Examine ideas, analysis and implementation details of data structures in order to assess their fitness to different classes of problems.
      Related competences: CG1, CG3, CEE3.1, CEE3.2, CB6, CB8, CB9, CTR4, CTR6,
    4. Select, design and implement appropriate data structures to solve given problems.
      Related competences: CG1, CG3, CEE3.1, CEE3.2, CB6, CB9, CTR4, CTR6,

    Contents

    1. Preliminaries.
      Review of required previous knowledge: asymptotic notation, basic algorithm analysis, arrays, linked lists, stacks and queues, basics of hashing, binary search trees, AVL trees, red-black trees, heaps.
    2. Techniques.
      Techniques: Experimental algorithmics. Probabilistic analysis of algorithms. Amortized analysis.
    3. Disjoint Sets.
      Disjoint Sets: Union-find data structures (a.k.a. merge-find sets). Union by weight. Path compression heuristics. Applications.
    4. Priority Queues.
      Priority Queues: Heaps. Binomial queues. Fibonacci heaps.
    5. Data Structures for Strings
      Data Structures for Strings: Tries. Patricia tries. Suffix trees and suffix arrays.
    6. Self-adjusting data structures.
      Self-adjusting data structures: List updates, Splay trees.
    7. Randomized data structures.
      Randomized data structures: randomized BSTs, treaps.
    8. Multidimensional and metric data structures, searching in metric spaces, associative retrieval and object representation.
      Multidimensional and metric data structures, searching in metric spaces, associative retrieval and object representation: grid files, kd trees, point quad trees, PR quad trees, octrees.
    9. Geometric and kinetic data structures.
      Geometric and kinetic data structures: interval, segment and partition trees, sweep lines.
      Data structures for points in motion.
    10. External memory / cache oblivious.
      External memory / cache oblivious: models, B-trees, ordered-file maintenance, van Emde-Boas layout.
    11. Succinct Data Structures.
      Succinct rank and select operations.
    12. Miscellaneous.
      Miscellaneous: concurrent, distributed, augmented, persistent data structures.

    Activities

    Activity Evaluation act



    Programming Projects

    Programming Projects
    Objectives: 1 4 3 2
    Week: 14 (Outside class hours)
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h


    Validation Exam.

    The validation exam, graded out of 10 points, aims to evaluate the student's knowledge consolidation and mastering of the programming projects.
    Objectives: 1 4 3 2
    Week: 14 (Outside class hours)
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Teaching methodology

    The lectures are theoretical/practical merged sessions.
    The lecturer will allocate the hours in accordance with the subject matter.

    The theory hours take the form of lectures in which the lecturer sets
    out new concepts or techniques and examples illustrating them.
    Sessions will consist of a presentation of the main topics of each content's item,
    mainly based in selected original research papers.
    A high level of students' participation is expected at each session.
    Current lines of research in each topic will be discussed at the end of each topics' presentation.

    The practical classes are used to explain implementations and show the performance
    of selected data structures. Students are required to take an active part in the class by
    discussing the various possible solutions/alternatives in class.

    Evaluation methodology

    The final grade F is calculated using the following formula:

    F = 0.5 (VE) + 0.5 ((P1 + P2 + P3 + P4) / 4);

    with:

    VE = exam (0--10 points), P_i = programming project (0--10 points), i = 1,2,3,4

    Bibliography

    Basic

    Previous capacities

    Knowledge any programming language (preferably C++).
    Basic knowledge of algorithm analysis methods (in particular asymptotic complexity).
    Basic knowledge of elementary data structures such as stacks, queues, linked lists, trees, and graphs as well as of sorting methods such as insertion sort, heap sort, merge sort, and quick sort.