All Questions

The system has same physical and virtual address space i.e. 32-bit. Are the logical address generated by CPU and address generated by MMU same?

if a predictive parser does not use backtracking how does it make use of grammars with more than one production. eg. A -> aB | bC

Perform the following binary operation assuming our resultant has a maximum of 8 bits: 00110110 + 01111001 - 00001100 Was there an overflow, a signed overflow, or no overflow? (a signed overflow ...

I have a master point cloud, which essentially just a list of points with {x,y} coordinates. The point cloud is HUGE ( like, it can contain more than 1 million ...

What is the name of the program that displays the documentation within the current software? For example: Each software that the documentation file is in HTML is showed in a small windows within the ...

I'm learning about mapping techniques in cache memory at university, associative mapping, direct mapping and set associative mapping. Which one is the most used nowadays? My guess is associative and ...

Given an unordered list of words, what's quickest way to test whether a certain word is in that list? I can't think of another way to do this other than just going through each element in the list ...

So, by the Bzozowski theorem, if A is DFA det(rev(det(rev(A))) would have minimal number of states. And for the most of them work. But for this example, I can't figure out why it doesn't. I have an ...

I didn't find, in the digital design books, who invented the adders. The same person invented the half-adder and the full-adder? What's the oldest publication on digital arithmetic design?

So, I'm trying to understand how to get the run time of this loop: for(int i = 1; i < n*n*n; i*=3) {...} So, far I know: loop starts at 1 finishes when $i &...

Types and Programming Languages book introduces a theorem about principles of induction on term (p. 31, theorem 3.3.4): Suppose P is a predicate on terms. Induction on depth: If, for each ...

I was wondering about the complexity of SAT tests with variables $x_i = 0 \lor 1 \lor 2 \dots \lor n$, with clauses being of the form $x_i = a \implies x_j \neq b$. When $n=2$, we have 2SAT, which has ...

I'm given a problem statement which states "There always exists a vertex from a tree G such that the remaining connected components have size at most |V(G)|/2". I'm trying to formulate an efficient ...

I claim to have solved the travelling salesman problem as follows. (You will have to be familiar with djikstra's algorithm for this.) 1) I am about to start using djikstra's algorithm on any given ...

Suppose we are given a CNF formula $F$ with $n$ variables and $m$ clauses. The question is whether we can represent $\lnot F$ as a CNF formula with the number of clauses polynomial in $n$ and $m$?

Add a constant $c\geq |w_{min}|$ to each edge of $G$, so that each edge now has non-negative weight. Run Dijkstra's algorithm Can anyone tell me if this is viable or if it fails?

Are individual Amazon Web Service EC2 instances considered a cluster or would a cluster have to be composed of multiple EC2 instances in order to be considered a cluster?

There are two definitions of oracle a) Oracle is a black box that "knows" (in an instant) the answer to a given decision problem, such as is this number (presented e.g. as a binary string) a prime ...

Expanding on this question : Why is Dijkstra's Algorithm more popular compared to Grassfire algorithm? What are the differences between grassfire and BFS? I'm surprised grassfire (supposedly) ...

I'd like to expand on this question : https://stackoverflow.com/questions/52420788/why-does-the-a-star-algorithm-need-gn Dijkstra's algorithm uses cost function $f(n) = g(n)$ whereas A* uses cost ...

In Types and Programming Languages by Pierce, from p257 to p258, about featherweight Java, The predicate override(m, D, C→C0) judges whether a method ...

The various complexity classes usually taught and studied ($P$, $NP$ $co-NP$, EXP, NSPACE etc) are usually defined using Turing Machines as the preferred model of computation. Are these sets of ...

Identify the compiler’s response about this line while creating the object-module: int main(){ fun(i=0,i<n,i++); } (A) No compilation error (B) Only a ...

Assume the languages: $$ a) \, L_1 = \{ w \in \{b,c \}^* | \, w \, \text{contains 'bbc' as substring} \} $$ $$ b)\, L_2 = \{ 1^k 0^m 1^m | k,m \in \mathbb{N} \} $$ $$ c)\,L_3 = \{ w \in {0,1}^* | \,...

Given a sequence of 100 pseudo-random numbers (generated using LCG, middle square Weil or another similar method) is it possible to predict the next number in the sequence (or at least the closest ...

I know Dijkstra's algorithm can be seen as a specific case of A star, when the estimation heuristic used simply returns 0, so I know that A star with this specific heuristic can not check more ...

Suppose we have a weighted binary tree $G$ where the nodes are towns and edges are streets with edge weights being the travel time and we want to find out whether it is possible to travel from any ...

I am trying to design an efficient algorithm that retrieves the ith to jth largest elements in an array. For example, if the following array is the input: ...

I have been asked this question in some interview. We need to build to go back in time. Implement a ticking clock which goes back in time, decremented by units specified (in hours). Application ...

Suppose a processor lacks STACK Pointer Register. But, It does have STACK. Then, in my opinion, a program will still be able to call subroutines but, will be unable to return back from the subroutines....

I'm working on a practice algorithm problem, stated as follows: There are eight houses represented as cells. Each day, the houses compete with adjacent ones. 1 represents an "active" house and 0 ...

The question is: given an array of size $n$ and a number $m$, now our goal is to find AT MOST $m$ contiguous subarrays such that the sum of all these subarrays is the largest. It is also required that ...

I'm trying to find efficient algorithm for checking if string with wildcards contains given substring. The parts of the string are separated with a "." character. So for example I have ...

The recurrence: $T(n) = pT(n/q) + \log n$ for p < q and p >= 2. So, I've figured out it would fall into case 1, since we have $n^{log_{q}p} = n^r $, for $0<r<1$, which would mean that $f(...

I am looking for an algorithm in $O(N^2)$ that finds the maximum value that be obtained from a sequence of real numbers greater than 0 (e.g. $\{ 1, 2, 3 , 4\}$) by inserting a plus ($+$) or ...

Are there any decision problems over [0,1]* with only one instance that are not in P? aka any languages over binary strings that only contain one string that are not decidable by a deterministic ...

Consider two graphs $G_1 = (E_1, V_1) $ and $G_2 = (E_2, V_2)$ with their associated sets of edges $E$ and nodes $V$. I'm familiar with concepts such as edit distance for computing the similarity/...

I was wondering why it is not possible. Is it because the corresponding language is not decidable, or because of the fact that it is not guaranteed that a Turing machine halts on every input?

How do i prove that Is {$↔,⊕$} not a complete set ? I have no clue how to prove it .

I was following a discussion on a forum where they have posted a question like this--> Some people are saying that we can merge A,B,C in a single table and m:n relation of A and C in another table ...

For context, one of Numpy's features is that an an array of integers can be passed as an index to an array, and this selects values at all of the specified positions, in any order with possible ...

public static int q3(int[] c) { int k=0,n=c.length; ...

I found en excercise asking this question. I know that for proving the equivalence of NFAs and DFAs we can use the conversion through subsets, and that for proving the equivalence of nondeterministic ...

In Types and Programming Languages by Pierce, Section 18.6 Simple Classes in Chapter 18 Imperative Objects says: We should emphasize that these classes are values, not types. Also we can, if we ...

I'm studying Formal Languages and Automata Theory and I found this question. I'm not sure of knowing the answer, so I'm asking for your help. I know that a universal Turing machine can emulate any ...

My assignment says: "Determine if the following statement is correct: If $A$ and $A \cup B$ are decidable, then $B$ is decidable." The solution says: "Incorrect. If $B = H_0 \subseteq \{0,1\}^*$ ...

If for-loops and function calls both boil down to jump instructions when implemented on a real machine, then how is "The Ackermann function isn't implementable with for-loops" a meaningful phrase?

Are Turing machines the only process and/or method to creating true artificial intelligence?

Having trouble figuring out which boolean identities will be useful in proving x = xy + xy'.

Summary: I have a tree, containing car parts, from which I need to build all valid combinations of these parts. Parts can be required - every build must contain them. Parts can be optional. Parts ...