##

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
- Linked lists
- Breadth
first search
- 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

- Representations:
matrix, adjacency lists
- 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...