# All Questions

30,177 questions
22 views

### Can CNF with an input string be evaluated in logarithmic space?

I have been trying to solve satisfiability of {$<c, w>$ | $c$ is a CNF and $w$ is a binary string which satifies the $c$}. As first looks to me, it is satisiable in linear time ($O(n)$) since ...
47 views

### Proving $L = \{\langle M, w, n \rangle$ : $M$ accepts $w$ within $n$ steps $\}$ is decidable

Show the following problem is decidable: Given $w\in \Sigma^{*}$, $n\in \mathbb{N}$, and a Turing machine $M$, does $M$ on $w$ halt within $n$ steps. My Thoughts: I am new to proving results like ...
40 views

### How to understand a equation related to speaker recognition?

This question refers to the following paper: Support Vector Machines for Speaker and Language Recognition, W. M. Campbell, J. P. Campbell, D. A. Reynolds, E. Singer, P. A. Torres-Carrasquillo, ...
91 views
+200

### Morphing Hypercubes, Token Sliding and Odd Permutations

A month ago, I asked the following question math.exchange (https://math.stackexchange.com/questions/3127874/morphing-hypercubes-and-odd-permutations), but for completeness, I will include the details ...
46 views

### Symmetry of NP completeness

To show that some problem X is NP-complete, we usually show that it is in NP and that an efficient algorithm for deciding X implies an efficient algorithm for deciding some known NP-complete problem ...
17 views

### How can I implement the instruction jrlti (jump-register if less than immediate) in the MIPS one cycle datapath? [on hold]

I have trouble implementing the instruction jrlti. I don't have the right to modify the ALU so it must remain intact. Here is how the instruction is defined: [rs] < SignImm ? PC = [rt] : PC = PC ...
29 views

### how do we demonstrate using Boolean algebra that these NAND and NOR gate combinations are XOR gates

How do we demonstrate using Boolean algebra that these NAND and NOR gate combinations are XOR gates?
17 views

### Name for multiset with fractional amounts?

What do you call a set which accepts multiples of the same element, even in fractional amount? Is there even an established for this? Example from a video game about production chains: For a ...
9 views

### PhoneBookDirectory array in java, explained in detail in picture below [on hold]

The PhonebookEntry class exists and is working fine, so write the code as if you had it already.
15 views

### Generalized geography game graph

I'm studying the Sipser textbook for my theory of complexity class. In a part of the book (i.e., Space Complexity chapter), for showing that Generalized Geography game is PSPACE-complete, the author ...
1k views

### What is a Meta algorithm?

I am currently reading a survey paper on the multiplicative weight update meta-algorithm. I am not quite sure what they mean by "meta-algorithm". Is it simply a general algorithm that can be used for ...
33 views

### Are the two LTL properties $GF(\psi_1 \land F\psi_2 )$ and $GF(\psi_2 \land F\psi_1 )$ equivalent?

Is $GF(\psi_1 \land F\psi_2 )$ equivalent to the property $GF(\psi_2 \land F\psi_1 )$? Attempt: In the first property each state must eventually see $\psi_1$ and $\psi_2$, in the second property as ...
27 views

### Does this algorithm exhibit the same behavior as Selection Sort?

This is a homework question. I have been asked to identify what sort this code below implements. ...
5 views

### theoretical question about difference between transmitting stations in Bit-Map Protocol

i am wondering about the difference between the transmitting station in a bit map protocol. for instance, if we have 8 broadcasting stations numbered 0-7, and the racing (contenting) time is $t_0$ ...
43 views

### Can a language with some set of higher-order functions like map, fold and filter but without recursion or iteration be Turing complete?

I was reading this article and was wondering if there is any finite set of higher-order functions like map, fold or filter such that they could empower a language to be Turing complete even without ...
17 views

### State Transition Diagrams for XOR

I have found two different versions for State Transition Diagrams for XOR. I'm confused as to why one has 2 states and the other has 3. What are the implied states in each please? Are they both ...
14 views

### Color interpolation with a set of 2D points [on hold]

I am trying to modelize a physical problem of photoelasticity on a surface. I succeed to get an array of X,Y - coordinates of the surface and for each points I have a corresponding color in a RGB ...
19 views

### What is the intractable power of two in terms of computation? [on hold]

I learned a lot about complexity of algorithms, such as dynamic programming, sorting, etc. Now, I'm wondering what the actually intractable order of computation. Suppose CPU runs addition of two ...
27 views

### Random walks on Complete Binary Trees

Let $T$ be a complete binary tree of height $n$ and root $r$. A random walk starts at $r$, and at each step uniformly at random moves on a neighbor. There are $m$ random walkers all starting at $r$ ...
57 views

### How can i prove this asymptotic comparison? [duplicate]

This is an exercise that's part of my assignment, but it is optional and flagged as a "challenge". I would like to discuss its solution: Prove that: $$27\log{n} + \sqrt{n} = \theta(\sqrt{n})$$ ...
31 views

### Characterization of NFA whose equivalent (minimal) DFA has exponential number of states

(I don't know if there are standard names for this, so) Let's say that a Nondeterministic Finite Automaton (NFA) is $n$-expansive if it has $n$ states and any Deterministic Finite Automaton (DFA) ...
20 views

### On outdegree of a vertex garanteeing no-unique topological sort [on hold]

Given a directed acyclic graph with only one vertex with no incoming edge. Now assuming that it has more than one topological sort, what is the out-degree of the existence of a vertex guaranteeing ...
97 views

### Use dynamic programming toe

Let's say we have two arrays m and n containing the characters from the set a, b, c , d, e. ...
19 views

### Write the Brute Force Recursive Code to generate the longest substring containing k distinct vowels

Given a string s we have to find the length of the longest substring of s which contain exactly K distinct vowels. This is the problem statment given on geeksforgeeks Input : s = “artyebui”, k = 2 ...
31 views

### A binning (sorting) algorithm

Rules: A conveyor belt is giving you little boxes. They are labeled for your convenience: Box $1$, Box $2$,... For your inconvenience, though, you can't see the number (from $1...n$) hidden in it. You ...
18 views

39 views

### Is this a regular grammar? What rules make it regular? [on hold]

$\Sigma = \{a,b\}$ $G=\{\{A,B\}, \Sigma, \{A \to BB, B \to aB\mid bB\mid \epsilon\}, A\}$ Is this a regular grammar? Can you justify why is or is not rule by rule?
23 views

### Hardness of FNP vs Choice of Verifiers

A (T)FNP problem is induced by a NP language, say $L$. Usually in the notion of verifers, we define $L=\{x:\exists y,V(x,y)=1\}$, where $V$ is a poly-time verifier. The function version would be ...
22 views

### Affects of altering a line in “stop and wait” protocol(no noises)

what will happen if we change "to_physical_layer(&s)" to "to_physical_layer(&r)" in the following code(marked in the code where)? does it make the protocol fail? if so, show a scenario it ...
24 views

### How to make sure matrix completion can generate a matrix with values in expected range?

I am doing a matrix completion project. Assume that I have an incomplete matrix like ...
17 views

### 2D arrays in java [closed]

Forgive me if this is a stupid question, but I am a beginner in java and our teacher doesn explain it too well. I understand how to create a checkerboard in java. This is the code I am using. ...
10 views

### Determining total of primitive operations and running time for code [duplicate]

i needed some help with these problem in DSA For the given pseudo code: ...
39 views

### Circular Queue using Dynamic Array

I'm learning data structures from "Fundamentals of Data structures in C" by Sahni . In the topic, Circular Queue using Dynamic Array, the author has mentioned below point, Let capacity be the ...
23 views

### Find an algorithm to write a given word with this broken keyboard

I am submitting this interview question I have recently found Imagine you have a computer keyboard that has all the letters mismatched example: - typing q gives you a - typing w gives you b ...
88 views

### Search a sorted array that ends with zeros in O(log n) time

I have an array of size $m$, $[1,1,2,2,3,4,5,...,f,0,0, \cdots,0]$, where the first $n$ elements $1,1,2,2,3,4,5,\cdots, f$ are sorted. If I make a binary search including the 0's I get $O(\log(m))$. ...
51 views

### Can hypercomputation compute the impossible? [on hold]

There are things which are illogical/logically impossible (like saying that 2+2=4 and 2+2=5. Without changing anything in the axioms of mathematics or logic, this would be a contradiction and would be ...
It was a question I was asked in an online assessment for a company. Please help me in this question- Given an array, $A$ of size $N$ and an integer $P$ , find the subarray $B = A[i \dots j]$ such ...