# All Questions

1answer
7 views

### How can a Turing machine run another machine for an infinite amount of strings?

The proof in my textbook, that $E_{TM}$ can be decided by oracle machine $O^{A_{TM}}$, uses a Turing machine $P$ such that for an input $w$: $P$ runs the Turing machine $M$ on all strings of ...
1answer
25 views

### Uncertainty whether $\{a^ib^jc^k\,|\,i+j\le k\}$ is context-free or not

I'm having trouble with this particular language $$\{a^ib^jc^k\,|\,i+j\le k\}$$ If it's not context-free I don't know how to correctly apply the Pumping Lemma for CFL; if it is context-free I don't ...
1answer
11 views

### Finding valid permutation using a graph

I need to solve the following problem: Let $A$ be a set of integers: $A=\left \{ x_1, x_2...x_n \mid 10<x_i<100\right \}$ a valid permutation $x_{i_1}x_{i_2}...x_{i_n}$ is a permutation that ...
0answers
12 views

### Time Complexity of transitive closure of a binary relation

What is the time complexity of computing the transitive closure of a binary relation on a set of n elements? A) O(n) B) O(n log n) C) O(n^(3/2)) D) O(n^3)
1answer
23 views

### Is Co-NP closed under taking subset?

I have a question on my homework causing some confusion. If L is a strict subset of L', and L' is a member of Co-NP, is L a member of Co-NP? True of False Now I understand what belonging to ...
1answer
19 views

### Hashing a Specific Range Of a Character Array

I need to process queries to Hash various ranges of a character array. I am currently using the Arrays.hashCode from the standard java library. But the problem is that this method is too slow. Also my ...
2answers
42 views

### Minimum spanning tree and its connected subgraph

This problem is from the book Algorithms, Chapter 5: Greedy algorithms. In case of being closed as a duplication to that in Minimum Spanning tree subgraph, I will first make a defense: The accepted ...
2answers
79 views

### What is a dichotomy? Whether 2-SAT itself is a dichotomy of SAT?

