# All Questions

31,820 questions
Filter by
Sorted by
Tagged with
32 views

### What is meant by a preemptive algorithm?

The definition on Google says 'serving or intended to pre-empt or forestall something, especially to prevent attack by disabling the enemy.' So, how does this relate to an algorithm, especially the ...
73 views

### Difference between computation in proposition proof and definitional computation?

As stated in equality at nLab, "computational equality" is about computational steps which take for example, $s(s(0))+ s(0)$ to $s(s(s(0)))$ and it acts exactly and can be considered same as ...
15 views

### Deterministic Time Hierachy Proof by Arora and Barak: Question about time to simulate Turing Machine $M$ that decides separating language

In the book "Computational Complexity: A modern approach", Arora and Barak proof the statement that $DTIME(n) \subsetneq DTIME(n^{1.5})$ by constructing a separating language $L \in DTIME(n^{1.5})$ ...
35 views

### Quota sampling participants

We need to select participants, based on the quotas provided. For example: exactly 15 men exactly 15 women exactly 10 young exactly 10 middle aged exactly 10 old exactly 10 poor exactly 10 middle ...
45 views

### Algorithm for the complete parenthesization of n factors

Is there an algorithm that can list all possible parenthesizations of a given set of commutative factors? This is related to the Catalan number. It, however, merely determines the number of such ...
23 views

### Can you determinize an NFA in PSPACE?

QUESTION Given some NFA $A$, can you simulate the determinization of it (using Subset-Construction for example) while remaining in $PSPACE$? MORE DETAILS I'm asking this as I want to be able to ...
19 views

### On teaching Kolmogorov complexity with Python and the complexity of composed strings

The setting of this question is a bit long-winded, but please bear with me. This fall I will be lecturing a course on mathematical information theory, and on a few lectures we will be discussing ...
18 views

### Question about details for a proof for “if a coNP-hard problem is in NP (NP-hard problem is in coNP), then NP=coNP”

I searched the internet for a proof of the statement: If a $coNP$-hard problem is in $NP$, then $NP=coNP$ (NP-hard problem is in coNP). I found a proof sketch here (page 3 in the pdf, slide 341) and I ...
24 views

### What is the class of automata with stack and unlimited amount of memory, addressable only by immediates?

Let's assume we've got an automata with infinite stack ($s_n \epsilon \mathbb{Z}$) and infinite amount of "registers", but no arbitrary memory access whatsoever and it's data is separated from code. ...
18 views

### UNDIRECTED HAMCYCLE to HAMPATH reduction

I'll define the problems UHAMPATH Input: A undirected graph G and 2 nodes, s and t Question: Is there a hamiltonian path from s to t in G? UHAMCYCLE Input: A undirected graph G ...
394 views

### Halting problem in EXP-complete

I have some troubles understanding why the halting problem is in EXP. In Wikipedia the following is written: It is in EXPTIME because a trivial simulation requires O(k) time, and the input k is ...
16 views

### Why are CFL not closed under set difference, and complementation? [duplicate]

I was wondering why CFL are not closed under set difference, and complementation can anyone explain? I tried searching, but no luck.
32 views

### Proof of the average case of the Heap Sort algorithm

Consider the following python implementation of the Heap Sort algorithm: ...
14 views

### How to compute within a Multi tape turing machine [a binary substraction between 2 numbers and result on 3rd tape]? [closed]

I'm trying to compute a Multi-tape turing machine (of 3 tapes) that follows this statement. "A binary subtraction operation between the first and second tape printing the result on the third tape" I'...
10 views

### Recurrence Relation of Ternary search and the number of comparisons with binary search

i was reading the binary search and ternary search algorithms. But i had a doubt with recurrence relation of ternary search as somewhere it is T(n/3)+c and T(2*n/3)+c. I want to know which one is ...
23 views

13 views

### Efficiently calculate values based on subsets of a list

Let's say I have a list of items, each of which has some value Eg. L1 = [A, B, C, ...] And another list of items L2: [1, 2, 3, ...]. Each of the items in L2 needs to calculate the max value of a ...
7 views

### Calculating spatial “orderedness” at each position in a binary image: entropy? lacunarity?

Let's say I have image where all pixel values are either 0 or 1. What I'd like to do is to be able to generate a new image with the same dimensions where each pixel represents how "ordered" the area ...
22 views

### $L = \{ \langle M \rangle \mid M$ is a Turing machine and $\mathcal{L}(M)$ is decidable $\}$

$L = \langle M \rangle \mid M$ is a Turing machine and $\mathcal{L}(M)$ is decidable $\}$. How could I show this language is undecidable using the HALTing method? A language $L$ is undecidable if its ...
46 views

### Oracle Turing Machine ${EXP^{EXP}}$

does ${EXP^{EXP}=EXP?}$ here is my thought ${EXP}$ machine can ask $2^{O(n)}$ queries to the oracle, and each oracle would itself solve an exponential time problem in a single step. So the total ...
18 views

### computation of a hypergeometric sum [closed]

