« first day    last day (3322 days later) » 

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
Q: What is the significance of context-sensitive (Type 1) languages?

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

Q: evaluating the average time complexity of a given bubblesort algorithm

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

Q: Clever memory management with constant time operations?

Stéphane GimenezLet'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...

Q: Rice's theorem for non-semantic properties

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

Q: Language theoretic comparison of LL and LR grammars

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

Q: Will homework questions be allowed?

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

Q: Cannot see what I'm typing

Stéphane GimenezI 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...

Q: Homework tag discussion

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

Q: What about list questions?

RaphaelI 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?

Q: Cross-Posting Questions from CSTheory

JoeThere 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
Q: How does one know which notation of Time Complexity Analysis to use?

user110Ok, 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
Q: Characterization of lambda-terms that have union types

GillesMany 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
Q: Syntax highlighting -- should we have it?

RaphaelI 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
Q: Random Sudoku generator in Objective-C

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

Q: Which kind of branch prediction is more important?

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

Q: Programming questions

KavehWhat 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
Q: Does Smoothed Analysis get used outside academia?

J.D.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?

Q: Time spent on requirement and its effect on project success and development time

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

Q: Finding the LCM of two numbers

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

7:54 AM
Q: Problems between NPI and NP-hard

Mohammad Al-TurkistanyNPI 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
Q: Applying the graph mining algorithm Leap Search in an unlabeled setting

mitchusI 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
Q: Are questions on introductory undergraduate CS theory appropriate here?

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

Q: Policy on stocking the beta with "easy" questions

Patrick87This 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
Q: Policy on "easy" programming questions

malexmaveThis 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
Q: What is our stance on Software Engineering?

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

4:41 PM
Q: How to behave during beta?

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

5:08 PM
Q: Is there any nongeneral CFG parsing algorithm that recognises EPAL?

Alex ten BrinkEPAL, 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...

Q: Clock synchronization in a network with asymmetric delays

GillesAssume 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
Q: Recursive definitions over an inductive type with nested components

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

Q: Tags for specific algorithms?

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

Q: Scope limits on proof assistants (e.g. Coq)

GillesTo 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
Q: Topics in Applied Computer Science, are they on topic?

Ken LiShould 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.
Q: Help with a BST algorithm

OghmaOsirisI 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
Q: Equivalence of Buchi automata and linear $\mu$-calculus

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

Q: Are there inherently ambiguous and deterministic context-free languages?

Patrick87Let 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
Q: Determining capabilities of a min-heap (or other exotic) state machines

Patrick87One 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>
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.
I've posted an answer
my first answer on CS… It's unusual for me to ask more than I answer
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
Q: Code vs pseudo-code

OghmaOsirisWhat 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?
@bitmask yes, seriously. It's simple.
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?
@bitmask yes and no
it's not a distributed VCS, so yes
but Back Then everybody was working on the central server, or at least accessing its files through NFS
but there were distributed VCS systems on top of CVS. The BSD guys used cvsup
Of course, cvsup is extremely clunky compared to a real DVCS
Well, I'm extremely glad I made the transition from SVN to GIT when I did it.
I only worked with CVS briefly before SVN, but I do not remember a big difference
11:52 PM
This beta is off to a slow start

« first day    last day (3322 days later) »