All Questions

6
votes
1answer
465 views

Why can L3 caches hold only shared blocks?

In a recent CACM article [1], the authors present a way to improve scalability of shared and coherent caches. The core ingredient is assuming the caches are inclusive, that is higher-level caches (e....
0
votes
1answer
144 views

Problem with the definition of P

In "Introduction to Algorithms: 3rd Edition" there is Theorem 34.2, which states $P = \{ L \mid L \text{ is accepted by a polynomial-time algorithm} \}$ "Accepted in polynomial-time" is defined by:...
4
votes
2answers
8k views

Time complexity formula of nested loops

I've just begun this stage 2 Compsci paper on algorithms, and stuff like this is not my strong point. I've come across this in my lecture slides. ...
4
votes
1answer
278 views

What is known about coRL and RL?

Wondering about any known relations between $\mathsf{RL}$ complexity class (one sided error with logarithmic space) and its complementary class, $\mathsf{coRL}$. Are they the same class? What are $\...
12
votes
3answers
3k views

How fast can we find all Four-Square combinations that sum to N?

A question was asked at Stack Overflow (here): Given an integer $N$, print out all possible combinations of integer values of $A,B,C$ and $D$ which solve the equation $A^2+B^2+C^2+D^2 = N$. This ...
5
votes
2answers
639 views

Automated geometric theorem-proving using synthetic methods

This question is about geometric theorem proving and is inspired by this Math.SE post. Currently, Euclidean-geometric theorem provers, as referred to in the post, use coordinate geometry to convert ...
3
votes
1answer
182 views

Factor a grammar

Consider the context free grammar: $\qquad \begin{align} \mathrm{bill} &\to \mathrm{items}\ \mathrm{total}\ \mathrm{vat} \\ \mathrm{items} &\to \mathrm{item} \mid \mathrm{item}\ \...
10
votes
1answer
711 views

Micro-optimisation for edit distance computation: is it valid?

On Wikipedia, an implementation for the bottom-up dynamic programming scheme for the edit distance is given. It does not follow the definition completely; inner cells are computed thus: ...
5
votes
1answer
2k views

Optimization problem vs decision problem - reduction

Assume we have an optimization problem with function $f$ to maximize. Then, the corresponding decision problem 'Does there exist a solution with $f\ge k$ for a given $k$?' can easily be reduced to ...
5
votes
1answer
2k views

Examples of undecidable problems whose intersection is decidable

I know that given two problems are undecidable it does not follow that their intersection must be undecidable. For example, take a property of languages $P$ such that it is undecidable whether the ...
2
votes
1answer
575 views

Showing that the set of TMs which visit the starting state twice on the empty input is undecidable

I'm trying to prove that $L_1=\{\langle M\rangle \mid M \text{ is a Turing machine and visits } q_0 \text{ at least twice on } \varepsilon\} \notin R$. I'm not sure whether to reduce the halting ...
4
votes
1answer
346 views

How to implement simulation on two LTSs?

Does any one know how to implement the simulation relation on two labelled transition systems (LTS)? I know how to do it for branching bi-simulation. The signature refinement theorem is used for ...
27
votes
4answers
12k views

Generalised 3SUM (k-SUM) problem?

The 3SUM problem tries to identify 3 integers $a,b,c$ from a set $S$ of size $n$ such that $a + b + c = 0$. It is conjectured that there is not better solution than quadratic, i.e. $\mathcal{o}(n^2)$....
7
votes
1answer
841 views

Solving the recurrence relation $T(n) = 2T(\lfloor n/2 \rfloor) + n$

Solving the recurrence relation $T(n) = 2T(\lfloor n/2 \rfloor) + n$. The book from which this example is, falsely claims that $T(n) = O(n)$ by guessing $T(n) \leq cn$ and then arguing $\qquad \...
6
votes
6answers
428 views

Looking for books on creating and understanding theorems targeted at Computer Science

In studying logic to understand verifying programs I have found that there are books on logic targeted at Computer Science e.g. Logic in Computer Science: Modelling and Reasoning about Systems ...
5
votes
1answer
488 views

Period in postulate; what does it mean?

While I am learning a lot from others here at the Computer Science site, I must admit that I don't get as much out of some questions and answers since I typically don't understand the theorems to the ...
2
votes
1answer
6k views

Example using Penetrance & Branching Factor in State-space Heuristic Search

I need an example for how to calculate penetrance and branching factor of the search tree in in state-space heuristic search. The definitions are as following. Penetrance $P$ is defined by $\qquad \...
1
vote
0answers
206 views

Finding a sequence of numbers where every product of two mod k is unique

I want to make a sequence of numbers, where I pick the numbers $a_{0}, a_{1},..,a_{n}$. The length of the sequence is $n+1$. Now I want the product of any pair of two numbers in the sequence modulo $...
4
votes
1answer
198 views

Semantic similarity in text

Is there a relatively simple way of telling if two pieces of text are semantically similar? Some assumptions that are valid: It is all english I have a list of all the important nouns Are there any ...
18
votes
1answer
1k views

Generating inputs for random-testing graph algorithms?

When testing algorithms, a common approach is random testing: generate a significant number of inputs according to some distribution (usually uniform), run the algorithm on them and verify correctness....
5
votes
1answer
3k views

Is MAX-SAT NP-hard?

Is the MAX-SAT problem NP-hard? From the Wikipedia page: The MAX-SAT problem is NP-hard, since its solution easily leads to the solution of the boolean satisfiability problem, which is NP-complete ...
2
votes
2answers
497 views

Counting with constant space bounded TMs

The problem, coming from an interview question, is: You have a stream of incoming numbers in range 0 to 60000 and you have a function which will take a number from that range and return the ...
0
votes
1answer
1k views

How to calculate the depth of sorting networks?

I have trouble understanding how to calculate the depth of a sorting network on $n$ inputs. For example, in case of selection sort, we have: $\qquad \displaystyle D(n)=D(n-1)+2\\\qquad D(2)=1$ ...
12
votes
4answers
28k views

Am I right about the differences between Floyd-Warshall, Dijkstra and Bellman-Ford algorithms?

I've been studying the three and I'm stating my inferences from them below. Could someone tell me if I have understood them accurately enough or not? Thank you. Dijkstra algorithm is used only when ...
13
votes
2answers
627 views

Do non-computable functions grow asymptotically larger?

I read about busy beaver numbers and how they grow asymptotically larger than any computable function. Why is this so? Is it because of the busy beaver function's non-computability? If so, then do all ...
3
votes
1answer
142 views

Can bottom-up architectures be effectively programmed in top-down paradigms?

The subsumption architecture, proposed by Rodney Brooks in 1986, is a "bottom-up" approach, in which robots are designed using simple hierarchical models. These models build upon and subsume the ...
3
votes
0answers
766 views

Analysis of a linear-time algorithm for longest palindromic substring

Background $\newcommand\ldotd{\mathinner{..}}$Last month, I heard about a new linear-time algorithm to determine the longest palindromic substring called Jeuring's algorithm. It seemed interesting, ...
10
votes
2answers
230 views

Complexity of computing $n^{n^2}$

What is the complexity of computing $n^{n^2},\;n \in \mathbb{N}$?
6
votes
1answer
166 views

Looking for a book that derives and constructs a model checking application

I am teaching myself program verification and am currently learning proof assistants. I have the book Handbook of Practical Logic and Automated Reasoning which gives the proofs necessary for the ...
4
votes
1answer
4k views

Semantic clustering

I have a very specific question about semantic clustering. I have a list of words/phrases. I want to run an intelligent semantic clustering algorithm on this list. Please let me know what the ...
11
votes
1answer
453 views

Inferring refinement types

At work I’ve been tasked with inferring some type information about a dynamic language. I rewrite sequences of statements into nested let expressions, like so: <...
26
votes
4answers
68k views

What exactly is the difference between supervised and unsupervised learning?

I am trying to understand clustering methods. What I I think I understood: In supervised learning, the categories/labels data is assigned to are known before computation. So, the labels, classes or ...
4
votes
1answer
358 views

Order preserving encoding of strings to numbers

I want to encode strings as real numbers while preserving order. The order of the strings is the lexicographic order (as used in phone books); the order of the numbers is the standard order. Is there ...
3
votes
1answer
218 views

Source entropy and other questions related to information theory

Kolmogorov-Sinai entropy (KS) explains the mathematical concept behind KS entropy. $$h ( T ) =\sup\limits_{\xi} \, h ( T , \xi )$$ defines the formula for KS where the left-hand side is nothing but ...
11
votes
1answer
597 views

Bound on space for selection algorithm?

There is a well known worst case $O(n)$ selection algorithm to find the $k$'th largest element in an array of integers. It uses a median-of-medians approach to find a good enough pivot, partitions ...
6
votes
1answer
273 views

Determining whether a CFG is $LL(k)$ for any $k$?

In Knuth's original paper on $LR(k)$ grammars, he proved that the decision problem "Given a CFG $G$, is there a $k$ such that $G$ is an $LR(k)$ grammar?" is undecidable. Is there a similar result ...
5
votes
3answers
207 views

Why does NTIME consider the length of the longest computation?

In Sipser's textbook "Introduction to the Theory of Computation, Second Edition," he defines nondeterministic time complexity as follows: Let $N$ be a nondeterministic Turing machine that is a ...
5
votes
1answer
208 views

Notation for operational semantics that can be used in code comments

I'm defining an intermediate language for a multi-backend code generator that I'm writing. I want to document the operational semantics for this intermediate language in a way that is readable both ...
3
votes
1answer
89 views

distinction between $\textbf{P}^{\# \textbf{P}}$ and $\# \textbf{P}$-Complete

We know that $\# \textbf{P}$ is closed under polynomial sums, i.e., sum of polynomially many $\# \textbf{P}$ functions is still in $\# \textbf{P}$. Functions in $\textbf{P}^{\# \textbf{P}}$ are those ...
16
votes
1answer
860 views

Universal simulation of Turing machines

Let $f$ be a fixed time-constructable function. The classical universal simulation result for TMs (Hennie and Stearns, 1966) states that there is a two-tape TM $U$ such that given the description of ...
5
votes
1answer
2k views

Determining Probability from a Graph

Lets say I have node A that connects to 10 other nodes. 6 of those nodes have Property 1 and the other 4 have Property 2. How can I easily determining the probability of landing on a node with ...
7
votes
1answer
563 views

Origins of the term “distributed hash table”

I am currently researching for my diploma thesis in computer science with a topic in the area of distributed hash tables. Naturally, I came to the question were the term distributed hash table came ...
22
votes
3answers
3k views

What are staged functions (conceptually)?

In a recent CACM article [1], the authors present an implementation for staged functions. They use the term as if it was well-known, and none of the references looks like an obvious introduction. ...
3
votes
1answer
935 views

How to call something that can be either a terminal or a nonterminal?

I had written a compiler compiler a few years ago and I'm now cleaning it up, improving it, and turning it into C. I came across a terminology problem however that I remember in the past I couldn't ...
10
votes
2answers
210 views

Determining the particular number in $O(n)$ time and space (worst case)

$\newcommand\ldotd{\mathinner{..}}$Given that $A[1\ldotd n]$ are integers such that $0\le A[k]\le m$ for all $1\le k\le n$, and the occurrence of each number except a particular number in $A[1\ldotd n]...
10
votes
1answer
428 views

Are regular languages closed under sort (Parikh image)?

Assume $L$ is a regular language over an ordered alphabet. Is the language built by taking every word in $L$ and sorting it always a regular language?
11
votes
1answer
595 views

Can top SAT-solvers factor easy numbers?

Modern SAT-solvers are very good at solving many real-world examples of SAT instances. However, we know how to generate hard ones: for instance use a reduction from factoring to SAT and give the RSA ...
4
votes
1answer
332 views

Choosing an element from a set satisfying a predicate uniformly at random in $O(1)$ space

We are given a set of objects, say integers, $S$. In addition, we are given a predicate $P$, for example $P(i): \Leftrightarrow i \geq 0$. We don't know in advance how many elements of $S$ satisfy the ...
1
vote
1answer
285 views

Which method for ODE instead of Euler's?

I need a super-fast method for ordinary differential equations. Should I use the midpoint method? I need this for a reaction-diffusion system (Gray-Scott).
0
votes
1answer
464 views

Does this regular expression equal this automata?

I just came across an exercise which is to find a regular expression for the following automata, such that the regular expression and the automata generate the same language. One solution presents ...

15 30 50 per page