Recursion
Normally, recursion involves a function calling itself repeatly. Hence the function stack grows. However, the compiler would know to avoid the growth of stack (hence preventing stack overflow because of that) if the recursion is a tail recursion. Tail recursion is a recursion that,
- The recursive function is called in the
return
statement - The recursive function in the return statement is not part of a larger expression
For example, the following is not a tail recursion:
int factorial(int n) {
if (n>0) {
return n*factorial(n-1);
} else {
return 1;
};
};
// Call: factorial(10);
but the following is a tail recursion:
int factorial(int n, int a) {
if (n>0) {
return factorial(n-1,a*n);
} else {
return a;
};
};
// Call: factorial(10,1);
Big-O notation
Some situation wherein common complexities occur:
Complexity | Example |
---|---|
\(O(1)\) | Fetching the first element from a set of data |
\(O(\log n)\) | Splitting a set of data in half repeatly |
\(O(n)\) | Traversing a set of data |
\(O(n\log n)\) | Splitting a set of data in half repeatly and traversing each half |
\(O(n^2)\) | Traversing a set once for each member of another set of equal size |
\(O(2^n)\) | Generating all possible subsets of a set of data |
\(O(n!)\) | Generating all possible permutations of a set of data |
Automata
Finite automata:
- We have NFA (non-deterministic) and DFA (deterministic), but they are equivalent in function
Regular language: Some NFA recognizes it
- Discribed by regular expression
- RE is equivalent to some NFA
- GNFA (generalized NFA): An NFA that allows RE in addition to symbols on arrows
Non-regular language: No finite automata can recognize it
- Non-regular language can be verified by pumping lemma
- Pumping lemma: \(A\) is a regular language if and only if:
- \(A\) is a language
- \(s \in A\) such that \(\vert s\vert \ge p\) and \(s=xyz\), and
- \(xy^iz \in A \quad \forall i \ge 0\); and
- \(\vert y\vert > 0\); and
- \[\vert xy\vert \le p\]
Context-free language: Described by Context-Free gammar, i.e. substitution rules
- substitution rules consists of variables and terminals (i.e. symbols)
- derivation: The sequence of substitution according to the rules
- The derivation of CFR can be shown using parse trees
- A CFL is ambiguous if the grammar generates the same string in different ways
Push-down automata (PDA): A finite automata with a stack
- CFG is equivalent to PDA
- Pumping lemma for CFL: \(A\) is a CFL if and only if:
- \(A\) is a language
- \(s \in A\) such that \(\vert s\vert \ge p\) and \(s=uvxyz\), and
- \(uv^ixy^iz \in A \quad \forall i \ge 0\); and
- \(\vert vy\vert > 0\); and
- \[\vert vxy\vert \le p\]
Turing machine: A finite automata with a tape of infinite size for read/write
- Turing-recognizable language: Some Turing machine accepts the language
- Decidable: Some Turing decider accepts it
- Decider either accepts or rejects an input, but never loops indefinitely
Oracle: An external device capable of reporting whether any string \(w \in B\)
Relation of languages:
Regular \(\subset\) Context-free \(\subset\) Decidable \(\subset\) Turing-recognizable
Complexities
P: Class of languages for which membership can be decided in polynomial time
NP: Class of languages for which membership can be verified in polynomial time
NP-Complete: A set of problems for which if a polynomial time algorithm exists for any of these problems, all NP problems are polynomial time solvable
- i.e., if NP-complete = P, then P=NP
- Work by Stephen Cook and Leonid Levin
Examples of NP-complete problems:
- Satisfiability problem
- For a boolean expression, such as \(\phi = (\bar x \wedge y) \vee (x \wedge \bar z)\), it is satisfiable if \(\phi = 1\) for some assignment to its variables.
- Satisfiability problem: Provided some boolean expression \(\phi\), determine whether \(\phi\) is satisfiable
- 3SAT problem
- A satisfiability problem of 3-conjunctive normal form, i.e. 3 ORed-triples joined by ANDs
- \(k\)-Clique: Determine if a graph has a \(k\)-clique
- Reducible from 3SAT problem
- Vertex-cover problem:
- Vertex-cover is a subset of nodes of a graph G which every edge of G touches one of those nodes
- For a graph \(G\), determine if a \(k\)-node vertex-cover exists
- Hamiltonian path problem
- For a graph \(G\), determine if a path exists that traverses every node
- Subset sums problem
- Given a collection of numbers, determine if a subset of them adds to have a certain sum
Probability
Given a DTMC, with one absorbing state. The transition matrix is like:
\[P=\begin{bmatrix}Q & C\\ 0 & 1 \end{bmatrix}\]where \(Q\) is a \((n-1)\times(n-1)\) sub-stochastic matrix (i.e. the one with row sum less than 1). Hence the \(k\)-th power of transition matrix is:
\[P^k=\begin{bmatrix}Q^k & C'\\ 0 & 1 \end{bmatrix}\]and we have the fundamental matrix:
\[M=(I-Q)^{-1}=I+Q+Q^2+\cdots=\sum_{k=0}^{\infty} Q^k\]and the \(ij\)-th entry in \(M\) denotes the expected number of visit to state \(j\) before the absorbing state, given we start with state \(i\).
Computer Architecture
The following is a very brief and good piece of tutorial on pipelining and cache:
http://www.cs.iastate.edu/~prabhu/Tutorial/title.html