Seeing that in the Chomsky Hierarchy Type 3 languages can be recognised by a DFA (which has no stacks), Type 2 by a DFA with one stack (i.e. a push-down automaton) and Type 0 by a DFA with two stacks (i.e. with one queue, i.e. with a tape, i.e. by a Turing Machine), how do Type 1 languages fit in...
Considering this pseudo-code of an bubblesort:
FOR i := 0 TO arraylength(list) STEP 1
switched := false
FOR j := 0 TO arraylength(list)-(i+1) STEP 1
IF list[j] > list[j + 1] THEN
switch(list,j,j+1)
switched := true
ENDIF
NEXT
IF switch...
Let's consider a memory segment (whose size can grow or shrink, like a file, when needed) on which you can perform two basic memory allocation operations involving fixed size blocks:
allocation of one block
freeing a previously allocated block which is not used anymore.
Also, as a requiremen...
Rice's theorem tell us that the only semantic properties of Turing Machines (i.e. the properties of the function computed by the machine) that we can decide are the two trivial properties (i.e. always true and always false).
But there are other properties of Turing Machines that are not decidabl...
People often say that LR(k) parsers are more powerful than LL(k) parsers. These statements are vague most of the time; in particular, should we compare the classes for a fixed $k$ or the union over all $k$? So how is the situation really? In particular, I am interested in how LL(*) fits in.
As f...
Since the current FAQs say this site is for students as well as professionals, what will the policy on homework be?
What are the guidelines that a homework question should follow if it is to be asked? I know on math.se they loosely require that the student make an attempt to solve the question a...
I really like the new beta theme, I guess it is much more attractive to newcomers than the sketchy one (which I also liked). Thanks a lot!
However I'm slightly embarrassed because I can't read what I type, both in the title and in the body of a post. I never encountered the problem on other Stac...
This discussion started in my other question "Will Homework Questions Be Allowed?".
Should we allow the tag? It seems that some of our sister sites (Programmers, stackoverflow) have not allowed the tag as it isn't constructive to their sites. But other sites (Physics, Mathematics) do allow the s...
I know we have some very useful ones on cstheory.SE and I have seen some amusing ones on Stackoverflow. On other sites such as scifi.SE they seem to be banned.
What is our stand?
There have been many questions on CST that were either closed, or just not answered because they weren't considered research level. May those questions (as long as they are of good quality) be reposted or moved here?
I have a particular example question in mind: http://cstheory.stackexchange.com...
I've added feeds: a bot will post new questions from the main site and from the meta site (with a few minutes' delay).
They're often useful as conversation starters and to make the room feel less empty. And this way you get a notification of new questions when you have the room open.
If you don't like the automatic question feed: click on the icon next to the questions then “ignore this user (everywhere)”. You need to do this separately for the main site and for Meta.
Ok, so in most introductory Algorithm classes, either BigO or BigTheta notation are introduced, and a student would typically learn to use one of these to find the time complexity.
However, there are other notations, such as BigOmega and SmallOmega. Are there any specific scenarios where one not...
Many textbooks cover intersection types in the lambda-calculus. The typing rules for intersection can be defined as follows (on top of the simply typed lambda-calculus with subtyping):
$$
\dfrac{\Gamma \vdash M : T_1 \quad \Gamma \vdash M : T_2}
{\Gamma \vdash M : T_1 \wedge T_2}
...
I expect to see pseudo code and maybe even HPL code on regular basis. I think syntax highlighting would be a great thing to have.
On Stackoverflow, code is highlighted nicely; the schema used is inferred from the respective question's tags. This won't work for us, I think, because we probably wo...
Sudoku generation is hard enough. It is much harder when you have to make an application that makes a completely random Sudoku.
The goal is to make a completely random Sudoku in Objective-C (C is welcome). This Sudoku generator must be easily modified, and must support the standard 9x9 Sudoku, a...
I have observed that there are two different types of states in branch prediction.
In superscalar execution, where the branch prediction is very important, and it is mainly in execution delay rather than fetch delay.
In the instruction pipeline, where the fetching is more problem since the inst...
Did the smoothed analysis find its way into main stream analysis of algorithms? Is it common for algorithm designers to apply smoothed analysis to their algorithms?
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 ...
NPI is the class of NP problems without any polynomial time algorithms and not known to be NP-hard. I'm interested in problems such that a candidate problem in NPI is reducible to it but it is not known to be NP-hard and there is no known reduction from it to the NPI problem. Are there any known ...
I am reading Mining Significant Graph Patterns by Leap Search (Yan et al., 2008), and I am unclear on how their technique translates to the unlabeled setting, since $p$ and $q$ (the frequency functions for positive and negative examples, respectively) are omnipresent.
On page 436 however, the au...
This is my first time to be involved in a site beta, and I would like to gauge the community's opinion on this subject.
On StackOverflow (and possibly Math.SE), questions on introductory formal language and automata theory pop up... questions along the lines of "How do I show language L is/isn't...
This is my first time to be involved in a site beta, and I would like to gauge the community's opinion on this subject.
Certainly, there are many kinds of questions which we could expect to (eventually) be asked on CS.SE; lots of candidates were proposed during the lead-up to the Beta, and a few...
This is somewhat related to this discussion, but different enough to deserve its own thread, I think.
What would be the site policy regarding questions that are generally considered "easy", but may be asked during the first semester of studying computer science. Example:
"How do I get the symme...
EPAL, the language of even palindromes, is defined as the language generated by the following unambiguous context-free grammar:
$S \rightarrow a a$
$S \rightarrow b b$
$S \rightarrow a S a$
$S \rightarrow b S b$
EPAL is the 'bane' of many parsing algorithms: I have yet to enc...
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 inductive type which has some recursive occurrences in a nested, but strictly positive location. For example, trees with finite branching with nodes using a generic list data structure to store the children.
Inductive LTree : Set := Node : list LTree -> LTree.
The naive way of d...
I was editing a question and I was about to tag it bubblesort, but it occurred to me that tag might be too specific. I almost tagged it sorting but its only connection to sorting is that the algorithm happens to be a type of sort, it's not about sorting per se.
So should we tag questions on a pa...
To what extent are questions about proof assistants on-topic?
I see four main classes of questions:
Modeling a problem in a formal setting; going from the object of study to the definitions and theorems.
Proving theorems in a way that can be automated in the chosen formal setting.
Writing a co...
Should topics in applied CS be on topic? These are not really considered part of TCS, examples include:
Computer architecture (Operating system, Compiler design, Programming language design)
Software engineering
Artificial intelligence
Computer graphics
Computer security
Source: http://en.wik...
I asked one of my current homework questions as a test to see what the site as a whole is looking for in a homework question. It's not a difficult question, but I imagine this is what some of our homework questions will look like.
I have an assignment for my data structures class. I need to create an algorithm to see if a binary tree is a binary search tree as well as count how many complete branches are there (a parent node with both left and right children nodes) with an assumed global counting variable.
So far I have
...
@Kevin Valid as in if there are no nodes that contain information they shouldn't. ie all left children are less than the parent, and right children are greater than the parent.
It's a known fact that every LTL formula can be expressed by a Buchi $\omega$-automata. But, apparently, Buchi automata is a more powerful, expressive model. I've heard somewhere that Buchi automata are equivalent to linear-time $\mu$-calculus (that is, $\mu$-calculus with usual fixpoints and onl...
Let us call a context-free language deterministic if and only if it can be accepted by a deterministic push-down automaton, and nondeterministic otherwise.
Let us call a context-free language inherently ambiguous if and only if all context-free grammars which generate the language are ambiguous,...
One can imagine using a variety of data structures for storing information for use by state machines. For instance, push-down automata store information in a stack, and Turing machines use a tape. State machines using queues, and ones using two multiple stacks or tapes, have been shown to be equi...
Though in the future it would probably a good idea to more thoroughly explain your thinking behind your algorithm and where exactly you're stuck. Because as you can probably tell from the answers, people seem to be unsure on where exactly you need directions in this case.
What will the policy on providing code be?
In my question it was commented that it might not be on topic as it seemes like I was asking for working code. I wrote my algorithm in pseudo-code because my problem didnt ask for working C++ or whatever language.
Should we only allow pseudo-code here?...
I have observed that there are two different types of states in branch prediction.
In superscalar execution, where the branch prediction is very important, and it is mainly in execution delay rather than fetch delay.
In the instruction pipeline, where the fetching is more problem since the inst...
This is somewhat related to this discussion, but different enough to deserve its own thread, I think.
What would be the site policy regarding questions that are generally considered "easy", but may be asked during the first semester of studying computer science. Example:
"How do I get the symme...
