All Questions

Filter by
Sorted by
Tagged with
0
votes
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 ...
2
votes
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 ...
1
vote
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})$ ...
1
vote
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 ...
1
vote
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 ...
0
votes
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 ...
2
votes
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 ...
0
votes
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 ...
0
votes
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. ...
1
vote
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 ...
2
votes
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 ...
0
votes
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.
0
votes
0answers
32 views

Proof of the average case of the Heap Sort algorithm

Consider the following python implementation of the Heap Sort algorithm: ...
0
votes
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'...
-1
votes
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 ...
0
votes
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)∗...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
-2
votes
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-...
0
votes
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 ...
0
votes
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 ...
1
vote
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-...
2
votes
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. ...
0
votes
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 ...
1
vote
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....
0
votes
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.
1
vote
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 ...
0
votes
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, ...
1
vote
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 ...
0
votes
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,..........
0
votes
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.
0
votes
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 ...
0
votes
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 ...
2
votes
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-...
0
votes
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 ...
1
vote
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 ...
0
votes
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 ...
1
vote
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 ...
4
votes
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 ...
2
votes
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. ...
1
vote
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 ...
1
vote
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?
1
vote
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....
1
vote
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 ...
0
votes
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 (...
4
votes
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....
0
votes
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 ...
2
votes
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