# All Questions

28,864 questions
5 views

### NP-hardness does not imply lower bound, strictly speaking?

A problem is NP-hard iff every NP problem can be polynomially-time reduced to it. Hardness is often intuitively explained as a lower bound. But it isn't, strictly ...
3 views

### Banker's algorithm - additional allocation

I have a problem with the banker's algorithm. There are 6 processes and one type of resources. The allocation is (0, 29, 35, 10, 25, 35) and the MAX need is ...
26 views

In MIPS processor, address bus is of 32 bits. So on addressing an instruction, a whole 32 bit instruction is fetched. How is it byte addressable then? I mean if on addressing a particular address, the ...
3 views

### Understanding Hough transform examples in python

I have been reading up about the Hough transform recently, but I want to implement the algorithm (or a follow an existing algorithm such that I understand it) in python. I can't find many resources to ...
13 views

### Superposition calculus: Elimination of redundant atoms

Bachmair and Ganzinger (1991), 'Rewrite-Based Equational Theorem Proving With Selection and Simplification', section 5.2, 'Simplification and Deletion Techniques', page 17, 'Elimination of redundant ...
12 views

### How to generate a grammer from this language? [duplicate]

I'm trying to generate a grammar from this language: L={a^i b^j c^k d^l : i+j=k+l} to be clear its a in the power of i and b in the power of j... and so on, so ...
120 views

### Why Church-encoded types aren't sufficient to express inductive proofs?

I've heard some claims that the calculus of constructions without inductive types isn't powerful enough to express proofs by induction. Is that correct? If so, why isn't the Church-encoding sufficient ...
41 views

### Reducing subset sum to even subset sum

I'm trying to learn reduction. I have this problem called "even subset sum" that's very similar to subset sum. It's the same problem as as subset sum except that the only numbers allowed are even ...
17 views

### Expectation for the number of leaf nodes in a randomized tree construction

Consider this procedure for building a tree from $v_1, v_2, ..., v_n$: insert $v_1$ insert $v_2$ and connect it to $v_1$ via a directional edge from $v_2$ to $v_1$ insert $v_3$ and with a uniform ...
5 views

### How to understand out of bound in the following theoretical context?

Consider the following initialization step of loop invariant for merge procedure Initialization: Prior to the first iteration of the loop, we have $k=p$, so that the subarray $A[p .. k - 1]$ is ...
11 views

### T&PL: Language grammar with terms

I'm autodidacting Pierce's Types and Programming Languages. On page 27 he states a definition for "terms, concretely" in constructing a language of terms, thus: For each natural number $i$, define a ...
10 views

### Proof of heuristic function in A star algorithm

Maybe I am missing something very easy and obvious. But, I don't understand why estimate cost of source vertex is subtracted from the overall estimate cost, if heuristic function $h$ is monotonic: ...
8 views

### Is there any relationship between grammar being ambiguous and the language itself?

According to my understanding, a grammar is ambiguous if it generate strings which can be interpreted in more than one ways ( that is , more than one parse tree), but when it comes to the language ...
83 views

### What is the point of traversing a binary tree in preoder, inorder or postorder?

Why would you want to traverse a binary tree in preoder, inorder or postorder? Why not use an order like breadth-first search for all graphs?
20 views

### How to draw a parsing tree according to syntax diagram?

I would really appreciate if someone can explain the syntax diagram itself and can help to build the parsing tree.
9 views

### Stop and Wait Efficiency

A sender uses Stop and Wait protocol for transmission of 8000K bits size frames on a 1Gbps satellite channel with a propagation delay of $400ms$.What will be the link utilization(in percent),if ...
14 views

### What Are the Ideas Behind Variations of the Coin Change Problem?

Problem: given a set of n coins of unique face values, and a value change, find number of ways of making change for ...
69 views

### Does undecidability violate Turing completeness? Shouldn't “complete” include “decidability”?

Does undecidability violate Turing completeness? Shouldn't "complete" include "decidability"? That is, if one has a language that's Turing complete, but expresses infinite computation (i.e. may not ...
21 views

### Is it possible that $L=NP$?

According to Wikipedia and other sources, the question whether $L=P$ is an open problem, and of course everyone is familiar with the problem of whether $P=NP$. However, I found absolutely no ...
41 views

### Update each element to product of all others in linear time, constant additional space, no division

Question: I am trying to solve question 6.10.1 from Elements of Programming Interviews. There is no solution for this question in the book. I have only been able to ...
28 views

1k views

### How can you find all unbalanced parens in a string in linear time with constant memory?

I was given the following problem during an interview: Gives a string which contains some mixture of parens (not brackets or braces-- only parens) with other alphanumeric characters, identify all ...
22 views

### Complexity of generating non-uniform random variates

What can we say about the complexity of generating (negative) binomial and (negative) hypergeometric random variates? In particular, it is possible to generate (negative) binomial and (negative) ...
51 views

### Induction to prove equivalence of a recursive and iterative algorithm for Towers of Hanoi

Using induction how do you prove that two algorithm implementations, one recursive and the other iterative, of the Towers of Hanoi perform identical move operations? The implementations are as follows....
24 views

### Which is the best scheme for memory management

For each of the four processes P1, P2, P3, and P4. The total size in kilobytes (KB) and the number of segments are given below. ...
13 views

### Set List Queue Deque Map these are Collection frameworks of Java but can anyone differentiate the unique features among each of them [on hold]

We are know Set List Deque Map Queue are all a part of java collection framework but can anyone please tell me how are the unique in terms of Memory management Fetching Data When is the particular ...