# All Questions

42,773 questions
Filter by
Sorted by
Tagged with
1answer
54 views

### Is this FA really equivalent to the given regular expression?

From the picture, the automata can accept $(\text L|\text D)^*$ following say $\_\text L\text D$, but in the formula above $(\text L|\text D)^*$ can't follow the $\_\text L\text D$. So the Automata ...
1answer
25 views

### no-input Turing Machine which accepts in k or fewer steps

Can we prove by induction that $A_k$ is computable for every choice of $k \in \mathbb{N}$? $A_k$ is the set of descriptions of a no-input Turing Machine which accepts in $k$ or fewer steps.
1answer
26 views

### DFA for {w|w contains a substring of length at most 5 that has at least three 1's}

I have thought about this problem, but cannot come up with a convincing answer since I think this problem has too many states too consider. The accepting states can be length 5 substring and 3 1's, ...
0answers
12 views

0answers
19 views

### How many clock cycles uses to run my code?

Assume, I want to know the number of the cycles of cpu clock that uses to run a specific code written with a specific Programming language like python or others Can i do it? i mean, do you have any ...
1answer
47 views

### I want to determine if this language is non regular-any tips?

After working through some examples of proving the non-regularity of languages I encountered this language $$L = \{(ab)^{i}a^{j} | i \geq j, i,j \in \mathbb{N}\}$$ Where $a^{k}$ = a repeated k times....
1answer
28 views

### Is this set covering problem NP-Hard?

Consider this variant of set covering problem. Input: a collection of sets S = {s$_1$, s$_2$, ... s$_n$} and an universal set U, in which s$_k$ $\subseteq$ U. (1<=$k$<=n) The problem is, divide ...
2answers
5k views

### Difference between Sequential ,Direct and Random acess with their acess time

I'm stuck on a point while reading about these different accessing methods. As per author. Sequential access Memory is organized into units of data, called records.Access must be made in a ...
1answer
25 views

### Is there a simplistic way of describing the proof to the undecidability of David Hilbert's 10th problem?

I recently have been reading a bunch about David Hilbert's famous 10th problem, and trying to understand its proof. I am currently in the process of reading through an explanation of the proof, given ...
1answer
90 views

### Proof for time complexity of Insertion (k-proximate) Sort equals O(nk)

The following is the definition for Proximate Sorting given in my paper: An array of distinct integers is k-proximate if every integer of the array is at most k places away from its place in the array ...
1answer
19 views

### Reducing one problem to another

I know this is sort of a basic question, but I don't completely understand the following. Let $A$ and $B$ be two problems. If I take one instance $a$ of $A$ and one instance $b$ of $B$, and show the ...
1answer
60 views

### Is Max 3-SAT W[1]-hard?

Is Max 3-SAT a W[1] hard problem, parmeterized by some parmeterize? I can't find the relevant literature.
0answers
16 views

### Is this variant of Subset Product NP-hard?

Given a set $Y$ with whole number positive divisors of $N$, is there a combination of divisors that have a product equal to $N$? Does Subset Product remain NP-hard when whole number divisors are only ...
1answer
325 views

### Could H correctly decide that P never halts?

Could H be adapted to correctly decide that P never halts? ...
1answer
45 views

### Number of spanning arborescences with a specific root in a directed graph

I am wondering how to calculate the number of spanning arborescences in a directed graph when a root is specified. For example: where there are 5 spanning arborescences. Note that there is an edge ...
0answers
11 views

### How many code alphabets do we need in order for a Huffman Code and a Shannon-Fano Code to be the same for the same source symbols probability

For example, If we have a source with alphabet $\{x, y, z\}$ with probabilities $\{0.5, 0.3, 0.2\}$ , What is the smallest integer $\mathbf{D}$ such that the expected length of a D-ary Shannon-Fano ...
3answers
712 views

### How exactly is the process of showing a problem to be NP-Complete a proof by contradiction?

The steps involved in proving that a problem is NP-Complete are fairly straightforward to follow, it's the logic behind why the proof is valid that's really throwing me for a loop. Okay so an easy one:...
1answer
58 views

### Find nodes at k distance from given source node in an undirected cyclic graph if k<=1e9

I have encountered this problem many times. In an undirected graph, you need to get all the nodes/one node that is k distance away from the given source node (...
1answer
49 views

### List of algorithms that depend on sorting / ranking / argsorting

I am looking for a list of algorithms that depends on sorting / relative ranking / argsorting, not for a list of sorting algorithms. I want to study and illustrate the importance of fast sorting in ...
1answer
14 views

### Is integer multicommodity flow problem is NP-hard?

As Wikipedia states the time complexity of Integer Linear programming(ILP) is NP-hard, so this means integer multicommodity flow problem is also NP-hard?
2answers
55 views

### What factors of the integer dataset being sorted can I change, in order to compare two sorting algorithms?

I am comparing two comparison and binary data structure based sorting algorithms, the Tree Sort, and the Heap Sort. I am measuring the time taken for both algorithms to sort an increasing size of an ...
0answers
47 views

### Decision problem solution monte carlo

I have a rather straightforward question for this community (that I am not able to solve). Assume there is a probability of Tom having a bag of candy. If Tom has a bag, he says the truth 4/5 times and ...
0answers
21 views

### Cluster 3d points with constraints

I have some 3d point cloud I wish to cluster into some number of clusters. I have the probability of two points being in the same cluster given as some function of their relative locations, with the ...

15 30 50 per page