All Questions

Filter by
Sorted by
Tagged with
0
votes
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 ...
0
votes
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.
0
votes
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, ...
0
votes
0answers
12 views

Making a simplest possible CFG to recognize the language L = {a^i b^j c^k | i + j ≥ 2k}

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 $...
1
vote
2answers
72 views

Comparison-based sorting on a list of size n must make n-1 comparisons (reference to proof)

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 ...
0
votes
1answer
40 views

How do i delete one single unequal element from an array of equal elements without using hashing?

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 ...
26
votes
5answers
15k views

Finding the minimum cut of an undirected graph

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 ...
1
vote
1answer
113 views

Meaning of $a\lor b \to b' \lor c'$

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 ...
6
votes
10answers
3k views

Real life examples of *zero* weight edges in graphs

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 ...
1
vote
2answers
30 views

3SAT: Get smallest number of algorithm invocations to get a satisfiable assignment? How should it be done?

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? ...
0
votes
0answers
8 views

Advices needed to study the deep learning book of ian goodfellow?

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 ...
0
votes
1answer
19 views

How can we prove that a reduction exists?

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 ...
1
vote
1answer
49 views

Find close pairs of real points in a set

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 ...
0
votes
0answers
23 views

Confused about Turing Recognizability

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 ...
0
votes
0answers
20 views

Can I use the term pseudo-logarithmic?

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 ...
1
vote
0answers
21 views

Uniformly random decimal numbers

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

Stuck on Converting to Chomsky Normal Form,

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 → ...
0
votes
2answers
168 views

Sorting algorithm which sorts half the possible inputs in linear time

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 ...
4
votes
1answer
64 views

Combinatorics - how many $c$-distinct sets are possible?

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 ...
0
votes
0answers
13 views

Organic Chemistry Dataset with Compound name and formula

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 ...
0
votes
0answers
27 views

Can this special case of Set Cover problem be solved in polynomial time?

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 ...
7
votes
0answers
141 views

Shortest path in directed graphs with no more than $\log \log n $ negative edges

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 ...
1
vote
0answers
9 views

Recurring computations for 2-counter machines

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 ...
-1
votes
1answer
39 views

Is the right quotient of a regular language respect to another regular language a regular language?

Will the language $\{w\in L_1\mid \exists v, wv\in L_2\}$ be regular if $L_1$ and $L_2$ regular languages?
0
votes
1answer
59 views

updating n elements in $O(\lg{n})$ time

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 ...
6
votes
1answer
158 views
+50

Fast and compact data structure for dynamic graphs

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]$...
2
votes
2answers
1k views

Efficient algorithm to find minimum steps to cover all the given points in infinite 2D grid?

Problem statement: You are in an infinite 2D grid where you can move in any of the 8 directions : ...
0
votes
1answer
13 views

DPDA by empty stack

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 ...
0
votes
1answer
850 views

Determine if an NFA accepts infinite language in polynomial time

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,...
1
vote
1answer
137 views

Algorithmic Problem on Trees

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 ...
1
vote
1answer
16 views

Runtime analysis with multiple parameters: case study with heaps in Huffman coding

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 $...
0
votes
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 ...
0
votes
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....
2
votes
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 ...
1
vote
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 ...
1
vote
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 ...
0
votes
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 ...
1
vote
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 ...
2
votes
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.
0
votes
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 ...
-4
votes
1answer
325 views

Could H correctly decide that P never halts?

Could H be adapted to correctly decide that P never halts? ...
0
votes
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 ...
0
votes
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 ...
1
vote
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:...
-2
votes
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 (...
2
votes
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 ...
0
votes
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?
1
vote
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 ...
1
vote
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 ...
1
vote
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
1
2 3 4 5
856