Algorithms and Data Structures

Credits
6
Types
Compulsory
Requirements
This subject has not requirements , but it has got previous capacities
Department
CS
Mail
caroline.leonore.konig@upc.edu
This subject focuses on data structures and algorithm for efficient data analysis in bioinformatic problems. The subject covers trees, dictionaries, graphs and priority queues and explains the related algorithms on these data structures as well as efficient algorithms for exploring complex search spaces. The course introduces the theory of computational intractability and their respective classes.

Teachers

Person in charge

Weekly hours

Theory
2
Problems
1
Laboratory
1
Guided learning
0
Autonomous learning
6

Competences

Learning Outcomes

Knowledge

  • K3 - Identify the mathematical foundations, computational theories, algorithmic schemes and information organization principles applicable to the modeling of biological systems and to the efficient solution of bioinformatics problems through the design of computational tools.
  • K4 - Integrate the concepts offered by the most widely used programming languages in the field of Life Sciences to model and optimize data structures and build efficient algorithms, relating them to each other and to their application cases.

    • Skills

  • S7 - Implement programming methods and data analysis based on the development of working hypotheses within the area of study.
  • S8 - Make decisions, and defend them with arguments, in the resolution of problems in the areas of biology, as well as, within the appropriate fields, health sciences, computer sciences and experimental sciences.

    • Competences

  • C6 - Detect deficiencies in the own knowledge and overcome them through critical reflection and the choice of the best action to expand this knowledge.

    • Objectives

    1. Know the key data structures used in bioinformatic computing.
      Related competences: K3, K4, S7, S8, C6,
      Subcompetences
      • Know relevant problems in bioinformatic computing which are solved relying on specific data structures.
    2. Understand the design and implementation of basic data structures for efficient data management in advanced algorithms.
      Related competences: K3, K4, S7, S8, C6,
      Subcompetences
      • Know, understand, design data structures to implement dictionaries.
      • Know, understand, design data structures to implement priority heaps.
      • Know, understand, design data structures to implement trees.
      • Know, understand, and design data structures to implement stacks and queues.
    3. Knowledge about algorithms for the resolution of classic problems with graphs.
      Related competences: K3, K4, S7, S8, C6,
      Subcompetences
      • Know, design, compare and implement shortest path algorithms in graphs.
      • Know, design, compare and implement algorithms for topological ordering.
      • Know, design, compare and implement graph traversal algorithms.
    4. Understand, design, compare and implement string matching algorithms.
      Related competences: K3, K4, S7, S8, C6,
    5. Know, design and implement exhaustive search algorithms .
      Related competences: K3, K4, S7, S8, C6,
      Subcompetences
      • Understand, design and implement algorithms to explore the search space: Backtracking and Branch and Bound.
    6. Analyze the limits of computation through the study of computational completeness.
      Related competences: K3, K4, S7, S8, C6,
      Subcompetences
      • Understand the Cook-Levin Theorem as a basis for proving the NP-completeness of problems.
      • Recognize and classify various NP-complete problems, exploring their difficulties and possible algorithmic approaches to address them.

    Contents

    1. Introduction to data structures in bioinformatic computing
      Introduction to key data structures and overview of its application in relevant bioinformatic problems.
    2. Algorithm on trees
      Tree data structure. Binary search trees, AVL-trees.
    3. Dictionaries
      Basic implementations: tables and lists. Advanced implementations: dispersion tables, binary search trees.
    4. Priority queue
      Operations of priority queues. Implementation with heaps. Heapsort.
    5. Algorithm on strings
      Exact and approximate string matching algorithms
    6. Basic graph algorithms
      Representations: Adjacency matrix, adjacency list. Depth first search, Breadth first search. Dijkstra and Bellman-Ford algorithms of shortest path.
    7. Advanced graph algorithms
      Topological sort. Minimum spanning trees. Kruskal¿s algorithm. Prim¿s algorithm.
    8. Exhaustive search algorithms
      Principles: solution space, subset generation, permutations. Backtracking and Branch and Bound.
    9. Notions of intractability
      Class P and NP. NP-completeness and reducibility.

    Activities

    Activity Evaluation act


    Introduction to data structures in bioinformatic computing


    Objectives: 1
    Theory
    2h
    Problems
    0h
    Laboratory
    2h
    Guided learning
    0h
    Autonomous learning
    4h

    Algorithm on Trees


    Objectives: 2
    Theory
    4h
    Problems
    2h
    Laboratory
    2h
    Guided learning
    0h
    Autonomous learning
    10h

    Dictionaries


    Objectives: 2
    Theory
    2h
    Problems
    0h
    Laboratory
    2h
    Guided learning
    0h
    Autonomous learning
    4h

    Priority Queue (Heaps)


    Objectives: 2
    Theory
    2h
    Problems
    2h
    Laboratory
    1h
    Guided learning
    0h
    Autonomous learning
    6h

    String matching algorithm


    Objectives: 4
    Theory
    3h
    Problems
    2h
    Laboratory
    2h
    Guided learning
    0h
    Autonomous learning
    10h

    Midterm exam


    Objectives: 2 4 1
    Week: 8 (Outside class hours)
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Basic graph algorithms


    Objectives: 3
    Theory
    4h
    Problems
    2h
    Laboratory
    2h
    Guided learning
    0h
    Autonomous learning
    10h

    Advanced graph algorithms


    Objectives: 3
    Theory
    2h
    Problems
    1h
    Laboratory
    2h
    Guided learning
    0h
    Autonomous learning
    6h

    Exhaustive search algorithms


    Objectives: 5
    Theory
    4h
    Problems
    2h
    Laboratory
    2h
    Guided learning
    0h
    Autonomous learning
    10h

    Notions of intractability


    Objectives: 6
    Theory
    2h
    Problems
    4h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    10h

    Final examen


    Objectives: 2 5 3 6 4 1
    Week: 18 (Outside class hours)
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Teaching methodology

    The theory classes introduce fundamental concepts and techniques, which are then applied in problem-solving and laboratory sessions through a collection of exercises evaluated by an automatic judge.

    Theory sessions are held weekly for two hours, while laboratory and problem-solving classes take place every two weeks, also lasting two hours each.

    The course is based on programming with Python.

    Evaluation methodology

    EP = grade mid-term exam (0- 10)
    EF = grade final exam (0-10)
    AC= continuous avaluation activities (problems)
    EJ= programming exercises (jutge)

    NOTA = 10.0%AC + 10.0%EJ+ 35.0%EP + 45.0%EF

    The re-evaluation grade replaces the grade of the mid-term and final exam.

    Bibliography

    Basic

    Complementary

    Web links

    Previous capacities

    Students are required to have a foundation in imperative object-oriented programming, including parameter passing, classes, objects, methods, pointers, dynamic memory, recursion, and iterators. They must also be familiar with Python and have basic knowledge of algorithm efficiency calculations, including asymptotic notation and time and space complexity analysis.