Recently, I am reading papers about dichotomy. I do not understant what condition can be called as a dichotomy? What is the meaning of "a question is either in P or in NP-complete"? (assume P $\neq$ ...
2answers
41 views

### Why does a regular expression only accept all my required strings when the concatenation is the first of the OR operations?

I am having a bit of difficulty understanding the order of precedence in boolean logic for the OR operation. Take this example: Assume the following regular expression: ...
3answers
49 views

### Worst run-time for 3 nested loop

Suppose we need to find a tight asymptotic bound on the worst case run time of the following program ...
0answers
21 views

### Upper or Lower bound for Maximum clique size in a Graph

In a hypothetical scenario for an arbitrary graph, if we let $n$ be the number of vertices, $m$ the number of edges, and $d$ be defined as the maximum degree of some graph G. Would the maximum clique ...
1answer
35 views

### NP-hardness given some reducible language

While reading a passage in an older textbook I came upon this problem which I am having difficulty in justifying whether its true or false. Is this possible? If some problem $A$ is NP-hard, and if ...
0answers
16 views

### How to convert a DFA to a Turing machine? [duplicate]

Having the diagram of a DFA, how can I convert it to a Turing Machine? Do I have to find the language that the DFA accepts and then create the Turing Machine? Or is there a direct way? Thank you.
2answers
43 views

### Prove Point separation problem is NP Complete

I am preparing for algorithm final term. While preparing, I came across this question and I am not sure how to solve this. I am trying to reduce Travel Salesman Problem(TSP) to this but I am getting ...
0answers
32 views

### k-shortest paths

Given a weighted digraph $G=V,E$, and a weight function, $d(u,v)$, one can normally use Dijkstra's algorithm to obtain the shortest path. What I am interested in, is how to obtain the ...
1answer
11 views

### If dynamically typed languages are truly statically typed, unityped languages, what is the (finite) type expression of the one type?

Some claim that dynamically typed languages are in reality statically typed, unityped languages. This would imply to me that this one type should be expressible as a static, finite type expression, so ...
2answers
220 views

### Kolmogorov Complexity: Why would you need more bytes than the string itself?

I was reading Wikipedia's entry on Kolmogorov Complexity (thanks to this question), which states: It can be shown that the Kolmogorov complexity of any string cannot be more than a few bytes ...
0answers
15 views

### Turing machine for the language {0^m 1^n 0^m, m>=0, n<=m}

Is the following machine a possible machine for the language {0^m 1^n 0^m, m>=0, n<=m}? Thank you.
1answer
20 views

### Turing Machine which Diverges on its Own Code

Show that the set $K^{c}$ = $\lbrace M \text{ }| \text{ }M(M) \text{ }diverges \rbrace$ is not recursively enumerable. This question is essentially asking to show that the set of turing machines ...
1answer
26 views

### Binary operators with higher precedence than unary operators

Generally (perhaps always) in programming languages, unary operators have the highest precedence. In some langauges, such as Standard ML, one can dynamically change the precedence of binary operators ...
2answers
154 views

### Parallelising random reads seems to work well — why?

Consider the following very simple computer program: for i = 1 to n: y[i] = x[p[i]] Here $x$ and $y$ are $n$-element arrays of bytes, and $p$ is an ...
1answer
23 views

### Relative complement of a Non CFL to CFL

Let $L$ be a given Context Free Language over the alphabet $\{a,b\}$. Now consider $$L_1=L-\{xyx\ |\ x,y\in\{a,b\}^*\}$$ I know that $\{xyx\ |\ x,y\in\{a,b\}^*\}$ is not Context Free (by using pumping ...
1answer
42 views

### Turing machine commands

I been reading a bit about Turing's machine and I do not understand what are the commands limitation? What consider to be legal and what consider to be illegal command? What are states?
0answers
35 views

### Redundant States During Removal of Null-Moves (Regular Expression to DFA)

I've had this little doubt bothering me since four semesters now, so I've come here to resolve it. Theoretical CS was probably not the right place to ask. Coming to the question, my old coursebook ...
0answers
7 views

### Getting Forwarding Table for Bridges connecting a number of LANs [on hold]

I have the following question showing some bridges connecting a number of LANs alongwith a few questions asked thereafter : Can someone please help me out ? Thanks.
0answers
10 views

### “Grammar inference” for 2-D images

Others have studied the following question: given a set of words $w_1,w_2,\dots \in \Sigma^*$, find a regular grammar (or a context-free grammar) that generates all of those words, is "natural" in ...
0answers
12 views

### Interpreting a digital logic diagram [on hold]

I have the following image for a logic diagram : I wanted to know the meaning or how to interprete the inputs to get the expression for the output f ?? Can someone please help me out ? Thanks and ...
0answers
105 views

### Question on SAT reduction

Let Two-Solutions-SAT be the language of Boolean formulas that have exactly two distinct satisfying assignments. Show Two-Solutions-SAT is co-NP-hard. I know how to show that the complement of ...
2answers
94 views

### Are there problems with complexity between $O(n^c/\log^b n)$ and $O(n^{c - \varepsilon})$?

I am having an extremely tough time with this homework question, wondering if anyone could help me (for all you theory aficionados, this one's for you). There is a language $L$ with the following ...
0answers
37 views

### Big O confusion [duplicate]

I have a question asking about a language L with the property: there is a TM that decides L in time O(n^2013 / (log(n))^2012), and if there is a TM that decides L in time O(n^2012.9). My confusion ...
3answers
55 views

### About the complexity of deciding whether no two elements of a collection are the same

Given a collection of $n$ numbers, $S$, the question is to decide whether all the elements of $S$ are distinct from each other. If they are distinct from each other (no two of them are the same), ...
0answers
22 views

### all pairs shortest problem interview task

I am solving algorithm interview questions and came across this. Question: You work for a construction industry. Your boss would like to open a new office in some city. You have to help your boss to ...
0answers
25 views

### Demonstrate that DPDA is closed under complement by construction

I've been trying for quite some extended time to find a construction so that I can formally demonstrate that a deterministic PDA is closed under complementation. However, it happens that every idea I ...
1answer
36 views

### Find subset with minimal sum under constraints

Let $M$ be a finite set of even cardinality. Define $C=\{\{a,b\}:a,b \in M, a \neq b\}$ the set of all pairs over $M$. Let $w:C \rightarrow \mathbb{R}^+_0$ be a function. Now find $C' \subset C$ with ...
0answers
18 views

### How can i find a language of a grammer

hi there i have a following grammar and want to find the language of this problem what is the regular way? S-->SSc|SSd|a the result of my research is but this ...
2answers
36 views

### Minimum spanning tree vs Shortest path

What is the difference between minimum spanning tree algorithm and a shortest path algorithm? In my data structures class we covered two minimum spanning tree algorithms (Prim's and Kruskal's) and ...
2answers
32 views

### Why are bytes treated like the base unit?

If bits are the base unit of information, why are bytes treated like the base unit? For example, usually values are expressed in Mega/Giga/Tera/Exa bytes instead of bits. I am aware that bits are ...
1answer
15 views

### Big O Notation - Find a Function That Represents the Statement

There's an f(n) such that f(n) != O(f(n/2)) so by the definition of big O notation: for ...
1answer
36 views

### CNF SAT conversions

I am interested in reductions from 3-CNF boolean expressions to similar restricted forms. For example, I am interested in knowing how to reduce a 3-CNF formula to another 3-CNF formula where each ...
0answers
22 views

### Modified Pumping Lemma

How could we prove the following modified Pumping Lemma:Let the language L has an infinite number of words, then there are words $x,y,z \epsilon \Sigma ^{*}$, so that $|xz|\leq |\Sigma_{k}|$, and each ...
0answers
11 views

### Calculating average turn around times Round Robin

I understand RR works but I dont know how to calculate the average turn around times In a system using Round Robin scheduling, three processes, each with a burst time of 6 units, arrive at the same ...
2answers
84 views

### Metagame Paradox: what is wrong with this explanation?

Today I've heard about fascinating metagame paradox. I tried to come up with an explanation via Turing Machines formalization (below). Do you know what is the solution to the paradox? (the post ...
0answers
16 views

### Why generally to find a Euler cycle is easier than Hamilton cycle for the same set of nodes? [duplicate]

To find a Hamilton cycle is a NPC problem, but Euler is not. Considering one can always transform the vertex as edge or vice versa conceptually. Then the vertex can be used to describe the information ...
1answer
43 views

1answer
45 views

### Can we decide the language of a turing machine is in a regular language?

Consider for any given DFA D and Turing machine M, can we decide wether L(M) is in L(D)?

15 30 50 per page