All Questions

0
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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, ...
1
vote
0answers
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 ...
2
votes
2answers
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 ...
0
votes
0answers
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 ...
0
votes
2answers
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?
1
vote
1answer
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 ...
-3
votes
0answers
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.
0
votes
1answer
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 ...
7
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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. ...
0
votes
0answers
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$ ...
0
votes
2answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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$ ...
0
votes
3answers
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})$$ ...
1
vote
0answers
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) ...
0
votes
0answers
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 ...
2
votes
1answer
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. ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
0
votes
0answers
18 views

Is reduction from A_TM to EQ_TM possible to prove EQ_TM is undecidable?

\begin{align} EQ_{\mathrm{TM}} &= {\{ \langle M,N\rangle : L(M)=L(N) \}}\\ A_{\mathrm{TM}} &= {\{ \langle M,w\rangle : \textrm{TM $M$ accepts $w$}\}} \end{align} I can do it using $E_{\mathrm{...
1
vote
2answers
42 views

Algorithm to compact/simplify ranges?

I'm trying to create an algorithm in C# that given a list of ranges (segments) it produces a compacted list of them: Example 1 Input: [1, 3], [2, 6] Output: [1, 6] Example 2 Input: [1, 2], [2, 3] ...
-2
votes
0answers
11 views

Program Please solve in C# [on hold]

A Class Diagram clearly showing the class relationships. in a word document . Include a description of the class diagram that describes each class and indicates why it is a good design. Screen ...
1
vote
1answer
232 views

Binary strings such that the sum of 0's is not equal to twice the sum of 1's

Construct a context-free language for $L=\{w\in \{0,1\}^* \mid n_0(w)\not= 2n_1(w)\}$. Here $n_b(w)$ is the number of $b$'s in $w$. I can construct a CFL in the case $n_0(w)=2n_1(w)$, but I have no ...
0
votes
0answers
28 views

Book for algorithms [on hold]

I would like a book(s) that covers the following: Abstract data types and their uses, and specifications. Including" List, array, dictionary, stack, queue, priority queue, and graph theory related to ...
0
votes
0answers
6 views

What is difference between parallel virtual machine (PVM) and (mpi) Message passing Interface? [duplicate]

I am using beowulf cluster. And want to know the difference between parallel virtual machine(pvm) and message passing interface(mpi). Thank you.
-1
votes
0answers
42 views

dfa modulo 6 don't work correctly [on hold]

this dfa accepts the multiples of 6 in binary, I have tried it and it works with 0,6,12,18,24,30,36. this dfa accepts 0000, 0110,100,10010,11,000,11110 and 100100. the dfa has only worked correctly ...
0
votes
0answers
27 views

How to determine the post byte for 6809 indexed addressing Instruction [on hold]

Given an instruction such as LDA ,X how do you figure out what the post byte should be for the indexed addressing?
0
votes
1answer
27 views

Kolmogorov randomness for Pseudo random number generator

I am working on pseudo random number generation for one of my projects. My goal is to prove that the output is almost Kolmogorov Random since Kolmogorov complexity is uncomputable. So would appreciate ...
-1
votes
0answers
17 views

Static Routing in Cisco packet tracer [closed]

I have been working in a tool Cisco packet tracer. Configuring router in a static way. I have searched on the net but I couldn't find the solution. When I connnect my router0 to router3 By giving ...
3
votes
1answer
479 views

Complexity of many constant time steps with occasional logarithmic steps

I have a data structure that can perform a task $T$ in constant time, $O(1)$. However, every $k$th invocation requires $O(\log{n})$, where $k$ is constant. Is it possible for this task to ever take ...
0
votes
0answers
20 views

How to estimate processes using Semaphores - PLEASE HELP! I need help in pointing me in the right direction. How can I solve this? [closed]

Please I need assistance in understanding the context of this question. I have read about buffers and their uses but from the question the process is concurrent and I do not know if buffers allow ...
2
votes
0answers
21 views

On the robustness of BQP class

Typically the notion of quantum Turing machine is introduced with its transition function. $$ \delta:Q\times \Gamma\rightarrow \mathbb{C'}^{Q\times \Gamma\times\{L,R,0\}} $$ Where $\mathbb{C}'\...
-2
votes
1answer
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?
3
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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. ...
0
votes
0answers
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: ...
0
votes
1answer
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 ...
-1
votes
1answer
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 ...
3
votes
1answer
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))$. ...
0
votes
0answers
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 ...
0
votes
1answer
22 views

What is parallel virtual machine (pvm) and how it's different from mpi (message passing interface)

I am learning beowulf cluster. And I want to know what is pvm and how it's work and there is any difference between mpi and pvm
1
vote
2answers
155 views

Find the bitwise AND of a subarray closest to given number

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

15 30 50 per page