Let $q,\ell, M \in \mathbb{N}$ I am not familiar with mathematica, maple or mathlab to, at least see what this sum suppose to be. I am wondering if someone can compute this sum  \sum_{m=0}^q\binom{q-...
23 views

### A doubt on converting NOT gate to CNF formula

For a NOT gate if $x_1$ is input and $x_2$ is the corresponding output, I see the equivalent CNF (conjunctive normal form) is $(x_1 \lor x_2) \land (\overline x_1 \lor \overline x_2)$. My ...
20 views

### Disjoint Set Connected Components With Weighted Graph

I have been trying to solve this HackerRank problem (link). The basic premise of this problem is that there is a tree with undirected, but weighted, edges. The cost of a path in this tree is taken ...
27 views

### Connected but not adjacent vertex

Is there any specific terms or adjectives in graph theory to name this two situations? Two vertices are non-adjacent (disjoint? I have seen that the term "disjoint" is rather used for paths with non-...
29 views

### Data structure & algorithms for super-interval queries on intervals with small integer ends

I would like to have an online data structure that supports inserting an interval, and given a query interval $I_q=[l_q,h_q]$ answer if some interval of the data structure is contained in $I_q$, i.e. ...
18 views

### A deterministic finite state automata for finding all (potentially overlapping) regular expression matches?

I was working on a bioinformatics practice problem named Finding a Protein Motif on rosalind.info. In essence, I was given a particular regular expression ...
9 views

### How to use c-gap problems to prove inapproximability?

Suppose there is a specific set function with some properties - $f=2^V\to \mathcal{R}$. It is known that the following problem is NP-Hard: Find $S\subseteq V, |S|\leq k$ such that $f(S)$ is maximized....
16 views

### Find the asymptotic time complexity of the following [duplicate]

while(n>1){ n = sqrt(n); } Where sqrt returns the root of n. n = 2^k and k is a power of 2.
32 views

### Minimize cost of recursive pairwise sums: how to prove the greedy solution works?

The problem is in this other question. Why does this always work? It's not clear to me how one would use induction. For $n = 3$, a quick calculation shows it works, however, I don't think it ...
8 views

### Design of Evolutionary Algorithm

I was going through some study material and a practice question popped up asking the reader to design an evolutionary algorithm to solve the following task: "A candy bar consists of sugar, choclate, ...
17 views

### Which is harder, an NP-complete problem or the Raz-Tal oracle problem?

This is a (hopefully) sharper version of a question that I asked previously. Which of these algorithms is believed to have a longer asymptotic runtime? The optimal algorithm guaranteed to solve some ...
15 views

### Number of distinct BFS, DFS trees in a complete graph

What is the number of distinct BFS, DFS in a complete graph? My approach is like this--> For DFS take a node, we have (n-1) possible tree edges, next we have all possible (n-2) tree edges,..........
15 views

### How to initialize the first h in an RNN?

Take a Vanilla RNN represented by the function $h_t = f(h_{t-1}, x_t)$, how do you determine $h_0$? Edit: This answer over on the stats page has helped.
11 views

### Genome mutation probability

I am taking an extra course this semester and we were given a series of questions for exam preparation. But I was unable to attend the discussion session and so I have no access to the solutions. I ...
5 views

### Tournament Selection Probability

I am taking an extra course this semester and we were given a series of questions for exam preparation. But I was unable to attend the discussion session and so I have no access to the solutions. I ...
15 views

### How can we convert between a program using call/cc and a program using functions written in CPS?

The Scheme Programming Language says It turns out that any program that uses call/cc can be rewritten in CPS without call/cc, but a total rewrite of the program (sometimes including even system-...
9 views

### How to assign people to categories based on some voting rules?

Say in an election there are predefined categories users can be assigned to. Of the people who are assigned to a certain category, other users can vote for them. To compute the results, the following ...
15 views

### Lower bound for merging $m$ sorted arrays (decision tree leaves count - permutations)

I need some help understanding how to calculate the lower bound on the time complexity of merging $m$ sorted arrays of length $n$. The bound should be $nm \lg(m)$. I need to prove this using a ...
11 views

### Roulette Wheel Selection Probability

I am taking an extra course this semester and we were given a series of questions for exam preparation. But I was unable to attend the discussion session and so I have no access to the solutions. I ...
14 views

### Do relativized relations between complexity classes tell us anything about the nonrelativized relation?

The existence of relativized relations between complexity classes seems to often be treated as "circumstantial" evidence about the "true" or "real-world" (i.e. nonrelativized) relation between the ...
49 views

### Why values can not be replaced with their extensionally equal values in an intensional system?

Thomas Streicher states in Investigations into Intensional Type Theory(§Introduction p.5) that: Although in Intensional constructive set theory (Intensional Type Theory) one can do most of the ...
37 views

### Undecidable languages

I'm confused on the definition of undecidable languages. Definition: For an undecidable language, there is no Turing Machine which accepts the language and makes a decision for every input string w. ...
39 views

### What is an example of a Turing-recognizable infinite word, which is not Turing-decidable?

I am confused about Turing Machines that are able to decide languages that contain infinite words. Are languages with an infinite amount of only finite strings always decidable? How can a Turing ...
40 views

### if $L \in NP$ then its mapping reducible to HALT?

This is true because every language in $NP$ is decidable and therefore HALTS but how do I formally show this?
22 views

### Parallel deletion and traversal in a lock free linked list

I'm unsure about the safety of deletion in a linked list. I've seen the issue posed by a parallel insertion and deletion (resulting in the loss of the insertion) and proposed solutions to that problem....
25 views

### Global variables and frame stack [closed]

The below program will read a positive integer from keyboard and print the binary equivalent. This program is using only one variable. If global variables are not stored in frame stack, how this is ...
17 views

### Number of Times to Run an Evolutionary (Genetic) Algorithm

Evolutionary algorithms like genetic algorithms (GAs) are typically run multiple times and the outputted results are averaged across successive runs. However, in the case of long-runtime algorithms (...
36 views

### Min Fibonacci Heap - increase key

I have been trying to implementing heap data structures for use in my research work. As part of that, I am trying to implement increase-key operations for min-heaps....
### how to calculate $2^{5000}$ mod 10 without calculator in fast way?
How is it possible to calculate $2^{5000}$ mod 10 without using a calculator in a fast way? The result with calculator was 6.