All Questions

31,062 questions
6 views

Number of steps - Count Change Procedure

I don't know if this is dupp question, i've already seen some explanations on why the procedure below is equal to $\theta(n^d)$ in terms of time complexity, being $d$ the number of coins. My question ...
4 views

Intersection of two deterministic parity automata

Given two deterministic parity automata $A_1=(Q_1,\Sigma,\delta,q_{01},c_1)$ and $A_2=(Q_2,\Sigma,\delta,q_{02},c_2)$ with the finite set of states $Q_i$, the finite alphabet $\Sigma_i$, the ...
23 views

Can any NP-Complete Problem be solved using at most polynomial space (but while using exponential time?)

I read about NPC and its relationship to PSPACE and I wish to know whether NPC problems can be deterministicly solved using an algorithm with worst case polynomial space requirement, but potentially ...
13 views

Maximum weighted matching for directed (non-bipartite) graphs

This post concerns mainly non-bipartite graphs. Edmonds (1961) have proposed the Blossom algorithm to solve the maximum matching problem for undirected graphs. The best implementation of it is due ...
16 views

How do I prove no algorithm exists for a given problem? [duplicate]

Is there a general framework for showing that a problem has no algorithm? For example, to show that two problems are equally as hard to each other, we use reduction. One example of where this was ...
7 views

Set of steps that cannot be implemented on a Turing machine

Is there an example of a "set of steps" that we thought was an algorithm, but later was shown not to be an algorithm because it could not be implemented on a Turing machine?
9 views

Linear programing, objective function. variable depending on the sign of another variable

I have the variable Si. How to express a variable Di in LP that satisfies: Di=100*Si if Si>=0 ...
27 views

Below I will list a concrete example and the confusion it causes. Let's first say we have a decision problem, which is: "Is X <= 400?" We define the alphabet as the set of natural numbers. The ...
16 views

Is Halting problem only applicable to infinite languages

Is the halting problem, only applicable for infinite languages? I assume that if the language is finite, then we can search over all words?
9 views

How does the Random Forest classification function

I was going the through Random forest classification trying to understand it and I stumbled on two equation and I was wondering if anyone knows their name. what are the names of the theorms or ...
3 views

Obtaining the dual variables of an optimisation problem with second order cone constraints solved using Gurobi

I'm solving an optimisation problem with linear and second order cone constraints, in other words the problem is convex and should have dual variables. I'm using Julia with JuMP to formulate the ...
21 views

Partitioning a set so both parts have sum at least $c$ times the total sum

Let $c\in(0,1/2]$ be a constant. Given a set of positive integers with sum $S$, is there a partition into two subsets such that both subsets have sum at least $cS$? If $c=1/2$, this is the famous ...
9 views

DSPACE(f(n)) closed under complement

Im thinking that you can create the complementary Language that is an element of DSPACE(f(n)) (f(n) >= log(n)) by adding a step to the algorithm that reverses the answer. By that the function f(n) ...
3 views

What's real world binary CSPs problem can be solved with AIMA JAVA CSP framework?

I am testing AIMA CSP framwork and I want to implement real world CSP problems.I know that AIMA CSP framework with java can only solve binary CSP problems and most real world CSPs problems are not ...
16 views

Binary search uneven split number of queries?

For even split binary search (repeated halving) number of queries is log with base 2. According to Skiena's Algorithm Design Manual, if the split in binary search is by ratio 1/3:2/3 instead of 1/2:1/...
17 views

A deterministic FA for $0^*1^*$ is required

A deterministic finite automaton without $\epsilon$ steps for the language $0^*1^*$ is required. Any nice picture ? I have created a NFA for this language which has 2 states $Q_1,Q_2$, both are ...
18 views

Multiway Cut question

I am trying to understand Multiway Cut, and basically how the Multiway Cut works. I am searching google many hours to find a good example to understand. A good example that I am trying to understand ...
11 views

are all problems solvable given infinite time?

Given a turing machine which has unlimited memory and time, can it solve all problems or are there a class of problems that cannot be solved even with unbounded power. Is there a way to prove this?
11 views

Why sum of two binary numbers cannot be determined in $NC^0$ but in $AC^0$?

Why sum of two binary numbers cannot be determined in $NC^0$ but it can be determined in $AC^0$?
18 views

Efficient algorithm to prune a graph

I'm faced to a problem I don't know the name, and for which I'm searching an efficient algorithm. From two list of nodes (without shared elements), the aim is to remove edges between element of the ...
18 views

In a Turing machine, what is the difference between the instruction table and the algorithm?

In a Turing machine, what is the difference between the instruction table and the algorithm? The instruction table seems to be an algorithm for completing the task no?
16 views

19 views

How can maximum number of minimum cuts of a graph be exactly $n \choose 2$?

According to my instructor, $n\choose 2$ is the maximum number of minimum cuts we can have on a graph. To prove this, he showed the lower bound using an n-cycle graph. To prove the upper bound, he ...
25 views

Reversible shuffle function

I would like to implement this algorithm with a minimum memory use: ...
20 views

Is $L(G) \subseteq L(R)$ decidable?

Is the following problem decidable? Given a context-free grammar $G$ and a regular expression $R$, is $L(G) \subseteq L(R)$? It is given that the following problem is undecidable Given a ...
24 views

Who studied the algorithms through the Cousera. Tell me whether to take a subscription? [on hold]

It is very difficult for me to learn algorithms. And so I think how best to start learning. And I also think whether I have enough material from the platform where I want to purchase a subscription. ...
9 views

Which Window models in stream data processing increasing monotonically?

Good morning, at the moment I try to understand which of the types of windows are increasing monotonically (not a strict increase) In Scholl we hat the following windows Tuple-based Sliding ...
34 views

Wikipedia says this grammar is LR(0), but Grammophone says it is not; is it?

E -> E * B . E -> E + B . E -> B . B -> 0 . B -> 1 . I am confused because Wikipedia cites this grammar as an example of an LR(0) grammar ...
17 views

Proving 3-Hitting Set is NP complete

Consider the following desicion problem: 3-Hitting Set - This problem is indentical to the classic Hitting Set problem with the following constraint: Each set has to be exactly 3 items long. Similarly ...
11 views

Difference between computational complexity theory and complexity theory

I read that complexity theory is the study of complex systems. While I associate computational complexity theory with classification of problems.
34 views

What are the benefits of languages that are not Turing complete?

Unfortunately I did a degree in CS without much theoretical computer science. One thing I used to hear is that sub languages, or languages which are not Turing complete, allow for better optimization? ...
8 views

Training of two 3x3 convolution layers vs training one 5x5 convolution layer

I'm not 100% sure this is the right stackexchange, please feel free to redirect me to another one. I know that two 3x3 convolution layers can be equivalent to one 5x5 convolution layer. I also know ...
How to proof problem L $\notin \texttt{DSPACE}(f)$
I want to proof a language $L$ is not in $\texttt{DSPACE}(f(n))$ the languages, that a deterministic Turing machine can decide with fixed tape length of $f(n)$ (wiki). Show: \begin{align*} L \notin ...