All Questions

Filter by
Sorted by
Tagged with
0
votes
0answers
5 views

Is logical address generated by CPU and MMU same if Physical and Virtual address space are same?

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

Predictive parsers in compiler construction

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

Overflow when adding multiple binary numbers

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

Efficient algorithm to filter off points from a point cloud

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

What is the name of the program that opens the documentation?

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

What is the most used mapping technique in cache memory?

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

Fastest algorithm to find whether a list contains a word?

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

Automata with minimal number of states using reverse

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

Who invented the adder, full-adder, half-adder?

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?
0
votes
1answer
15 views

Runtime-Analysis for single loop incremented by a factor of 3

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

Types and Programming Languages - proof for theorem about principles of induction of terms

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

Non-Boolean SAT

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

O(n) algorithm for the connected components at most n/2 problem

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

Why haven't I solved the Travelling Salesman problem with the following argument using djikstras algorithm?

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

Is inverse CNF polynomial?

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$?
1
vote
1answer
17 views

I came up with a way to modify Dijkstra's Algorithm to handle graphs with negative edge weighs [duplicate]

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

Is AWS EC2 instance considered a cluster?

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

Two definitions of oracle

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

Grassfire vs BFS

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

Coefficients in cost function in A-star

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

What does valid method overriding mean?

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

Complexity classes for various models of computation

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

Lexical and Syntactic Error confusion in C [on hold]

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

Examples of Regular, Context-free and Context-sensitive languages

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}^* | \,...
0
votes
0answers
18 views

Extrapolation algorithm for predicting the next random number [on hold]

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

Can Dijkstra's algorithm outperform A star, in terms of vertices checked?

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

Algorithm to find longest path in a tree that is smaller than x

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

Algorithm Design: Efficient O(n) algorithm to get the ith to jth largest elements in an array

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

GOING BACK IN TIME [on hold]

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

Lack of Stack Pointer Register

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

Algorithm for competing cells of 0s and 1s. Can it be made faster? [on hold]

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

Max sum of k contiguous subarrays

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

Algorithm for searching string with wildcards

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

Does the master theorem applies to this recurrence?

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

How can I calculate the maximum sum/product of sequence?

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

Language with one word not in P

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

Computing similarity of two graphs with partially overlapping sets of nodes

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

Why is it not possible to prove that two Turing Machines calculate the same function?

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?
0
votes
2answers
28 views

prove that {$↔,⊕$} is incomplete set?

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

DBMS: MINIMUM NUMBER OF TABLES REQUIRED TO REALIZE THIS ER MODEL

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

Integer-array indexing (e.g. numpy.take) as function composition: where can I find more resources?

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

what is the time complexity and primitive operation of following triple while loop [duplicate]

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

Why is it not possible to prove the equivalence of nondeterministic and deterministic Turing Machines the same way as for NFAs and DFAs?

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

Which is a type of objects in mainstream OO languages: a class, an interface, an abstract class, a metaclass?

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

Is there a universal Turing machine for non-deterministic Turing machines?

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

How can $A \cup B$ be decidable if $B$ is undecidable?

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\}^*$ ...
1
vote
3answers
52 views

How can any non-primitive-recursive function like the Ackermann function be implemented on hardware?

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?
-1
votes
0answers
15 views

Turing Machines,Robots and Artificial General Intelligence [on hold]

Are Turing machines the only process and/or method to creating true artificial intelligence?
0
votes
0answers
11 views

boolean algebra (proof with identities) X=X.Y+X.Y' [on hold]

Having trouble figuring out which boolean identities will be useful in proving x = xy + xy'.
0
votes
0answers
13 views

Traverse tree collecting nodes combinations

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

15 30 50 per page