Alexandre Passos
  • Member for 11 years, 5 months
  • Last seen more than 3 years ago
Computational complexity of learning (classification) algorithms - fitting the parameters
4 votes

"Training" a naive bayes classifier, assuming you're given the feature vectors, is $O(n)$, where $n = \sum_i nnz(x_i)$, where $nnz(x_i)$ is the number of nonzero features in data point $i$. For ...

View answer
Everyday encounters with NP-complete problems
4 votes

I usually use SAT as an example. I say something like "all sorts of problems that come up all the time can be rewritten as looking for a true assignment to a big logic formula. The P vs NP question is ...

View answer
Internal Regret in Online Convex Optimization
0 votes

This Avrim Blum paper points a connection between external and internal regret. According to its abstract, externa regret is a measure of how bad an algorithm is compared to the best fixed action, ...

View answer
What are good references on understanding online learning?
11 votes

Most online learning algorithms come from at least one out of these lineages: the perceptron State of the art perceptrons are the passive-aggressive algorithm, the structured perceptron, and their ...

View answer
Can every non-deterministic finite automate be changed into one with only one acceptance state?
3 votes

Even if you don't allow epsilon transitions, yes. Create a new state and for each edge that would lead to a final state in the original NFA create another nondeterministic one that points to this new ...

View answer
Can a nondeterministic finite automata (NDFA) be efficiently converted to a deterministic finite automata (DFA) in subexponential space/time?
8 votes

The minimum DFA corresponding to an NFA has 2^n states in the worst case, so you can't garantee anything. Without having a constructive example, the reasoning is that in an NFA you can be at any ...

View answer
What are some effective heuristics to find the number of Hamiltonian paths in a rectangular grid?
Accepted answer
3 votes

I don't see an easy way of counting without enumerating. You can easily visit all hamiltonian paths with an exaustive depth-first search with backtracking. You can actually cheat a bit, and realize ...

View answer
Simple balanced trees with O(1) concat?
Accepted answer
5 votes

You can trivially make a data structure with O(1) amortized concatenation time, by just reinserting everything from one tree on the other on concatenation (which has O(n log n) cost, exactly the same ...

View answer
Minimum spanning tree algorithm.
2 votes

This is not a well-defined algorithm. You can tweak it to make it well-defined, by changing the description to Remove all edges, from high to low weight, that do not make the graph disconnected. and ...

View answer
Best resources for string searching or pattern matching exercises
Accepted answer
6 votes

Are you already familiar with the main algorithms in the area? Are you familiar with this site a huge and well-maintained list of references in pattern matching? I don't see how one could come up ...

View answer
What is the theoretical basis of imperative programming?
22 votes

The simplest theoretical model of an imperative program is the turing machine itself. It has both essential components of an imperative program: unbounded modifiable state and a state machine that ...

View answer