## Prequisite concepts in algorithms, data structures, and discrete math for 03-511/711

Students are expected to be familiar with the following concepts.   While some of this material will be reviewed in class, students are ultimately responsible for acquiring any background knowledge they may be lacking.

### Resources

• Introduction to Computational Molecular Biology, J.C. Setubal and J. Meidanis, chapter 2 (on reserve).
• Computational Methods in Molecular Biology, S. L. Salzberg, D. B. Searls and S. Kasif,
Chapter 2:  "A tutorial introduction to computation for biologists". (electronic reserves)
• Computational Biology , P. Clote and R. Backofen, Sections 2.1.1 - 2.1.3
• Data Structures and Problem Solving using Java, M. A. Weiss
• Introduction to Algorithms, T. H. H. Cormen  R. L. Rivest  C. E. Leiserson
• Dictionary of Algorithms and Data Structures

### Strings

• Substrings, superstrings, concatenation, prefix, suffix

### Algorithms and Data structures

• Pseudocode
• Divide and Conquer
• Dynamic programming
• Stacks, queues
• Depth first search
• Binary search trees
• Searching
• Sorting

### Graph theory

• Directed vs undirected graphs
• Notation: G = (V,E)
• V = {nodes, aka vertices}
• E = {edges}
• Cyclic vs acyclic graphs
• Trees
• Binary trees, k-ary trees
• Counting leaves, nodes, and edges
• Depth, Height
• Node degree
• Paths and cycles,
• Connected components
• Cliques

### Algorithmic complexity

• Big Oh notation
• Asymptotic behavior
• "Hard" problems - NP-completeness

### Basic Probability and Statistics

• Random variables
• Conditional probability
• Bayes Theorem
• Hypothesis testing, p-values
• Basic probability distributions: Normal, exponential, binomial...