Algorithms and Data Structures

• Weekly hours
• Objectives
• Contents
• Activities
• Teaching methodology
• Evaluation methodology
• Bibliography
• Web links
• Previous capacities

Teachers

Person in charge

• Caroline König ( )

Weekly hours

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

Teaching methodology

Evaluation methodology

Bibliography

Basic:

• Introduction to algorithms - Cormen, Thomas H; Leiserson, Charles Eric; Rivest, Ronald L; Stein, Clifford, The MIT Press, [2022]. ISBN: 9780262046305
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991005238379006711&context=L&vid=34CSUC_UPC:VU1
• Combinatorial algorithms : generation, enumeration and search - Kreher, Donald L; Stinson, Douglas R, CRC Press, cop. 1999. ISBN: 084933988X
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991001878419706711&context=L&vid=34CSUC_UPC:VU1
• Introduction to computation and programming using Python : with application to computational modeling and understanding data - Guttag, John V, 2021. ISBN: 9780262363433
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991005184779906711&context=L&vid=34CSUC_UPC:VU1

Complementary:

• Algorithms unlocked - Cormen, Thomas H, The MIT Press , cop. 2013. ISBN: 0262518805
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004001129706711&context=L&vid=34CSUC_UPC:VU1
• Algorithms on trees and graphs : with python code - Valiente Feruglio, Gabriel, Springer , [2021]. ISBN: 9783030818845
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004916440606711&context=L&vid=34CSUC_UPC:VU1

Web links

• MIT OpenCourseWare: it is a free publication of the materials of the courses of the Massachusets Institute of Technology (MIT) that shows most of the topics that are taught in MIT. Contains notes, exercises, solved exercises, exams and videos of classes. http://ocw.mit.edu/courses/#electrical-engineering-and-computer-science
• Jutge https://jutge.org/
• Algorithms Courses on the WWW https://people.cs.pitt.edu/~kirk/algorithmcourses/index.html
• Lecture Notes K. Wayne of the course "Algorithms and Data Structures" from Princeton University https://www.cs.princeton.edu/courses/archive/fall12/cos226/lectures.php

Previous capacities