# All Questions

8 views

### Is it possible to calculate the propagation delay if only the length of the link is known & not the speed at which a bit travels into the link?

Consider a $10^7$ bps link that is $400$ km long, with a queue large enough to hold $2000$ packets.Assume that the packets arrive at the queue with an average rate of $4000$ packets per second ...
11 views

### How can we add back edges in Ford - Fulkerson algorithm?

I was going through the Ford-Fulkerson(FF) algorithm. The given graph is directed and there is an edge from A to B with capacity y. Now sending a flow of x units (x < y) from A to B is equivalent ...
19 views

### Branchless function equivalent

Does every pure function have a branchless equivalent? By pure function I understand a function that uses only its input values and no global state to produce the output. By branchless function I ...
18 views

### B epsilon tree and Fractal trees

My question is simple, while reading up on B-trees, I stumbled across B epsilon trees and Fractal trees. Google gives me results for Fractal trees when i search for b epsilon trees and vice and versa. ...
12 views

### Does dijkstra works when I multiply weights of successive nodes

Consider a complete bidirectional weighted graph. Weight of each edge (a,b) is the probability of getting from a to b. So all weights are in range (0,1]. Probability of going from ...
19 views

### Proving “QUESTION” is NP-Complete by reduction from n-variable 3SAT

I'm struggling with a problem in my theory of computation course that asks us to prove "QUESTION" is NP-complete by reduction from n-variable 3SAT. I've done a number of other similar reductions but I ...
14 views

### What software development method would be appropriate for a homomorphic encryption research project?

Right now, I am playing with homomorphic encryption https://en.wikipedia.org/wiki/Homomorphic_encryption, namely I want to make a software that sorts a vector of encrypted integers and returns the ...
22 views

### On Ladner's theorem

In Ladner's theorem, can we take $\mathsf{NPI}$ problems to be problems in $\mathsf{SUBEXP}\cap\mathsf{NP}$? Is this a proper subset? Can we extend Ladner's theorem to interpret ...
26 views

### Understanding the proof of the halting problem

I came across the following example that proves that the blank tape halting problem is not decidable. I understand the proof technique, but I just don't see how the blank tape problem is shown to ...
19 views

### Construct matching for half of the vertices, in linear time

Suppose we have a graph $G=(V,E)$ connected and $K_{1,3}$-free. Sumner proved that every claw-free connected graph with an even number of vertices has a perfect matching (so, it is maximum matching). ...
17 views

### How to fix pipeline data hazards in following MIPS instructions?

MIPS instructions: add s2, s4, s1 sub t0, s2, s5 lw t1, 4(t0) add s3, s4, s1 A. Identify and explain any examples of pipeline hazards that you can find in ...
5 views

### How to calclate Avd() value to test the traceability attack

In this paper what is the value of Avd(ID0, ID1) that's mean this protocol is susceptible to traceability Attack? And how to caclate it?
29 views

### Patriot Missile Software Bug (Range Gate Calculation)

Okay so I was reading about the Patriot Missile Software Bug, where to calculate the predicted range gate the missile system relied on the time keeping, however it would convert the whole/integer time ...
27 views

### Another version of the online set cover problem?

Here is a note about online set cover problem: we are initially given the $m$ sets, but we do not know which elements they contain. At any time $t$, we get a new element $e_t$ and learn which sets ...
39 views

### When do deadlocks occur?

I was reading about deadlocks in Operating Systems. Where I came across two examples below. Circles with label $P_x$ are processes. Squares with label $R_x$ are resources. Each dot in the square ...
336 views

### Seems like NP cannot equal coNP by the definition of NP

A yes answer to an NP problem must be deterministically verifiable in polynomial time. The complement is that the no answer must be similarly verifiable. If the problem is NP-complete, there will ...
19 views

### What are the theoretical and practical contributions of Multiagent Systems to science?

Speaking about multiagent systems (MAS) is about as fuzzy as talking about artificial intelligence systems (AI). They are in essence the distributed counterpart of AI. While there are no so-called ...
46 views

80 views

### NP-hard complexity proof [duplicate]

I have this resource allocation problem (a special case of my main problem), as follows, for which I have been trying to show it is NP-hard. I have a set of Items, each item i has a size s(i) and a ...
28 views

### Computer won't boot up [on hold]

Whenever I try to turn on my computer, it won't boot up into the bios (pressed f8 at start) or windows or anything like that. It's a black screen. I think some kind of virus messed around with my MBR ...
42 views

### How can i prove that every NFA can be converted to a equivalent NFA that has only one accepting state? [on hold]

I don't even know how to begin ! If you can even give me a hint on how to start proving that i would be appreciated.