All Questions
45,999
questions
0
votes
0
answers
3
views
Doubt regarding conjugations of permutations
I was studying the Barrington Theorem in https://homes.cs.washington.edu/~anuprao/pubs/CSE531Sp2020/lecture2.pdf when I found a doubt regarding permutations. Particularly, with conjugations.
It is ...
- 362
0
votes
0
answers
3
views
Is the set of instances of PCP, which have a solution, semi-decidable?
My idea was that it is because we can construct a TM M' that simulates a TM M that is to find a solution for a PCP instance. M' accepts if M accepts, rejects if M rejects, and doesn't halt if M does ...
0
votes
1
answer
5
views
Is this definition of the class P correct?
The definition of P is given by the union of all DTIME($n^k$) languages for $k >= 0$, where DTIME($n^k$) is the set of languages for which there exist a TM time-bounded by $T(n) = O(n^k)$. However, ...
0
votes
1
answer
15
views
Best data structure in C++ to store bodies in an N-body simulation?
I am writing an N-body simulation in C++ that has to be able to deal with large N ($N \le 10^6$).
Everything has been going well so far, but now that I have started to code in collisions between ...
0
votes
0
answers
6
views
Where can I find a list of logics with their corresponding calculus and computation phenomena?
I was watching some lectures by Prof. Pfenning on Proof Theory. He gave a list for some different kinds of judgments along with their calculus and computation phenomena that they can represent or ...
- 101
0
votes
0
answers
8
views
MIX computer's field specification
Section 1.3.1 describes Knuth's imaginary MIX computer. Its instructions consist of five (variable) bytes. I'm trying to understand the field specification byte.
A field is of the form (L:R) where L ...
0
votes
0
answers
9
views
Reduction from Diophantine Equation Problem to Halting Problem
I want to study the reduction from the Diophantine Equation Problem (Hilbert's tenth problem) to the Halting problem.
Can you either explain it to me or give me a credible source from which I can ...
- 1
0
votes
0
answers
11
views
Range updates in segment trees of sorted arrays (merge sort trees)
I understand range updates in segment trees using lazy propagation where each node is an integer.
Merge Sort Tree (source GFG): https://media.geeksforgeeks.org/wp-content/uploads/20220722205737/...
- 119
0
votes
1
answer
9
views
How to make LR(1) grammar for sequence that cannot have more "Down" than "Up" for any given prefix
I am working on a problem that asks me to write an LR(1) grammar that satisfies the following rules:
Consider a robot arm that accepts two commands: "Up" puts an apple in
the bag and "...
0
votes
2
answers
26
views
How to find the standard theta notation of this?
Hi i am practising standard theta notation:
How could i find the standard theta notation of the following :
2n + 3n^2(log n)^3 + 2
and
...
- 3
1
vote
0
answers
11
views
Applying Baum-Welch to multiple observed sequences iteratively
When using the Baum-Welch algorithm to train a hidden markov model you normally repeat it on some observed sequence iteratively until your values converge.
If you have multiple observed sequences, ...
- 11
0
votes
1
answer
66
views
Is this sorting problem NP-complete?
Consider array $A=(a_1,a_2,...,a_n)$ such that $a_i$s are positive integers. Moreover, we have $k$ binary tuples, each with length $n$. In each iteration, we choose one of those tuples, and decrease ...
-1
votes
0
answers
13
views
How is it possible to "lock" device's software?
How is it possible to "lock" device's software (i.e. only the manufacturer's own software works)? Can the CPU do that? It feels unnatural because hardware is "dumb" and not "...
-3
votes
0
answers
14
views
Binary Sequence
Computer is used to control security lights given as 0110010. The system is programmed in that there will be light when 10101010 trigger switch is activated while switching signal is given as 01010. ...
1
vote
1
answer
18
views
Are the indices of variables in the formula variable?
Let $L$ be an arbitrary language in $\Sigma_3$. Thus it can be written that $x \in L \Leftrightarrow \exists y^{p(|x|)} \forall z^{p(|x|)} \exists w^{p(|x|)} \langle x,y,z,w \rangle \in B$ where $p(\...
- 2,903
0
votes
1
answer
10
views
L is a recognizable undecidable language ,M is a Turing machine that recognizes L, does M reject or infinitely loop for s belonging to L-complement?
If $L$ is a decidable language, $M$ is a Turing machine that determines $L$. For $\forall s \in L$, M accepts, and for $\forall s \in \overline{L}$, M rejects
However, my question is that
If $L$ is a ...
- 183
0
votes
0
answers
20
views
Linearly independent paths with loops and cyclomatic complexity
I'm trying to find out what are the linearly independent paths in this control flow graph.
Later Edit: Sorry. I've cleaned up the drawing is was confusing...
The cyclomatic complexity is 3 = 6 edges - ...
- 229
1
vote
1
answer
23
views
Encoding "all-except" constraints in CNF
I am looking for an efficient CNF encoding of the following situation: I have sets of boolean literals $A = \{ a_1, \ldots, a_m \}$, $B = \{ b_1,\ldots, b_n \}$ and subsets $B_1, \ldots, B_m$, where ...
- 166
2
votes
1
answer
61
views
Is there a name for this kind of binary tree?
While working on a math problem the following tree structure came up:
o
\
o
/
o
/ \
o o
/ \ /
It is a binary tree with the ...
- 121
1
vote
1
answer
69
views
What is the smallest NFA you can design for {a^n : n =/= 1003}
What is the smallest NFA that could be design for a^n where n!=1003?
I have been racking my brain at this for a while but still can't reduce the number of states required from 1004. Here state(1003) ...
- 13
0
votes
0
answers
27
views
Divide and conquer problem
Problem:
Given a set of n intervals I = [a1, b1],[a2, b2], . . .[an, bn]. Here ai < bi for all i = 1
to n. Devise a Divide and Conquer algorithm to compute the length of the biggest
overlap between ...
- 3
2
votes
1
answer
34
views
Find if there is more than one path between two vertices such that no vertices are used more than once
So I have an undirected graph G(V, E). We may assume there is always at least one path between any two vertices. I want to efficiently check if there are at least 2 different paths between x and y ...
- 21
1
vote
0
answers
13
views
Determining when a substring has a unique parse forest
Given an arbitrary (potentially ambiguous) context free grammar $G: \mathbb{G}$, and string $\alpha: \Sigma^\ast$, is there a decision procedure that returns whether appending and/or prepending ...
- 123
-1
votes
0
answers
16
views
Inequation Proof - Graph Optimization
I have a graph problem in which the edge cost depends on the node demand. However, I do not have the demand before calculate the shortest path.
I want to prove that if: $a +C.b \leq c +C.d$,
then: $a +...
- 1
2
votes
1
answer
15
views
Finding general time complexity for recurrence relation $T(n)=aT(n/\alpha)+bT(\beta n/\alpha)+f(n)$
I was given an assignment in which I had multiple recurrence relations and I had to find their Big-oh time complexities. Nearly all of the recurrence relations were of the form as under:
$$T(n)=aT(n/\...
- 121
0
votes
0
answers
12
views
Does plantri software provide the option to screen out abstract non-isomorphic graphs
This may be off topic, but I still want to find a solution.
The plantri software can generate planar graphs, but it may result in abstract isomorphism when generating planar graphs with a connectivity ...
- 121
0
votes
1
answer
29
views
Why is flex the best choice for handling mathematical content? (a question about approach0)
This questions is about the work A novel similarity-search method for mathematical content in LaTeX markup and its implementation.
Mr. Wei Zhong uses flex lexer generator.
Now, supose I find an ...
- 137
0
votes
1
answer
50
views
Why is a LALR parser the correct choice for parsing mathematical content? (a question about Approach0)
This questions is about the work A novel similarity-search method for mathematical content in LaTeX markup and its implementation.
The parser used by Wei Zhong is LALR.
Now, supose I have to parse a ...
- 137
4
votes
1
answer
61
views
Possibly Tractable Variation of Suguru Puzzles
I'm currently investigating the computational complexity of a modified one-dimensional Suguru puzzle. The general Suguru puzzles were recently proven to be NP-complete (see here). My investigation ...
- 41
1
vote
1
answer
132
views
Finding Optimal Configuration of Formula without trying every Permutation
I have a math problem I need to solve so I can complete an optimisation in a computer program. My initial approach was just to brute force all the possible permutations but it got out of hand quite ...
- 129
0
votes
1
answer
48
views
Time complexity of T(n) = 1600T(n/4) + n!
I'm trying to find the time complexity of T(n) = 1600T(n/4) + n! . So far I have thought of changing n! to something usable by the master theorem. Stirling's approximation gives us the equation
$$\...
- 1
0
votes
2
answers
37
views
Finding the length of the longest palindrome in the given array
The problem that I'm trying to solve is:
Given an array of length N, I want to find the length of the longest palindrome in the given array.
With palindrome, we refer to a word, phrase, or sequence ...
0
votes
0
answers
19
views
Manipulating a binary tree representation
I am designing a discrete probability distribution with a string of binary values as an input $\{s_i\}\in\{S_i\}$, and binary outputs $e\in E$ with Bernoulli probability $P(E=1|\{S_i\})=XOR[\{S_i\}]=...
- 1
0
votes
1
answer
26
views
Strong NP-completeness of permuted kernel problem
The permuted kernel problem is NP-complete problem by simple reduction from partition problem. In fact, it is strongly NP-complete by reduction from 3-partition. The literature points to Garey and ...
- 4,353
0
votes
0
answers
20
views
What type of tree traversal should be performed to obtain the same splay tree?
I'm trying to figure the following:
Given splay tree number 1. Perform a tree traversal on it and insert each node into splay tree number 2 in that order. What type of tree traversal should be ...
- 231
2
votes
1
answer
36
views
Is checking whether a a set of 3-literal clause is satisfiable such that every literal in each clause is either all true or all false NP-complete?
I want to know if checking whether a a set of 3-literal clause is satisfiable such that every literal in each clause is either all true or all false NP-complete?
By 3-literal clause, I mean it can ...
- 29
0
votes
1
answer
23
views
Given a graph `G`, what is the maximum number of "minimum" cycles it could have?
In graph G: a cycle $A$ is a subcycle of cycle $B$ if there exists vertices $c$ and $d$ such that:
$cd$ is an edge of $A$.
$F$ is the resulting path of $A$ after ...
- 411
0
votes
0
answers
29
views
Is there any way to tell which states are final states in a finite state automata given only its grammar?
Problem
In the problem, I was given the grammar for a non-deterministic finite state automata (NDFSA). There was no other useful context given. The problem asks you to use this grammar to draw the ...
0
votes
1
answer
34
views
O(nlogn)-time complexity
Is there a $O(nlogn)$ time algorithm for computing $p(x)=\sum\limits_{i=0}^na_ix^i$ ?
I think with the method below I get O(n), but I need O(nlogn)
Hint: there's a way to calculate $x^i$ more ...
- 3
2
votes
0
answers
33
views
How to delete node from RB-tree
I need to implement my own red-black tree and I am stuck with deletion. I have found this book (Introduction to Algorithms) (p.222) and in the following code I can't understand this marked line.
...
0
votes
1
answer
17
views
Are there any other language classes of time complexity between the P language class and the NP language class?
$P$ is the language class that is decidable in polynomial time by a deterministic Turing machine.
$NP$ is a language class that is decidable in polynomial time by non-deterministic Turing machines and ...
- 183
-4
votes
2
answers
60
views
A string that contains aabb, does this work?
Can you verify this like please bro please tell me the answer to my question
- 1
1
vote
3
answers
43
views
What set.seed() mean in the Monte Carlo method
I'm trying to learn the implementation of the Monte Carlo method in R language. I am following a course with an example of predicting results for a board game. What I'm not understanding is the usage ...
- 11
1
vote
0
answers
60
views
Successive shortest paths with fixed costs and costs per unit
I have a directed graph $G(V,A)$ with arc costs $c_{ij} = \alpha_{ij}1_{x_{ij}>0} +\beta_{ij}x_{ij}$, where $\alpha_{ij}$ and $\beta_{ij}$ are, respectively, a fixed cost and a cost per unit of ...
- 111
0
votes
0
answers
21
views
Proving that $c^Tx_B<c^T\hat x_\hat B$ holds [closed]
I have this problem: Given the linear optimization problem $\max\{c^Tx|x\in P\}$, where $P\subset \mathbb{R}^n$ is a polyhedron. Further, let $x_B$ be a non-degenerate basis solution to the basis B. ...
0
votes
1
answer
92
views
What is this question actually asking for me to solve?
(15 marks) Suppose a ray comes from a point (2, 8) and hits at mirror point (6, 6). Assume
that perpendicular vector a point (6, 6) is 𝑛̅= (0, 3). Find the reflection emitting point from
(6, 6).
[...
- 1
0
votes
0
answers
38
views
Goedel's theorem, halting problem and irreducible complexity
I have a vague idea on the tip of my mind that I can only convey through examples.
Gödel's theorem states that some systems (ZFC, for example) are always incomplete in the sense that new axioms (which ...
-2
votes
0
answers
15
views
Difference between systems of systems, distributed systems, and complex systems?
Also, what are the learning resources about them. For example, an introductory book about their design and architecture
- 97
2
votes
1
answer
22
views
Whether the class of languages with time complexity between polynomial and exponential is an NP language？
We know that the P language class is a polynomial-time solvable language class, and the NP language class can be determined in exponential time. And there exist some languages that can be decided only ...
- 183
1
vote
2
answers
87
views
Definition of complexity of an algorithm
In a sorting algorithm, While computing the complexity of an algorithm why do we only account for the number of comparisons done but not the number of swappings done?
And what's the formal definition ...
- 11