Eclipse & JDK Downloads

July 31, 2007

Eclipse 3.2

JDK 1.5

Leave a Comment » | OO Systems Design | Permalink
Posted by Chad Salinas

NFA vs. DFA

July 30, 2007

Theorem:  \forall NFA, \exists 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 \epsilon transitions.

Leave a Comment » | Automata & Complexity Theory | Permalink
Posted by Chad Salinas

Worst Case & Asymptotic Analysis

July 5, 2007

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

7n \log n is objectively better than 1/2n^2

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

f(n) \in O(g(n)) \exists c > 0 and n_0>0 s.t.

(\forall n>n_0)(0\le f(n)\le cg(n))

1 Comment | Design and Analysis of Algorithms | Permalink
Posted by Chad Salinas