# All Questions

6 views

### Tallest Person Average Memory Updating?

We ran into a problem that mentioned in an Interview 2-days ago. How can help us with any idea or hint? n persons randomly enter to a room . we want to find ...
4 views

Let's say I have a decision problem, D and it's complement D'. I know D is poly-time reducible to D'(it's complement). Furthermore, I know D is Np-Complete. What is the most strongest statement I ...
12 views

### A logic function that is true iff the first operand is less than the second operand

In my computer organization class I have been given a series of problems. One I'm stuck on currently is below: Assume that $X$ consists of 4 bits, $x_3 x_2 x_1 x_0$, and $Y$ consists of 4 bits, ...
7 views

### Relationship between independant set and VertexCover

Directly from Wikipedia, A set is independent if and only if its complement is a vertex cover. Does this imply the independent set problem's complement is the vertex cover problem?
6 views

### Understanding terms related to 2 SAT algorithm

Recently I am learning about solution of 2-Satiability problem using SCC(Strongly Connected Component). There is a theorem related to this problem given below: Theorem 2: The formula F is true if and ...
4 views

### Poly-time reduction: D and D Comp

Looking at the IndependentSet problem and it's complement. I want to show that IS is poly-time reducible to it's complement, however I am struggling on coming up with the reduction function. I will ...
6 views

### Placing data on the bus for a synchronous read operation

This question is taken from Computer Organization and architecture, William Stalling: For a synchronous read operation (Figure 3.18), the memory module must place the data on the bus sufficiently ...
8 views

### Is this grammar LR(1)?

A bit confused about whether this grammar is ambiguous or not C' -> C C -> d C u C C -> d C C -> ε I tried building the DFA for this but I get this ...
9 views

### VC Dimension for open intervals

I'm having difficulty calculating VC dimensions for these scenarios, any help is appreciated. $H = [a,\infty)$,I think it's 1 since if the label is less than a it's not gonna shatter. One sided ...
7 views

### In which pipeline stage are exceptions detected?

Do you immediatly handle an exception when it occurs (for example an overflow exception in the EX stage) or do you wait until the final pipeline stage and then check whether any interrupts had ...
14 views

### Edges of minimum spanning trees.

Is as edge of a minimum spanning tree in a graph $G$ the shortest path between its incident vertices? I think this might be true due to the cut property of but I am unable to prove it.
17 views

33 views