1:06 AM
Gilles has made a change to the feeds posted into this room
Gilles has made a change to the feeds posted into this room

1:28 AM
7

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...

1

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...

3

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...

7

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...

3

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...

7

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...

1

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...

4

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...

2

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?

2

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.

1:55 AM
0

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...

2:22 AM
0

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} ...

2:50 AM
0

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...

3 hours later…
5:36 AM
0

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...

1

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...

0

What should we do about programming questions like this one? Are they on-topic or should they be closed (or migrated to SO)?

2 hours later…
7:27 AM
1

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?

2

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 ...

0

What is an efficient algorithm to find the least common multiple of two numbers?

7:54 AM
1

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 ...

2 hours later…
9:43 AM
0

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...

3 hours later…
12:57 PM
Can questions on Operating Systems be asked on Computer Science?
IMO they should be.

1:21 PM
@VinayakGarg: +1 on that
unless they get too technical
However, if in doubt, there should be Meta question on that.

1 hour later…
2:52 PM
0

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...

0

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...

3:19 PM
0

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...

3:36 PM
@VinayakGarg I would think so, but like bitmask said, ask on meta.

3:46 PM
1

The question came up: Are questions about Software Engineering ontopic?

4:41 PM
0

How should we behave and what behaviour should we encourage during beta specifically in order to make our site successful?

5:08 PM
0

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...

2

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...

5:41 PM
0

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...

0

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...

0

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...

6:35 PM
1

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...

1 hour later…
7:50 PM
Oh hai everyone!
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.

1

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 ...

Oh, college...

@Kevin I love college :D

By valid BST do you just mean all the nodes are in order?

What else would it mean? (Not trying to be snippy, honestly wondering)

8:05 PM
@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.

8:17 PM
@OghmaOsiris Do you still need to count complete branches if it turns out not to be a BST?

@Kevin Yes

9:02 PM
1

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...

0

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,...

9:56 PM
3

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...

@OghmaOsiris I had no idea what BST could mean until I read the question. I edited your title

@Gilles @OghmaOsiris See whether you think my answer to that reveals too much.

@Kevin I'm not sure it explains the right things
<delves back into freshman course TA mode from a decade back>
<ouch>

10:12 PM
I TA'd an intro course too, not quite as long ago.
Suggestions on parts I should improve?
It's always easier to go through one-on-one to get them to reach the conclusions on their own.

@Kevin aye
@Kevin you don't explain that the two parts are unrelated
trying to do two things at once can be devastating for freshmen
and they don't have the experience to split the problem into manageable parts

Hey, I'm a junior, lol. I didn't think this class was still elementary. It's a 300 level course lol.

Would it be reasonable to suggest you write the two methods independently, then compare and merge them?

well to be honest, I combined 2 questions into 1 question. I thouoght they would easily combined. But they should be two separate methods.

10:27 PM
Your answer has an unclosed {

@Kevin (;

I feel like all the questions i would have are going to be considered "too elementary" ... :(

@Kevin that's on purpose, I'm being ambiguous as to whether other stuff goes into the braces

@Gilles I thought that might be, but ... OCD

I mean, what's the threshold of the scope of CS.se?

10:29 PM

@OghmaOsiris There's no such thing as too elementary as far as I'm concerned.

@Kevin first time I saw this… today…
@sepp2k anything from hydrogen and above is fine by me

@Gilles So no free subatomic particles for you?

no quarks or Higgs boson's?

@Kevin free? IDK, sounds dangerous. Is that one of 'em radioactive nucular thingies?

10:33 PM
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.

@OghmaOsiris ObSF: bosun Higgs
oops, wrong room

10:53 PM
0

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 hate subversion...
I just finished cleaning up a merge attempt.
3 days later.

@Kevin you fascist
seriously, me too. CVS FTW!

If I'm the only one working on a repo, I do a commit, then a checkout, how can everything be "out of date"???

@Gilles: CVS? seriously?

Plus I've been using it since before subversion existed

11:05 PM
and here I was, hoping it was a joke
Hypothetical question: Were I to recommend you git, would you like me doing that?

but for projects with more than a handful of people, it doesn't scale well. I'd switch to git or hg.

Can't be worse than SVN

@Kevin SourceSafe?
I've never used it, but I've heard of it

I hadn't heard of it, but given that it's made by microsoft, and even they don't think it's worth using, you're probably right.

@Gilles: well, a shared ftp server is also simple. That's hardly an argument.

11:09 PM
@bitmask a shared ftp server doesn't keep history, it's not a vcs
I use CVS for my personal stuff
I wouldn't recommend it for a new multi-person project

@Gilles: You need a dedicated, central server to run CVS, don't you?