All Questions

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

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.

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

The language given is $L = \{a^i b^j c^k\mid i+j \ge 2k\}$ for which I need to construct a simplest possible Context Free Grammar. I tried understanding but I could only go as far as making sense of $...

I am looking for a reference to a proof that comparison-based sorting cannot make less than n-1 comparisons on every list of size $n$. Do you have a reference of a book that covers it (with page ...

The rules of the question state that: Only one element is different. Rest are all same. Array A size is 8. I need to find the different element and remove it (Hashing cannot be used). I have not ...

Here's a question from a past exam I'm trying to solve: For an undirected graph $G$ with positive weights $w(e) \geq 0$, I'm trying to find the minimum cut. I don't know other ways of doing that ...

So I have done part a) but I have no clue what I am supposed to do for part b), I have been trying for days to wrap my head around and even asked my fellow course mates, none of which seem to know ...

The meaning of edges with zero weight in a weighted graph questions me for a long time, and I even asked a related question previously. Yet, when I recently read here a question on real life example ...

My Question is, what is meant with smallest number N. Does it mean I should try every possible constellation of the n variables and put each one of them into the formula φ and then use 3Sat on that? ...

After studying the basics of machine learning, I want to follow the deep learning book of Ian Goodfellow. To have a better understanding of the book and make clearer the points that I could not get ...

PROBLEM: I have two computational problems, A and B. We know that A $\in$ Psearch and I want to prove that A$\leq_p$B for all problems B. GOAL: It is my understanding that my goal is to prove that ...

Given an array $S$ with $n$ real numbers. Design a linear time algorithm that finds $x,y \in S$ such that that $|x-y| \leq \frac{max(S)-min(S)}{n-1}$. I was thinking that it is similar to the closest ...

If Turing Recognizability means a T.M. will either halt on input w if w is in the language, or run forever if w is not in the language. How can we know the language is Turing Recognizable if we run ...

Whenever an algorithm has polynomial complexity, but exponential over the encoding of the input, it is said to be pseudo-polynomial. What about logarithmic complexity? Can I state that these ...

Due to finite precision of number representations, we face situations like: In: 0.1+0.1+0.1==0.3 Out: False (on my ...

I am supposed to be changing this to Chomsky Normal Form and then to Greibach form, but I am still having a few difficulties changing it to the first form. Here is the language: S → AA|SBBa|b A → ...

Prove that there isn't any comparison sort algorithm which for an input of size $n$ can sort at least half of the permutations of the input in linear time. (For the other half the algorithm can ...

I'm not sure if CS SE is the right place for this question, but since originally this question was in the CS area (and I translated it to a mathematical form), I will post it here. I am given two ...

I am trying to create an app which needs access to a dataset with organuc chemistry compound names and formulas. The ones I have found don't satisfy the requirement. Does anyone else know of any ...

Let $U$ be the set of elements and $S$ be the subset collections. There exists a tree $T$ that each node is corresponding to an element in $U$. And for every subset $s$ in $S$, $V(T) \bigcap s $ is a ...

Given a directed graph $G=(V,E)$ with $|V|=n$ vertices and some weight function $w\colon E\to \mathbb{R}$, I also know that there are at most $\log\log n$ negative weight edges in $G$, and $G$ does ...

It is known that reachability of 2-counter machines is undecidable. As far as I know, it is semi-decidable though. Now let's focus instead on the problem of deciding if a 2-counter machine has a ...

Will the language $\{w\in L_1\mid \exists v, wv\in L_2\}$ be regular if $L_1$ and $L_2$ regular languages?

I need to devise a data structure $S$ with the following functions: BUILD($S$) - build the data structure from a series of $n$ elements in time $O(n \lg{n})$ INSERT($S$, $k$) - insert a new element ...

A graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ may be represented in central memory as follows: an associative array (hash table) $V$ gives for any $v\in \mathcal{V}$ the list of its neighbors $V[v]$...

Problem statement: You are in an infinite 2D grid where you can move in any of the 8 directions : ...

Let's say we have DPDA with acceptance by empty stack, w is accepted by this DPDA. Why can't wv be accepted? I know about the prefix property but i don't see where it's coming from. Can't we just ...

Question Statement: Given a NFA $N$, design an algorithm that runs in polynomial time such that it determines if $L(N)$ is infinite. (Note that converting NFA to DFA is exponential time). For any DFA,...

Given a directed, rooted tree with $n$ vertices, the height of a vertex $v$, $h[v]$ is the number of edges on the longest path from $v$ to some reachable leaf node. Give an efficient algorithm to find ...

While studying a book on algorithms, I came across a question that asked about essentially $d$-ary Huffman coding, where the codeword alphabet has $d$ symbols (the usual case has $d=2$, with symbols $...

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

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

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

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

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

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

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

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

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

Could H be adapted to correctly decide that P never halts? ...

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

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

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

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

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

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?

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

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

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