# Tag Info

62

Tail recursion is a special case of recursion where the calling function does no more computation after making a recursive call. For example, the function int f(int x, int y) { if (y == 0) { return x; } return f(x*y, y-1); } is tail recursive (since the final instruction is a recursive call) whereas this function is not tail recursive: int g(...

28

Here are three survey papers that examine the use of machine learning in time series forecasting: "An Empirical Comparison of Machine Learning Models for Time Series Forecasting" by Ahmed, Atiya, El Gayar, and El-shishiny provides an empirical comparison of several machine learning algorithms, including: "...multilayer perceptron, Bayesian neural ...

27

The main answer is that by exploiting semi-group structure, we can build systems that parallelize correctly without knowing the underlying operation (the user is promising associativity). By using Monoids, we can take advantage of sparsity (we deal with a lot of sparse matrices, where almost all values are a zero in some Monoid). By using Rings, we can do ...

24

The term "true concurrency" arises in the theoretical study of concurrent and parallel computation. It is in contrast to interleaving concurrency. True concurrency is concurrency that cannot be reduced to interleaving. Concurrency is interleaved if at each step in the computation, only one atomic computing action (e.g. an exchange of messages between sender ...

24

Positive result: persistence does not cost too much. One can show that every data structure can be made fully persistent with at most a $O(\lg n)$ slowdown. Proof: You can take an array and make it persistent using standard data structures (e.g., a balanced binary tree; see the end of this answer for a bit more detail). This incurs a $O(\lg n)$ slowdown: ...

23

No. That paper appears to be flawed. The flaw was explained in a comment by Tracy Hall on MathOverflow. A follow-up comment claims that the author later realized there is a flaw in his algorithm. As Yuval explains, it is not uncommon to see attempts from amateurs to solve these problems; they tend to be flawed. When it comes to results on famous open ...

21

Counting in the general case The problem you are interested in is known as #SAT, or model counting. In a sense, it is the classical #P-complete problem. Model counting is hard, even for $2$-SAT! Not surprisingly, the exact methods can only handle instances with around hundreds of variables. Approximate methods exist too, and they might be able to handle ...

20

Actually, until the 1950s the word computer was used to refer to a human who did arithmetic calculations. One (or more) of Richard Feynman's (many) autobiographies contains anecdotes about his time on the Manhattan project, where he ran the group of human computers. For arranging a group of humans to perform a complex computation they wouldn't start with ...

19

SMT solver is a SAT solver + decision procedure A SAT solver is a solver for a decision problem: the SAT problem is a decision problem. Additionally, this decision problem is "self-reducible": The SAT problem is self-reducible, that is, each algorithm which correctly answers if an instance of SAT is solvable can be used to find a satisfying assignment ...

19

Vertex Cover has an algorithm running in time $1.2738^k + nk$, and is thus faster than $2^n n^2$, even with $k=n$. You can check out Table of FPT races for a short list of FPT running times of different problems. Here, $n$ is the number of vertices and $k$ is the solution size. Also, the question Are there subexponential-time algorithms for NP-complete ...

19

Wikipedia says: An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm. $\mathcal{O}(\log n)$ is upper bounded by $\mathcal{O}(n)$, and $\mathcal{O}(n \log n )$ is upper bounded by $\mathcal{O}(n^2)$, therefore they are both in $P$.

18

Simply said, tail recursion is a recursion where the compiler could replace the recursive call with a "goto" command, so the compiled version will not have to increase the stack depth. Sometimes designing a tail-recursive function requires you need to create a helper function with additional parameters. For example, this is not a tail-recursive function: ...

18

There is no "official Turing test" so there's no concept of "officially pass[ing] the test". Turing described a methodology that one might use to evaluate artificial intelligences. The organizers of the event that Eugene Goostman won implemented that methodology in a particular way and the program satisfied the criteria the organizers had chosen. In that ...

18

This is pretty much what TU Eindhoven's Computing Science education, designed and implemented by Dijkstra and colleagues, was like from the time it started, around 1980, until Dijkstra's influence started to wane, somewhere half way through the 1990s. I started studying CS at Nijmegen University in 1982; a classmate did the same at TU Eindhoven. Every ...

17

My answer is based on the explanation given in the book Structure and Interpretation of Computer Programs. I highly recommend this book to computer scientists. Approach A: Linear Recursive Process (define (factorial n) (if (= n 1) 1 (* n (factorial (- n 1))))) The shape of the process for Approach A looks like this: (factorial 5) (* 5 (factorial 4)) ...

17

This is a good question. It appears that the term server was commonly used already in 1960s. For example, RFC 5, which was published in 1969, already uses the term, and it seems that it was in a common use already back then. However, the term client in this context seems to be much more recent; the earliest references that I was able to find are from 1978. ...

17

No, the graph isomorphism problem has not been solved. The paper you link to is from 2007–2008, and hasn't been accepted by the wider scientific community. (If it had been, I would have known about it.) Graph isomorphism, like many other famous problems, attracts many attempts by amateurs. They are almost always wrong. I would advise against trying to ...

15

I have not (nearly) read enough books to name $5000 worth of them. Therefore, I will suggest some groups of literature you should cover as well as point you towards selected representatives. I can not claim to have read most of the books in full myself, so I have to rely mostly on descriptions, cursory impression and reputation. I have looked into or worked ... 15 Although many papers in theoretical computer science claims practical applications for their work, this is unfortunately often simply not the case. Usually, either the problems are too far away from being something useful (too simplified), or the algorithms are too far away from being practical (e.g. hiding big constants in the O-notation). However, you ... 15 Category theory is not necessary to understand programming languages, it's not even necessary to do advanced research on programming languages. Most programming language people don't know (much) category theory. Category theoretical methods have been useful mostly in a small part of programming language research, namely in the analysis of functional ... 14 As AJed mentioned, ACM digital library and IEEE xplorer would be near the top of list. Additionally Goggling with advanced search for the name of the reference with the option to search for PDF or PS increases the change of a hit. Sometimes limiting the search to cs.xyz or xyz.edu increases the quality of results. If you are just starting out on a ... 14 There is actually a stronger result; A problem is in the class$\mathrm{FPTAS}$if it has an fptas1: an$\varepsilon$-approximation running in time bounded by$(n+\frac{1}{\varepsilon})^{\mathcal{O}(1)}$(i.e. polynomial in both the size and the approximation factor). There's a more general class$\mathrm{EPTAS}$which relaxes the time bound to$f(\frac{1}{\...

14

You haven't specified your computation model, so I will assume the comparison model. Consider the special case in which the array $B$ is taken from the list $$\{1,2\} \times \{3,4\} \times \cdots \times \{2n-1,2n\}.$$ In words, the $i$th element is either $2i-1$ or $2i$. I claim that if the algorithm concludes that $A$ and $B$ contain the same elements, ...

14

Structural complexity theory studies the relation between different complexity classes, usually uniform ones. The two most famous open questions in the field are: Is $\mathsf{P} \neq \mathsf{NP}$? Is $\mathsf{P} = \mathsf{BPP}$? In the past, a common pursuit in structural complexity theory was coming up with oracles that separate or join complexity classes....

13

Other answers have addressed this from a more theoretical perspective. Here is a more practical approach. For "typical" NP-complete decision problems ("does there exist a thingy that satisfies all these constraints?"), this is what I would always try first: Write a simple program that encodes your problem instance as a SAT instance. Then take a good SAT ...

13

If the state of the PRNG is finite, then it has a finite period. (By finite, I mean the same as we mean when we say that a finite-state automaton is finite: the set of all possible states is finite. For instance, if the state always fits into $b$ bits, for some fixed value of $b$, then its state is finite.) In practice, worrying about the period of the ...

13

Yes. The Turing machine that computes the Goodstein sequence beginning from its input and terminates when the sequence hits zero. It always terminates but this can't be proven in Peano arithmetic. I'm sure there are equivalent things for ZFC or any other system you might choose. Edit For ZF, Hartmanis and Hopcroft show that there's a Turing machine $M$ ...

13

The fact that P ≠ NP does not preclude the possibility that NP = co-NP, in which case NP ∩ co-NP = NP. So to further the discussion, let us assume that NP ≠ co-NP. In that case, Corollary 9 in Schöning's A uniform approach to obtain diagonal sets in complexity classes shows that there exists some language in NP – co-NP which is NP-intermediate. So NPI ...

13

Wikipedia says that the first use of tree in mathematics was by Cayley in 1857. Since the use in computer science is taken directly from mathematics, it seems more fundamental to ask when they originated there. Unless computer scientists originally called trees something else, the first computer scientist to use "tree" doesn't seem any more significant than,...

12

Apologies in advance for the shameless plug, but there is a paper of mine on a quantum lambda calculus that you may find interesting. It is called The Dagger Lambda Calculus and provides a higher-order representation for the diagrammatic circuits that the categorical school of quantum computation have introduced: http://arxiv.org/abs/1406.1633 You can also ...

Only top voted, non community-wiki answers of a minimum length are eligible