All Questions

0
votes
0answers
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 ...
0
votes
0answers
5 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 ...
3
votes
2answers
24 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 ...
1
vote
0answers
15 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 ...
0
votes
1answer
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 ...
0
votes
0answers
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?
0
votes
1answer
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 ...
0
votes
2answers
27 views

Questions about Turing Machine

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 ...
0
votes
0answers
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?
0
votes
0answers
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 ...
0
votes
0answers
4 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 ...
3
votes
1answer
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 ...
0
votes
0answers
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) ...
0
votes
0answers
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 ...
0
votes
1answer
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/...
1
vote
1answer
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 ...
0
votes
1answer
19 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 ...
0
votes
0answers
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?
0
votes
0answers
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$?
0
votes
0answers
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 ...
0
votes
1answer
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?
0
votes
1answer
19 views

Master theorem: When a $f(n)$ is smaller or larger than $n^{log_b a}$by less than a polynomial factor

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(...
-1
votes
0answers
37 views

What are the motivations for using a domain-specific language in particular within the database field? [on hold]

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 ...
0
votes
2answers
21 views

How to find the nearest point in the coordinate system

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 ...
0
votes
2answers
23 views

Matrix Inversion in the complexity class $P$ seen as a decision problem

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 ...
1
vote
2answers
80 views

Why does coNP⊆NP∖P imply that the polynomial hierarchy collapses?

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 ...
0
votes
2answers
23 views

Do algorithms reduce?

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?
0
votes
1answer
21 views

Introduction to computer science for ML [on hold]

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 ...
1
vote
1answer
14 views

In complexity theory, does polynomial time refer to the big-O notation?

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.
0
votes
0answers
4 views

Constructing a 3D virtual map from 2D Depth Maps and $x, y, z, \theta$ coordinates

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 ...
1
vote
0answers
22 views

Take k numbers from the array and xor them with x to get maximum sum

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 ...
0
votes
0answers
9 views

Segmentation with paging

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 ...
0
votes
0answers
21 views

Maximum Flow in a Network

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 ...
0
votes
0answers
21 views

Graph problem with cities in a road network

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 ...
1
vote
1answer
41 views

Did Wheeler really believe that physics was undecidable?

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 ...
0
votes
0answers
15 views

A Quine–McCluskey variant for conjunctive normal formal?

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?...
1
vote
0answers
31 views

How to solve 2 variable recursion?

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. <...
0
votes
0answers
19 views

For which instance are those relational queries equivalent?

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($\...
2
votes
2answers
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 ...
0
votes
0answers
25 views

Reversible shuffle function

I would like to implement this algorithm with a minimum memory use: ...
1
vote
1answer
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 ...
0
votes
1answer
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. ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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.
0
votes
1answer
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? ...
0
votes
0answers
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 ...
1
vote
1answer
20 views

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 ...
0
votes
0answers
9 views

How to use known Projection Matrices of cameras to generate new fundamental matrix located correctly in 3D space?

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

15 30 50 per page