Filed under: Uncategorized | Leave a Comment »
C++ STL
• http://www.dinkumware.com/manuals/default.aspx
• http://www.sgi.com/tech/stl
Filed under: OO Systems Design | Tagged: 107 | Leave a Comment »
Pumping Lemma
What is the importance of the Pumping Lemma?
Filed under: Automata & Complexity Theory | Tagged: Add new tag, Chad Salinas Pumping Lemma | 1 Comment »
Automata & Complexity Theory
Review the following:
- DFA
- NFA
- Regular Expressions
- Inductive proofs
- Constructive proofs
- CFGs
- Turing Machines
- Undecidability
- Computational Complexity
Filed under: Automata & Complexity Theory | Tagged: Add new tag | Leave a Comment »
Eclipse & JDK Downloads
Filed under: OO Systems Design | Leave a Comment »
NFA vs. DFA
Theorem: NFA,
a DFA that recognizes the same language.
Of course iff proofs require bi-direction, even when one direction is trivial.
Has it really been that long ago??? Just give me a state and a symbol so I can union it with the existing states…
Don’t forget about transitions.
Filed under: Automata & Complexity Theory | Leave a Comment »
Worst Case & Asymptotic Analysis
Guiding Principles of Worst Case and Asymptotic Analysis
1. Worst Case is useful for the following reasons:
- Gives a bounded running time for large inputs n
- Hard to define a “normal” input
- Easier to analyze
is objectively better than
2. Asymptotic Analysis
- Don’t care about coefficients
- Discard lower order terms
- Don’t lose any predictive power
- Constants are machine-dependent
Goal: Find algorithms as close to order n as possible
and
Filed under: Design and Analysis of Algorithms | 1 Comment »
Divide & Conquer Review
MergeSort
Input: a list of n numbers
Output: same n numbers in sorted order
Algorithm:
- Recursively sort 1st half
- Recursively sort 2nd half
- Merge 2 sorted lists together (tricky part)
When merging the 2 sorted lists the head of each list is the only candidate element for the head node of the final list.
Specific pseudo-code Running Time of MergeSort
Generalized Running Time of MergeSort
Filed under: Design and Analysis of Algorithms | Leave a Comment »
Design and Analysis of Algorithms Prelims
1) The Internet is a graph!
Think about how you would send a packet from one network to another on a given web-graph. What makes a path “good”? Good path could be any of the following:
- the one with the least number of hops,
- shortest path,
- lowest probability of errors,
- cheapest path,
- a working path…
Don’t forget about your tools:
- Dijkstra’s Algorithm
- Floyd’s Algorithm
- Hedetniemi’s Algorithm
- Bellman-Ford’s Algorithm
- Prim’s Algorithm
- Kruskal’s Algorithm
You need to know the all-pairs shortest path minimally.
2) Sequence Alignment
In computational biology, your input is two strings of DNA code over
What is similar about the two strings:
- Almost similar sequences?
- % error rate?
- edit distance?
Why do we care if two strings are similar?
- We may want to extrapolate the function that generates the two strings.
- Maybe similar correlates positively with proximity and the evolutionary tree, i.e. two similar genomes yield some inferences.
Forewarned is forearmed! If you don’t have a strong background in statistics and discrete math, you will not survive.
Chad Salinas Design & Analysis of Algorithms
Filed under: Design and Analysis of Algorithms | Leave a Comment »
Equivalent Regular Expressions
The following two Regular Expressions (RE) are equivalent:
Drawing the Non-Deterministic Finite Automata (NFA) makes it easier to ferret out the RE than drawing the “strictly” Deterministic Finite Automata (DFA).
Chad Salinas find an equivalent RE example.
Filed under: Discrete Structures | 1 Comment »