Lecture notes and material for the class Computational Thinking in Bioinformatics at the Bioinformatics Research Centre, Aarhus University.
- Problem domain / models / goals and problems / solutions / implementations
- Introduction to Python programming and Jupyter notebooks.
- Branching and looping (JVG 2 + 3)
Besides the lectures and exercises, we could recommend a basic online course in Python programming that could be followed and maybe have some of the exercises in relation to this.
- Correctness and complexity
- Pre- and post-conditions and invariants -- exemplified by e.g. different sorting algorithms
- O-notation and reasoning about complexity
- Functions (JVG 4)
- Basic data structures (JVG 5)
- Translating ideas into code by breaking them down to the right level of abstraction
- Running time in practise
- Testing and debugging (JVG 6)
- Plotting (JVG 11.1)
- Complexity (JVG 9)
- Pre- and post-conditions and invariants revisited
- Recursion
- Divide and conquer
- Dynamic programming
- Dynamic programming examples (JVG 13)
- Representing trees as lists
- Traversing trees, e.g. DFS for outputting a tree
- Implementing a tree representation
- Potentially a Newick parser
- DFS traversal and outputting a tree
- Representing graphs as incidence lists or matrices
- Classical graph algorithms (JVG 12.2)
- Problem complexity versus solution (algorithm) complexity
- NP-hardness
???
- gene finding,
- sequence data,
- FASTA format
- Parsing a FASTA file
- HMMs, automata, languages
- Representing an HMM
- Computing the likelihood of a HMM
- machine architecture
- representation of numbers
- Log-space and scaling likelihood computations
- Training by counting (maximum likelihood estimation for an HMM)
Training by counting
- How to statistically validate correctness
- How to (statistically) validate running time
- Validation of implementation
- Direct translation of simple python code to C
- Re-implement likelihood computations i C
- Compare running time
- HMMs as matrix-vector operations
- Implement in numpy as matrix vector operations
- Compare running time