All Questions

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 ...

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 ...

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 ...

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 ...

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 ...

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?

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

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 ...

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

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 ...

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 ...

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 ...

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) ...

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 ...

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/...

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 ...

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 ...

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?

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

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 ...

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?

I was trying to solve the following question while reviewing master theorem. Which of the following asymptotically grows faster. (a) $ T(n) = 4T(n/2) + 10n $ (b) $ T(n) = 8T(n/3) + 24n^2 $ (c) $ T(...

Domain-specific languages (DSLs) are common, but what are their advantages? I guess one obvious one is "expressivity" but what about optimization? If so, how? Are there any other advantages? I am ...

There are so many points in the coordinate system. When a specific point is given in the coordinate system, I want to find the closest point to the straight line distance. For example, if you have 800 ...

If the set $P$ is defined as the set of decision problems that can be solved by a deterministic Turing Machine in polynomial time, and matrix inversion using Gaussian elimination is $O (n^3)$, then ...

I was looking for some information on 1-in-3 SAT and came across this paper, last updated 9 days ago, which claims that the Polynomial Time Hierarchy collapses "to the level above P=NP". That's quite ...

Given two problems A and B. Given two algorithms a' and b'. a' solves A and b' solves B. If A reduces to B and B reduces to A. Then can we say anything about a' and b'? Are they the same?

I have learned python syntax (from books like fluent python or python cookbook etc.) and I want to learn the underlying concepts of computer science (in an abtract way), do you have some books/courses ...

When we are discussing the run time of an algorithm, are we referring to big-O notation or are we saying that the runtime is the same for all cases? For example; algorithm X runs in polynomial time.

Context: I intend on building a quadrotor which can generate a 3D virtual map of an area of which it captures photos with a 2D camera. I plan on first training a Convulational NN to return a depth ...

Given an array A of n numbers and integers k and x. We can perform the following operation any number of times (including zero times). Take exactly k numbers from the array and replace each of them ...

Question: A virtual memory system uses both paging and segmentation. Process virtual addresses consist of a total of 32 bits. The page size is 1024 (210) bytes. A page table may occupy at most one ...

Let N = (V, E) be a network in which the capacity of each edge is either 12 or 18. Prove or disprove: The value of a maximum flow for N can’t be 56. I'm trying to figure out how to definitely prove ...

In a country, some pairs of cities are connected by one-way roads. Each pair of cities have at most one road directly connected them. Each road has a cost for reversing its direction. Let $s,t$ be two ...

John Archibald Wheeler was a famous physicist It has been stated that he thought that there was a strong connection between undecidability and quantum physics This idea was given an early ...

There is the Quine–McCluskey algorithm for finding a minimal expression of a boolean expression in dis-junctive normal form. Would applying DeMorgan's rule to the minimal DNF result in the minimal CNF?...

T(m,n) = T(m-1,n) + T(floor(m/2), n-1) Base conditions T(m,n) = 1 when n = 0 T(m,n) = 0 when m < n Edited: Below is the code for which I want to know the time complexity in terms of m and n. <...

I have the following problem and i hope you could help me. Given is the following database schema, Student($\underline{\text{MatNo}}$, SName) Course($\underline{\text{CNo}}$, CName) Took($\...

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 ...

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

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 ...

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. ...

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 ...

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 ...

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 ...

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

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? ...

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 ...

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 ...

I have a few cameras which have been calibrated (using a checkerboard) so I know the fundamental matrix between an origin camera and each remaining camera I wish to take pairs of camera with no ...