# All Questions

9,862 questions
2 views

### What is the relationship between “model of computation” and “algorithm”?

Traditionally, the usual definition you find for model of computation is "an abstract description of how a computation may be carried out". To me, this seems really close to the informal notion of ...
43 views

### Distinguishing a biased coin with a small set of tests

Say we have a "coin" $f : [n] \to \{\pm 1\}$ so that either $f$ is balanced, or $f$ is $\epsilon$-far from being balanced. It's a classic result that sampling $O(1/\epsilon^2)$ random points of $f$ ...
125 views

301 views

### Are all turing machines paths predictable?

I was recently studying partial solutions to the halting problem and came across the problem which I discuss below. In particular I was studying when it was computable to tell if a turing machine has ...
67 views

### When is extra vertex required in arbitrage detection using Bellman Ford?

I am studying applications of shortest path, in particular arbitrage. Specifically, I was reading these two resources: https://stackoverflow.com/questions/2282427/interesting-problem-currency-...
112 views

### Does every online algorithm has an offline counterpart?

According to the wikipedia page for Online algorithms, it states: "Not every online algorithm has an offline counterpart." At the time of asking this question there is no citation for this claim. ...
46 views

### who is able to solve that paper [closed]

Exams Determine the time complexity of the following program statement in java for (int i = 10; i < 20; i = i+ 1) { for (int j= 10; j < 20; j = j + 1) { Y=(a(i,j) ^2 )+5; System.out....
45 views

### Find optimum of a neural network computationally

Imagine a neural network, whose parameters (like number of layers, epochs of training, numbers of neurons, ...) can be specified as arguments. You don't know where the optimum is (say, the point where ...
66 views

### Pulling a graph across a partition

I am looking for the name for a particular graph property, if it has been studied, and efficient algorithms for computing it, if they exist. I realise that this may be a well known property that I am ...
73 views

### Impartial Combinatorial Games as a core of the final undergraduate project

Solving several problems of Impartial Combinatorial Games in Game Theory has drawn my attention. So that, I'd like to ask if it's possible to use this topic (e.g. Sprague Grundy theorem) as a core or ...
44 views

### Ordering tours in a Euclidean TSP according to (strictly) increasing length

Let $H$ be the set of all Hamiltonian cycles on the complete graph $K_n$ associated with a set of $n \geq 4$ points $P$ in the plane where edge weights are defined using the Euclidean distance between ...
28 views

### Do new algorithms or better machine learning methods have a better chance of making an impact on protein analysis in bioinformatics?

In other words, are new classic algorithms critical to bioinformatics or are they sort of a commodity now, providing small constant factor improvements to analysis runs, but not contributing ...
55 views

### Complexity of enumerating over promise problems and circuits?

Given an enumeration over all Turing Machine which run with increasing length, is there a complexity class'' which describes the complexity of determining whether a given TM satisfies the promise ...
162 views

### Graduate school for CS theory?

I am currently studying a bachelor's in (joint honours) Mathematics and Computer Science in the UK. I am intrigued by the sorts of problems present in theoretical computer science and I want to ...
71 views

### Are there cascade decompositions of machines that are more general than finite automata?

The idea of decomposing automata and their associated semi-groups into irreducible sub-components is due to Krohn & Rhodes and has been explored relatively thoroughly. Krohn & Rhodes gave an ...
85 views

### Solving the Halting problem for most inputs [closed]

Is it possible to solve the following version of the Halting problem : given any Turing machine and some input tape, the program should answer if this pair halts or not except possibly for one Turing ...
63 views

### Find shortest prefix to generate original string by overlapping

Given a string $S$, I want to find the prefix string $P$ of shortest length, such that the original string $S$ can be generated by concatenating copies of $P$ (where overlapping is allowed). For ...
48 views

### how to calculate inverse of entropy?

I was wondering how to calculate the inverse of a binary entropy function, seems very simple but iI don't think that the answer I get is correct (i get 1.1461). this is what i want to do: p should ...