This is admittedly a rather loose question. My current understanding of singletons is that they are a class that you set up in such a way that only one instance is ever created.

This sounds a lot like a static class to me. The main difference being that with a static class you don&#39;t / can&#39;t instance it, you just use it such as `Math.pi()`. With a singleton class, you would still need to do something like

    singleton firstSingleton = new singleton();
    firstSingleton.set_name(&quot;foo&quot;);

    singleton secondSingleton = new singleton();

Correct me if i am wrong, but `firstSingleton == secondSingleton` right now, yes?

    secondSingleston.set_name(&quot;bar&quot;);
    firstSingleton.report_name(); // will output &quot;bar&quot; won&#39;t it?

Please note, I am asking this language independently, more about the concept. So I am not worried about actually how to code such a class, but more why you would wan&#39;t to and what thing you would need to consider.

Purpose of singletons in programming

I&#39;m asking more about what this means to my code.  I understand the concepts mathematically, I just have a hard time wrapping my head around what they mean conceptually.  For example, if one were to perform an O(1) operation on a data structure, I understand that the number of operations it has to perform won&#39;t grow because there are more items.  And an O(n) operation would mean that you would perform a set of operations on each element.  Could somebody fill in the blanks here?

  - Like what exactly would an O(n^2) operation do?
  - And what the heck does it mean if an operation is O(n log(n))?
  - And does somebody have to smoke crack to write an O(x!)?

Big-O for Eight Year Olds?

What does the term &lt;b&gt;referential transparency&lt;/b&gt; mean? I&#39;ve heard it described as &quot;it means you can replace equals with equals&quot; but this seems like an inadequate explanation.

What is referential transparency?

What are the main differences between the __Knuth-Morris-Pratt__ search algorithm and the __Boyer-Moore__ search algorithm?

I know __KMP__ searches for Y in X, trying to define a pattern in Y, and saves the pattern in a vector. I also know that __BM__ works better for small words, like DNA (ACTG).

What are the main differences in how they work? Which one is faster? Which one is less computer-greedy? In which cases?

What are the main differences between the Knuth-Morris-Pratt and Boyer-Moore search algorithms?

The question posed came about during a 2nd Year Comp Science lecture while discussing the impossibility of generating numbers in a deterministic computational device.

This was the only suggestion which didn&#39;t depend on non-commodity-class hardware.

Subsequently nobody would put their reputation on the line to argue definitively for or against it.  

Anyone care to make a stand for or against.  If so, how about a mention as to a possible implementation?



Could a truly random number be generated using pings to pseudo-randomly selected IP addresses?

The question is simple: I cannot understand the [Zipper][1] data structure.
 
My question is related to its uses with a Tree.
  
I want to understand how can I change the tree node using zipper. And how not to copy the whole tree (or the most part of it).

Please, clarify if I&#39;m wrong with zipper. Maybe it cannot help with the tree update?  
Or, maybe, it is possible to update the tree and I just cannot see the way?


  [1]: http://en.wikipedia.org/wiki/Zipper_(data_structure)

What is the Zipper data structure and should I be using it?

We have 8-bit, 16-bit, 32-bit and 64-bit hardware architectures and operating systems. But not, say, 42-bit or 69-bit ones.

