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...