@RanG When Theoretical Computer Science launched, a few people wanted a general CS site, but most wanted a research-level site, so that's what the site became
Then there were multiple proposals to create a general CS site, which were closed as duplicates of CSTheory (because Area 51 rep is a joke and the people with enough rep to close Area 51 proposals do not behave responsibly enough to read a site's FAQ before closing a proposal as a duplicate of that site) and of Stack Overflow (less immediately silly, but still not warranted)
2
I think this proposal was the fourth attempt (I may have missed some, closed proposals eventually get deleted)
@Gilles There's no problem with TCS being research-level.. but I find it surprising that elementary CS questions were left without a proper home for so long (while more esoteric SE were opened).
@RanG It has been a major effort to convince the non-CS practictioner crowd (who dominates SE in total, it seems) that we know better than them what CS is.
@Gilles regarding 227: My first read of your question entered my brain stem like "Why does UNIX have . and ..?". As such, I think the question would have been OT as it is to localized. Upon rereading, I think it can be seen as a general OS question.
@Gilles I don't think you will get a good answer, though; there does not seem a good reason. You clearly need the links somehow (cf XPath) but it should not matter at all where they are stored, modulo overhead.
@Gilles So you may get a good/better answer on unix.SE after all.
@Raphael ah, that is a problem. maybe I shouldn't have added that second paragraph.
@Raphael I don't think so, I'm ultimately not interested in anything like a unix system but in a proprietary filesystem designed for embedded systems and with a lot fewer supported operations
So if the answer turns out to be “it facilitates operations X and Y”, and X and Y aren't supported by my proprietary filesystem, then I don't want . and ..
In programming languages, closures are a popular and often desired feature. Wikipedia says (emphasis mine):
In computer science, a closure (...) is a function together with a referencing environment for the non-local variables of that function. A closure allows a function to access variables ...
@Gilles Much better now, thanks. :) We will see what people come up with. You probably need insight into a modern OS in order to understand if one really needs . and ...
For all our concerns regarding site traffic, area51 still lists us as hottest proposal. Whatever that means.
Do you guys think my question 196 needs more motivation? I have one, of course, but did not include it so far (because it is basically the result of my not-yet-finished master thesis).
I want to parse user-defined domain specific languages. These languages are typically close to mathematical notations (I am not parsing a natural language). Users define their DSL in a BNF notation, like this:
expr ::= LiteralInteger
| ( expr )
| expr + expr
| expr * expr
...
@Gilles That was related to your parsing question. In particular good error reporting is always a hassle, afaik, and might in fact be impossible (guessing here) for ambiguous grammars.
Let's take as an example the 3d → 2d reduction: What's the cost of simulating a 3d cellular automaton by a 2d cellular automaton?
Here is a bunch of more specific questions:
What kind of algorithms will have their time complexity changed, by how much?
What would be the basic idea for the encod...
Reflection is a common mechanism for accessing and changing the structure of a program at run-time, found in many dynamic programming languages such as Smalltalk, Ruby and Python, and in impoverished form in Java and (hence) Scala. Functional languages such as LISP and Scheme also support a good ...
I've just noticed that this question and this question were closed by @Rebecca Chernoff. It seems both question already had close votes, which is why I think they ended up getting closed.
My guess is that the SE Network has decided to do this to help communities in private beta to get enough clo...
A simple game usually played by children, the game of War is played by two people using a standard deck of 52 playing cards. Initially, the deck is shuffled and all cards are dealt two the two players, so that each have 26 random cards in a random order. We will assume that players are allowed to...
It is often said that hash table lookup operates in constant time: you compute the hash value, which gives you an index for an array lookup. Yet this ignores collisions; in the worst case, every item happens to land in the same bucket and the lookup time becomes linear ($\Theta(n)$).
Under what ...
It's 6 days into the private beta, we only have 66 questions, and Robert Cartaino has very discreetly announced:
We decided to extend this private beta another 7 days. The question count is a bit on the low side to launch and that gives you a bit more time to flesh out the scope and let the c...
I wonder whether the massively parallel computation units provided in graphic cards nowadays (one that is programmable in OpenCl for example) are good enough to simulate 1d cellular automata (or maybe 2d cellular automata?) efficiently.
Choose whatever finite grid would fit inside the memory of ...
Theoretical Computer Science Stack Exchange (“CSTheory.SE”) is for
research-level questions in theoretical computer science
My eyeball evaluation is that about half the questions so far are about theoretical computer science, and I don't know that any of them are research-level.
I don't wa...
plus the fact that the description of the site includes practitioners
Yeah I'm not sure, that talks about CSTheory. CS (syllabus wise) encompasses everything from Flip Flops, Programming to Software Design
But based on the questions so far, it seems to be just within the theory. Reason I asked is because I was browsing SO for possible good but closed questions
Is there an algorithmic approach to identify that dates given in a paragraph correlate to particular events (phrases) in the paragraph?
Example, consider the following paragraph:
In June 1970, the great leader took the oath. But it was only after May 1972, post the death of the Minister of S...
Assume a computer has a precise clock which is not initialized. That is, the time on the computer's clock is the real time plus some constant offset. The computer has a network connection and we want to use that connection to determine the constant offset $B$.
The simple method is that the compu...
Consider an filesystem targeted at some embedded devices that does little more than store files in a hierarchical directory structure. This filesystem lacks many of the operations you may be used to in systems such as unix and Windows (for example, its access permissions are completely different ...
In a round-robin scheduler, adding a process multiple times to the process list is a cheap way to give it higher priority.
I wonder how practical an approach this might be. What benefit does it have over other techniques such as giving the process a longer time slice (benefit: less switching tim...
Is there any evidence suggesting that time spent on writing up, or thinking about the requirements will have any effect on the development time? Study done by Standish (1995) suggests that incomplete requirements partially (13.1%) contributed to the failure of the projects. Are there any studies ...
Suppose that a certain parallel application uses a master-slave design to process a large number of workloads. Each workload takes some number of cycles to complete; the number of cycles any given workload will take is given by a known random variable $X$. Assume that there are $n$ such workloads...
In computer networking and high-performance cluster computer design, network topology refers to the design of the way in which nodes are connected by links to form a communication network. Common network topologies include the mesh, torus, ring, star, tree, etc. These topologies can be studied an...
I want to parse user-defined domain specific languages. These languages are typically close to mathematical notations (I am not parsing a natural language). Users define their DSL in a BNF notation, like this:
expr ::= LiteralInteger
| ( expr )
| expr + expr
| expr * expr
...
So is it possible to push this into a meta FAQ post? I really wasn't aware that's all. Just speaking from a first glance. I'm sure if I was more involved like in Movies.SE I would see these questions >.<
I had a little chat with Shog9, and he encouraged us to repost old CS posts from SO/Math/ProgSE that got no love (closed, or unanswered, or only crap answers
of course, only do that if it's a good question that you don't mind asking under your name
There's been a lot of hype about JIT compilers for languages like Java, Ruby, and Python. How are JIT compilers different from C/C++ compilers, and why are the compilers written for Java, Ruby or Python called JIT compilers, while C/C++ compilers are just called compilers?
I'd like to know how you think (or know) it is that Facebook produces the "people you might like" or "suggested friends" on each user's page. This is really an algorithm question, not a Facebook question, but social networking is probably the most visible and well understood example which is why ...
@phwd @Gilles agreed. It should probably be phrased in a general way, asking for sth along the lines of "How to determine likely connections in a social network?"
I have briefly tried to find closed questions that qualify for cs.SE but have had trouble accessing them. For users without access to moderator tools, they seem to be gone. :-/
@Gilles I doubt it, therefore the abstraction. But I don't know for sure. Social networks are actively researcher, though, so there should be plenty of meat there.
The halting problem cannot be solved in the general case. It is possible to come up with defined rules that restrict allowed inputs and can the halting problem be solved for that special case?
For example, it seems likely that a language that does not allow loops for instance, would be very easy...
@Raphael Heh... If you have something reasonably specific you're looking for, let me know and I can help you search. (leaving now, but I'll be back later tonight)
Also remember, "closed:1" is the search operator for closed (but not deleted) questions
@Shog9 basically, any closed question with the computer-science tag (which is largely misused on SO, by the way). Relevance will have to be judged by hand. One guideline might be my ubiquitous comment "This question may have been perfect for the upcoming..." which I put under all questions I though would be ontopic here for the last months.
Is there a unified theory of caching?
That is, collections of theorems and algorithms for constructing caches and/or optimizing for them?
The question is deliberately broad, because the results I am looking for are also broad.
Formulas for maximum achievable speedup, metrics for caching algorith...
What I was hoping was something like “. and .. are useful for operations X and Y”, and then I could decide whether to put them in depending on whether I wanted to support X and Y in my FS
Possible Duplicate:
Determine whether or not there exist two elements in Set S whose sum is exactly x - correct solution?
Consider an unsorted array of numbers and an constant Z. We want to find whether there are two elements in the array whose sum is Z.
I know there is an O(n*lgn) al...
@Gilles: well excepted for the obsolete (and respectively doubtful) reason I mention in the note I can't see why those entries would be useful. But let's wait maybe someone will come with a real answer :)
though maybe some indication of the expected level would be better
for example, on my hash table question, I feel I've had answers both below and above the level I expected
though mostly the answers were more theoretical than I wanted
I would have liked a discussion of when in practice a hash table may or may not be considered O(1)
rather than all this stuff about perfect hashes. I've yet to see perfect hashes being used, and anyway neither of the answers said anything about how you make a perfect hash from some data
I am curious in determining an approach to tackling a "suggested friends" algorithm.
Facebook has a feature in which it will send recommended individuals to which you can be acquainted. These users normally (excluding the edge cases in which a user specifically recommends a friend) have a highly...
@Raphael you never know, I've had people argue vehemently on a few of my U&L question that I didn't understand some basic concept and their answer expounding on something I brushed past in my question was definitely THE answer
In programming languages, closures are a popular and often desired feature. Wikipedia says (emphasis mine):
In computer science, a closure (...) is a function together with a referencing environment for the non-local variables of that function. A closure allows a function to access variables ...
Possible Duplicate:
Determine whether or not there exist two elements in Set S whose sum is exactly x - correct solution?
Consider an unsorted array of numbers and an constant Z. We want to find whether there are two elements in the array whose sum is Z.
I know there is an O(n*lgn) al...
