All Questions

Filter by
Sorted by
Tagged with
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 ...
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/...
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(\...
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 - ...
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 ...
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 ...
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 ...
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/\...
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 ...
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 ...
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 $$\...
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\}]=...
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 ...
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 ...
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 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 ...
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 ...
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 ...

15 30 50 per page
1
2 3 4 5
920