Mitch
  • Member for 11 years, 5 months
  • Last seen more than 1 year ago
  • http://--
Algorithms from the Book.
32 votes

Gaussian elimination. It completes the generalization sequence from the Euclidean GCD algorithm to Knuth-Bendix.

View answer
Solid applications of category theory in TCS?
12 votes

I think you are asking two questions about applicability, type A and type B separately. As you note, there are many substantive applications of category theory to type B topics: semantics of ...

View answer
Reference for the shortcomings of Google's PageRank algorithm?
Accepted answer
12 votes

to answer your specific question, there are many papers that discuss PageRank mathematically, such as: Deeper Inside PageRank, (A. N. Langville and C.D. Meyer), Internet Mathematics (1), 335–400 (...

View answer
Time-based mathematics or logic
3 votes

Temporal logic seems to be exactly the thing you are looking for (it allows proving things where the truth of propositions can be qualified by operators such as 'in the next time', 'for always after ...

View answer
Recovering the slope of a digitized line
1 votes

I don't know of any work in cg (or any other group for that matter) on deriving slope from the set of discrete points, but that's more a reflection of my lack of knowledge. Rather than cg, this seems ...

View answer
Generating a language from a given grammar
Accepted answer
0 votes

Since you want to generate -all- words of a given length, it really doesn't matter if it's stochastic/probabilistic or deterministic, you just want to see if a word is possible (the following method ...

View answer
Are there pre-doc positions in TCS?
0 votes

In the US, at a research level university, a masters program usually fills this role. Often (but not always), one gets support for the masters doing software or sysadmin'ing for a research group. ...

View answer
Is there a well-known nontrivial subset of NP for which it is known that it is a proper subset?
0 votes

Both the (current) answers plus the comments answer all together. I thought I'd summarize here. Completeness for a class is defined variably with respect to a given class; for example, NPC is usually ...

View answer