Why? Is it something fundamental that makes 2^n bits a better choice, or is just about compatibility with existing systems? (It&#39;s obviously convenient that a 64-bit register can hold two 32-bit pointers, or that a 32-bit data unit can hold 4 bytes.)

Why is number of bits always(?) a power of two?

As I&#39;m always dissatisfied with existing editors, a project I always wanted to start is my own text editor. However doing text editing is serious business.

Besides analyzing the source code of existing text editors, is there any book or other resource (like academic work) about this topic? I&#39;m interested especially in something that teaches how to handle memory and how to manage text insertion (if you have a 100 MB file and want to add a char at *x* position, you can&#39;t just `memmove` the huge text block...).

Text editor theory

The question of whether P=NP is perhaps the most famous in all of Computer Science. What does it mean? And why is it so interesting?

Oh, and for extra credit, please post a proof of the statement&#39;s truth or falsehood. :)

What&#39;s &quot;P=NP?&quot;, and why is it such a famous question?

[Interfaces](http://php.net/Interfaces) allow you to create code which defines the methods of classes that implement it. You cannot however add any code to those methods. 

[Abstract classes](http://php.net/Abstract) allow you to do the same thing, along with adding code to the method. 

Now if you can achieve the same goal with abstract classes, why do we even need the concept of interfaces? 

I&#39;ve been told that it has to do with OO theory from C++ to Java, which is what PHP&#39;s OO stuff is based on. Is the concept useful in Java but not in PHP? Is it just a way to keep from having placeholders littered in the abstract class? Am I missing something?

What is the point of interfaces in PHP?

I&#39;m no beginner to using SQL databases, and in particular SQL Server.  However, I&#39;ve been primarily a SQL 2000 guy and I&#39;ve always been confused by schemas in 2005+.  Yes, I know the basic definition of a schema, but what are they really used for in a typical SQL Server deployment?

I&#39;ve always just used the default schema.  Why would I want to create specialized schemas?  Why would I assign any of the built-in schemas?

EDIT: To clarify, I guess I&#39;m looking for the benefits of schemas.  If you&#39;re only going to use it as a security scheme, it seems like database roles already filled that.. er.. um.. role.  And using it a as a namespace specifier seems to have been something you could have done with ownership (dbo versus user, etc..).

I guess what I&#39;m getting at is, what do Schemas do that you couldn&#39;t do with owners and roles?  What are their specifc benefits?

What good are SQL Server schemas?

Could any one give an explanation on how a DHT works?

Nothing too heavy, just the basics.

Simple basic explanation of a Distributed Hash Table (DHT)

For a person without a comp-sci background, what is a lambda in the world of Computer Science?

What is a lambda (function)?

Can someone provide a straightforward (but not simpler than possible) explanation of a transaction as applied to computing (even if copied from Wikipedia)? 

What is a database transaction?

I am interested in learning how a database engine works (i.e. the internals of it).  I know most of the basic data structures taught in CS (trees, hash tables, lists, etc.) as well as a pretty good understanding of compiler theory (and have implemented a very simple interpreter) but I don&#39;t understand how to go about writing a database engine.  I have searched for tutorials on the subject and I couldn&#39;t find any, so I am hoping someone else can point me in the right direction.  Basically, I would like information on the following:

 - How the data is stored internally (i.e. how tables are represented, etc.)
 - How the engine finds data that it needs (e.g. run a SELECT query)
 - How data is inserted in a way that is fast and efficient

And any other topics that may be relevant to this. It doesn&#39;t have to be an on-disk database - even an in-memory database is fine (if it is easier) because I just want to learn the principals behind it.

Many thanks for your help.

How to write a simple database engine

&lt;sub&gt;&lt;b&gt;NB&lt;/b&gt; This is not a question about how to use inline functions or how they work, more why they are done the way they are.&lt;/sub&gt;

The declaration of a class member function does not need to define a function as `inline`, it is only the actual implementation of the function.  For example, in the header file:

&lt;!-- language: lang-cpp --&gt;

    struct foo{
        void bar(); // no need to define this as inline
    }

So why does the inline implementation of a classes function *have* to be in the header file? Why can&#39;t I put the inline function the `.cpp` file? If I were to try to put the inline definition in the `.cpp` file I would get an error along the lines of:

&lt;!-- language: none --&gt;

    error LNK2019: unresolved external symbol 
    &quot;public: void __thiscall foo::bar(void)&quot;
    (?bar@foo@@QAEXXZ) referenced in function _main 
    1&gt;C:\Users\Me\Documents\Visual Studio 2012\Projects\inline\Debug\inline.exe 
    : fatal error LNK1120: 1 unresolved externals

Why are C++ inline functions in the header?

What does the expression &quot;Turing Complete&quot; mean? 

Can you give a simple explanation, without going into too many theoretical details?

What is Turing Complete?

What is the difference between cohesion and coupling?

How can coupling and cohesion lead to either good or poor software design?

What are some examples that outline the difference between the two, and their impact on overall code quality?

Difference Between Cohesion and Coupling

With a RESTful service you can create, read, update, and delete resources.  This all works well when you&#39;re dealing with something like a database assets - but how does this translate to streaming data?  (Or does it?) For instance, in the case of video, it seems silly to treat each frame as resource that I should query one at a time.  Rather I would set up a socket connection and stream a series of frames.  But does this break the RESTful paradigm?  What if I want to be able to rewind or fast forward the stream?  Is this possible within the RESTful paradigm?  So: **How do streaming resources fit within the RESTful paradigm?**

As a matter of implementation, I am getting ready to create such a streaming data service, and I want to make sure I&#39;m doing it the &quot;best way&quot;.  I&#39;m sure this problem&#39;s been solved before.  Can someone point me to good material?


How do streaming resources fit within the RESTful paradigm?

What is the &quot;purist&quot; or &quot;correct&quot; way to access an object&#39;s properties from within an object method that is not a getter/setter method?

I know that from outside of the object you should use a getter/setter, but from within would you just do:

Java:
   
    String property = this.property;

PHP:
    
    $property = $this-&gt;property;

or would you do:

Java:
   
    String property = this.getProperty();

PHP:

    $property = $this-&gt;getProperty();

Forgive me if my Java is a little off, it&#39;s been a year since I programmed in Java...


**EDIT:**

It seems people are assuming I am talking about private or protected variables/properties only. When I learned OO I was taught to use getters/setters for every single property even if it was public (and actually I was told never to make any variable/property public). So, I may be starting off from a false assumption from the get go. It appears that people answering this question are maybe saying that you should have public properties and that those don&#39;t need getters and setters, which goes against what I was taught, and what I was talking about, although maybe that needs to be discussed as well. That&#39;s probably a good topic for a different question though...

How would you access Object properties from within an object method?

Is it possible for a computer to &quot;learn&quot; a regular expression by user-provided examples?

To clarify:

* I do **not** want to learn regular expressions.
* I want to create a program which &quot;learns&quot; a regular expression from examples which are interactively provided by a user, perhaps by selecting parts from a text or selecting begin or end markers.

Is it possible? Are there algorithms, keywords, etc. which I can Google for?

**EDIT**: Thank you for the answers, but I&#39;m not interested in tools which *provide* this feature. I&#39;m looking for theoretical information, like papers, tutorials, source code, names of algorithms, so I can create something for myself.

Is it possible for a computer to &quot;learn&quot; a regular expression by user-provided examples?

What is an NP-complete problem? Why is it such an important topic in computer science?

What is an NP-complete in computer science?

The hover &quot;joke&quot; in #505 [xkcd][1] touts &quot;I call rule 34 on Wolfram&#39;s Rule 34&quot;.

I know [what rule 34 is in Internet terms][2] and I&#39;ve googled up [who Wolfram is][3] but I&#39;m having a hard time figuring out what Wolfram&#39;s Rule 34 is.

So what exactly is this &quot;Rule 34&quot;?

Here&#39;s the comic: [http://xkcd.com/505/][4].

  [1]: http://en.wikipedia.org/wiki/Xkcd
  [2]: http://www.urbandictionary.com/define.php?term=Rule%2034
  [3]: http://en.wikipedia.org/wiki/Stephen_Wolfram
  [4]: http://xkcd.com/505/


Wolfram&#39;s Rule 34 in XKCD

How do I check if a directed graph is acyclic? And how is the algorithm called? I would appreciate a reference.

How do I check if a directed graph is acyclic?

I&#39;ve been looking through a few notes based on this topic, and although I have an understanding of threads in general, I&#39;m not really to sure about the _differences between user-level and kernel-level threads_.

I know that processes are basically made up of multiple threads or a single thread, but are these thread of the two prior mentioned types?

From what I understand, kernel-supported threads have access to the kernel for system calls and other uses not available to user-level threads.

So, are user-level threads simply threads created by the programmer when then utilise kernel-supported threads to perform operations that couldn&#39;t be normally performed due to its state?

Difference between user-level and kernel-supported threads?

I saw [this question][1], and was curious as to what the **pumping lemma** was ([Wikipedia][2] didn&#39;t help much).  

I understand that it&#39;s basically a theoretical proof that must be true in order for a language to be in a certain class, but beyond that I don&#39;t really get it. 

Anyone care to try to explain it at a fairly granular level in a way understandable by non mathematicians/comp sci doctorates?


  [1]: https://stackoverflow.com/questions/461539/do-theoretical-computer-science-topics-such-as-regular-vs-non-regular-languages
  [2]: http://en.wikipedia.org/wiki/Pumping_lemma

What is the Pumping Lemma in Layman&#39;s terms?

A Y-combinator is a computer science concept from the &amp;ldquo;functional&amp;rdquo; side of things. Most programmers don&#39;t know much at all about combinators, if they&#39;ve even heard about them.

- What is a Y-combinator?
- How do combinators work?
- What are they good for?
- Are they useful in procedural languages?

What is a Y-combinator?

I&#39;ve used recursion quite a lot on my many years of programming to solve simple problems, but I&#39;m fully aware that sometimes you need iteration due to memory/speed problems.

So, sometime in the very far past I went to try and find if there existed any &quot;pattern&quot; or text-book way of transforming a common recursion approach to iteration and found nothing. Or at least nothing that I can remember it would help.

* Are there general rules?
* Is there a &quot;pattern&quot;?

Way to go from recursion to iteration

The point of const-correctness is to be able to provide a view of an instance that can&#39;t be altered or deleted by the user. The compiler supports this by pointing out when you break constness from within a const function, or try to use a non-const function of a const object. So without copying the const approach, is there a methodology I can use in C# that has the same ends?  

I&#39;m aware of immutability, but that doesn&#39;t really carry over to container objects to name but one example.


&quot;const correctness&quot; in C#

What class of languages do real modern regexes actually recognise?

Whenever there is an unbounded length capturing group with a back-reference (e.g. `(.*)_\1`) a regex is now matching a non-regular language. But this, on its own, isn&#39;t enough to match something like `S ::= &#39;(&#39; S &#39;)&#39; | ε` — the context-free language of matching pairs of parens.

Recursive regexes (which are new to me, but I am assured exist in Perl and PCRE) appear to recognize at least most CFLs.

Has anyone done or read any research in this area? What are the limitations of these &quot;modern&quot; regexes? Do they recognize strictly more or strictly less than CFGs, of LL or LR grammars? Or do there exist both languages that can be recognized by a regex but not a CFG _and_ the opposite?

Links to relevant papers would be much appreciated.


The recognizing power of &quot;modern&quot; regexes

After discovering the [Boost preprocessor&#39;s capabilities][1] I found myself wondering: Is the C99 preprocessor Turing complete?

If not, what does it lack to not qualify?

[1]:http://www.boost.org/doc/libs/1_41_0/libs/preprocessor/doc/index.html


Is the C99 preprocessor Turing complete?

So I&#39;m using an app that stores images heavily in the DB. What&#39;s your outlook on this? I&#39;m more of a type to store the location in the filesystem, than store it directly in the DB.

What do you think are the pros/cons?          

Storing Images in DB - Yea or Nay?

I do not have any experience with programming fractals. Of course I&#39;ve seen the famous Mandelbrot images and such.

Can you provide me with simple algorithms for fractals.

Programming language doesn&#39;t matter really, but I&#39;m most familiar with actionscript, C#, Java.

I know that if I google fractals, I get a lot of (complicated) information but I would like to start with a simple algorithm and play with it.

Suggestions to improve on the basic algorithm are also welcome, like how to make them in those lovely colors and such.



How to program a fractal?

I&#39;m trying to boil down the concepts of coupling and cohesion to a concise definition. Can someone give me a short and understandable explanation (shorter than the definitions on Wikipedia [here][1] and [here][2])? How do they interact?

Thanks.

Anybody have a good, short example?


  [1]: http://en.wikipedia.org/wiki/Coupling_%28computer_science%29
  [2]: http://en.wikipedia.org/wiki/Cohesion_%28computer_science%29

Coupling and cohesion

I&#39;m aware that MD5 has had some collisions but this is more of a high-level question about hashing functions. 

If MD5 hashes any arbitrary string into a 32-digit hex value, then according to the [Pigeonhole Principle][1] surely this can not be unique, as there are more unique arbitrary strings than there are unique 32-digit hex values.


  [1]: https://en.wikipedia.org/wiki/Pigeonhole_principle &quot;Pigeonhole Principle&quot;

How are hash functions like MD5 unique?

So given the following program:

----------

Is the time complexity of this program O(0)? In other words, is 0 O(0)?

I thought answering this in a separate question would shed some light on [this question][1].

EDIT: Lots of good answers here!  We all agree that 0 is O(1).  The question is, is 0 O(0) as well?

  [1]: https://stackoverflow.com/questions/905551/are-there-any-o1-n-algorithms



Is the time complexity of the empty algorithm O(0)?

When have you ever personally come upon the **&lt;a href=&quot;https://en.wikipedia.org/wiki/Halting_problem&quot;&gt;halting problem&lt;/a&gt;** in the field? This can be when a co-worker / boss suggested a solution which would violate the fundamental limits of computation, or when you realized yourself that a problem you were trying to solve was, in fact, impossible to solve.

The most recent time I came up with it was when studying type checkers. Our class realized that it would be impossible to write a perfect type checker (one that would accept all programs that would run without type errors, and reject all programs that would run with type errors) because this would, in fact, solve the halting problem. Another was when we realized, in the same class, that it would be impossible to determine whether a division would ever occur by zero, in the type-checking stage, because checking whether a number, at run-time, is zero, is also a version of the halting problem.

When have you come upon the halting problem in the field?

Are there any O(1/n) algorithms?

Or anything else which is less than O(1)? 


Are there any O(1/n) algorithms?

I was recently reading about artificial life and came across the statement, [&quot;Conway’s Game of Life demonstrates enough complexity to be classified as a universal machine.&quot;][1] I only had a rough understanding of what a [universal machine][2] is, and Wikipedia only brought me as close to understanding as Wikipedia ever does. I wonder if anyone could shed some light on this very sexy statement?

[Conway&#39;s Game of Life][3] seems, to me, to be a lovely distraction with some tremendous implications: I can&#39;t make the leap between that and calculator? Is that even the leap that I should be making?

[1]: http://www.alesdar.org/oldSite/IS/chap3-9.html
[2]: http://en.wikipedia.org/wiki/Universal_machine
[3]: http://en.wikipedia.org/wiki/Conway&#39;s_Game_of_Life

Why can Conway’s Game of Life be classified as a universal machine?

Why can&#39;t a computer program be proven just as a mathematical statement can?  A mathematical proof is built up on other proofs, which are built up from yet more proofs and on down to axioms - those truths truths we hold as self evident.

Computer programs don&#39;t seem to have such a structure.  If you write a computer program, how is it that you can take previous proven works and use them to show the truth of your program?  You can&#39;t since none exist.  Further, what are the axioms of programming?  The very atomic truths of the field?

I don&#39;t have good answers to the above.  But it seems software can&#39;t be proven because it is art and not science.  How do you prove a Picasso? 

All Theory Solutions on Gang of Coders

Total of 40 Theory Solutions