PřF:C2142 Design of algorithms in life s

C2142 Design of algorithms in life sciences

Faculty of Science
Spring 2014

Extent and Intensity

1/2. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).

Teacher(s)

doc. RNDr. Radka Svobodová, Ph.D. (lecturer)
RNDr. Tomáš Raček, Ph.D. (lecturer)
Mgr. Tomáš Bouchal, Ph.D. (assistant)

Guaranteed by

prof. RNDr. Zdeněk Glatz, CSc.
National Centre for Biomolecular Research – Faculty of Science
Supplier department: National Centre for Biomolecular Research – Faculty of Science

Timetable

Mon 16:00–16:50 B11/205

Timetable of Seminar Groups:

C2142/01: Thu 14:00–15:50 C04/211, T. Raček
C2142/02: Tue 11:00–12:50 C04/118, T. Raček
C2142/03: Thu 12:00–13:50 C04/118, T. Raček

Prerequisites

Basic familiarity with an arbitrary programming language is an advantage, but it's not required.

Course Enrolment Limitations

The course is also offered to the students of the fields other than those the course is directly associated with.
The capacity limit for the course is 60 student(s).
Current registration and enrolment status: enrolled: 0/60, only registered: 0/60, only registered with preference (fields directly associated with the programme): 0/60

fields of study / plans the course is directly associated with

Chemoinformatics and Bioinformatics (programme PřF, N-BCH)

Course objectives

Introduce the fundamental principles for efficient algorithms and data structures design demonstrated on interesting science examples.
At the end of the course the students will be able to describe and to use known algorithms for solving common problems.
Moreover, they will be able to design new approaches to the particular applications with an emphasis on efficiency of the solution.
The graduates will also have the ability to critically evaluate and choose optimal solution to the uncommon problems.

Syllabus

1. From problem to algorithm. Specification, correctness.
2. Introduction to complexity. Examples of life science problems with logarithmic, polynomial and exponential complexity.
3. Basic data structures (linked list, queue, stack). Applications in biology and chemistry.
4. Motivation to the data searching, sorting algorithms (binary search, Selection sort, Merge sort). Applications in processing chemoinformatics and bioinformatics data.
5. Search trees, heaps (BST, Heap sort). Applications in processing chemoinformatics and bioinformatics data.
6. Hashes, indices. Possibilities of use in biology and computer chemistry.
7. Basic graph theory terms, graph representation, methods of traversal (BFS, DFS). Molecular graph.
8. Shortest path problem (Dijkstra, Bellman-Ford, Floyd-Warshall). Application in working with molecular graph.
9. Spanning trees (Prim, Kruskal). Application in processing molecular graph.
10. Approaches to solving problems (brute force, greedy algorithms, divide and conquer). Application in chemoinformatics and bioinformatics.
11. Hard problems (TSP, SAT, P vs. NP). Examples of life science hard problems.
12. Advanced data structures (AVL, B+ trees, Union-Find). Application in biology and chemistry.

Literature