# All Questions

31,820 questions
Filter by
Sorted by
Tagged with
1answer
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 ...
1answer
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 ...
0answers
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})$ ...
0answers
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 ...
1answer
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 ...
1answer
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 ...
0answers
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 ...
0answers
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 ...
0answers
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. ...
1answer
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 ...
1answer
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 ...
0answers
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.
0answers
32 views

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

Consider the following python implementation of the Heap Sort algorithm: ...
0answers
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'...
1answer
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 ...
1answer
23 views

### Need help understanding regular expressions

I was reading up about formal languages (see here: https://pdfs.semanticscholar.org/18b2/d685d5e244a6bfc5a31d312f1e8d322c16a9.pdf) and got confused when I started reading about this expression: 0(0+1)∗...
0answers
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 ...
0answers
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 ...
0answers
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 ...
1answer
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 ...
0answers
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-...
1answer
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 ...
0answers
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 ...
1answer
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-...
0answers
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. ...
0answers
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 ...
1answer
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....
0answers
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.
1answer
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 ...
0answers
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, ...
0answers
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 ...
0answers
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,..........
1answer
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.
0answers
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 ...
0answers
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 ...
0answers
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-...
0answers
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 ...
1answer
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 ...
0answers
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 ...
0answers
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 ...
2answers
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 ...
2answers
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. ...
1answer
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 ...
1answer
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?
0answers
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....
1answer
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 ...
0answers
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 (...
1answer
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....
2answers
64 views

### Constructing a directed graph for O(1) queries

This question appeared in an undergrad data structures final. The details are sound. I need help to design a data structure for a directed graph with the following properties: Initialization should ...
4answers
114 views

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

15 30 50 per page