# All Questions

35,118 questions
Filter by
Sorted by
Tagged with
17 views

### What Is The Appropriate Action To Take When You're Shortest Path Algorithm Finds A Negative Weight Cycle?

Typing out negative weight cycle again and again is kind of annoying, so for the rest of the question I'm going to abbreviate it to NWC. I'm writing an optimized version of Bellman-Ford's Shortest ...
6 views

### The maximum decimal integer that can be stored in memory of 8-bit word processor computer?

Actually i am preparing for an exam and in the last year exam this que. was been asked. i.e The maximum decimal integer number that can be stored in memory of 8-bit word processor computer ? a)...
3 views

### Functional Dependencies on relational schema

Given a relational schema R(V,W,X,Y,Z) with functional dependencies F = {VW -> X, X -> YZ, W -> VX, V -> W, Z -> XY}. What are the keys of R? Is the key just V? If so is { R2(V,W,Z) , R3(V,X,Y) } ...
9 views

### “Unrolling” a recurrence relation

int function(int n) { int i; if (n <= 0) { return 0; } else { i = random(n - 1); return function(i) + function(n - 1 - i); } } ...
52 views

### generic way to convert imperative if-then-else statements into functional style?

In this question, I asked about a reference for translating imperative code to functional code. I want to ask a more specific question here. How, in general, do we translate into functional style, a ...
6 views

### Unambiguous grammars with different right and left hand derevations

I read recently that for an unambiguous grammar the left hand derevation need not necessarily be equal to the right hand derevation. Can someone give an example of this.
101 views

### Determine endpoint of a graph given as a list of nodes + direct successors and predecessors

EDIT @20190313 I can rephrase my question a follows : I am given everyday a non weakly-connected directed graph by its so-called adjacency list representation -- nodes are stored as objects, and ...
14 views

### Sizing a Cuckoo filter for a subset of elements

Question I am considering the use of Cuckoo filter for a business case. To simplify the explanation here is an analogy of my needs: There are over $n = 30 000$ first names that exists in the whole ...
13 views

### Really confused about latency with pipelining

I finished watching a video about pipelining https://www.youtube.com/watch?v=eVRdfl4zxfI which I thought made sense. Latency is the amount of time it takes to complete each instruction. Even with ...
2k views

### Go-Back-N ARQ Protocol Throughput Question

I am an undergraduate studying Data Coms and Networking and this question about go-back-N ARQ popped up that I am struggling to get my head around and cant find anything similar online. Any help at ...
46 views

### Algorithm for finding “mean center” of unweighted graph

I have a large sparse unweighted undirected graph (20M vertices, 60M edges) and would like to find what I'm calling the "mean center" (the vertex w/ shortest mean distance to all other vertices. Does ...
11 views

### How to solve this problem using the Maximum matching algorithm for general graph?

For any general graph G(V,E) , the maximum matching can be calculated in O(√V.|E|) time using the following algorithm : https://www.researchgate.net/publication/...
7 views

### How to find Exponential Generating Function (EGF) for the class of rooted labelled trees?

Does anyone know how to solve this problem? problem: Let C be the class of rooted labelled trees such that the labels along any path stemming from the root form an increasing sequence. Use the boxed ...
7 views

### How would you write this code in MATLAB? [closed]

How would you write this code in MATLAB?
22 views

### Shuffling a collection too large for memory

I have a set that is too large to hold in memory but I have a function that I can use to compute a value within the set given an index. I'm curious if there's a standard way to shuffle this set, a ...
66 views

5 views

### Nondeterministic Logarithmic-space in directed graph

I continue to learn the complexity myself, currently I am interested in the complexity of space. I have read several books and tried some exercises as a practice. I would like to have your idea on the ...
27 views

### Proving NP completness

Let G = (V, E) be a directed graph. Consider the problem of dividing V into two disjoint parts A and B such that there does not exist directed cycles in A or B. Prove that this problem is NP-complete. ...
45 views

### Floyd's cycle detection algorithm, why is it linear time, and how do you prove that tortoise and hare will meet?

I haven't been able to find a full proof of Floyd's cycle detection algorithm. All proofs that I have been able to find just explain why the distance from the start of the graph to the start of the ...
7 views

### When would Kosaraju's algorithm be a better choice than Tarjan's for strongly connected components?

I know both have runtime complexity $\mathcal{O} (V+E)$, but Tarjan's algorithm does a single DFS pass, whereas Kosaraju's does two DFS passes. Both need extra space (e.g. a dynamic set, often a stack,...
46 views

### Find function that satisfy the relation

Can you find the function that satisfy the relation? $$f(n) = \Theta(g(n)), f(n) = o(g(n))$$
11 views

### Fault localisation using model checking

In many papers like Empirical Evaluation of the Tarantula Automatic Fault-Localization Technique there is a good explanation about how tarantula algorithm can be used with test suits. Is there any ...
11k views

### How to find a minimum cut of a network flow?

I am currently reading the lecture slides from Princeton regarding network flows but I cannot understand how they manage to find out minimum cuts from a directed graph. Could someone explain how to ...
22 views

### Exit Condition for Knight's Tour Using Depth-First Search

Suppose I'm using the algorithm below to perform Depth-First Search in a 2d Grid. It seems like it should be possible to adjust it to perform a Knight's Tour with little change. For example I would ...
54 views

### What other instructions are stored in the ROM?

Apart from the start-up instructions, what other programs are stored in the ROM?
35 views

### What is the denotation for identifiers?

I am trying to understand what is the domain for denotational semantics. Right now the way I understand denotational semantics is that given some syntax of a program that maps to some mathematical ...
22 views

### Is there a pda with maximum 3 state for every CFL?

This is the first question I'm asking here I'm trying to understand whether we can construct a PDA with a maximum of 3 states for every possible CFL or not? if so how?
31 views

8 views

### Duplicating ACKs and Window Sizes

After reading an answer at this link: https://serverfault.com/questions/503345/three-duplicate-acknowledgementss I am confused. Do ACK values repeat when a packet is lost or when an out of sequence ...
19 views

### Rank of root in AVL tree

Find a function that bounds from above and below (asymptotic) the rank of the root r in an AVL tree, i.e. find a function $f(n)$ so there exists a constant $c>0$ that for every AVL tree with $n$ ...
274 views

### How to deal with cost variation in a dynamic graph when applying Dijkstra

What are the methods to deal with variations in cost in a dynamic graph when applying Dijkstra? For instance, I select the shortest path in a graph, however, the weight of this path changed after I ...
14 views

### Algorithm For Random Distribution of Prizes Over A Given Time Period

I have been assigned a task to come up with an algorithm for evenly distributing prizes over a given time frame, I am looking for advice as I am a bit stumped on where to start. Here are my ...
251 views

### reinforcement learning in gridworld with subgoals

Andrew Ng, Daishi Harada, Stuart Russell published a conference paper entitled Policy Invariance Under Reward Transformations: Theory and Application to Reward Shaping. There is a specific example ...