All Questions

Filter by
Sorted by
Tagged with
0
votes
1answer
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 ...
0
votes
0answers
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)...
0
votes
0answers
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) } ...
1
vote
1answer
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); } } ...
0
votes
1answer
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 ...
1
vote
1answer
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.
0
votes
1answer
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
1
vote
1answer
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 ...
4
votes
1answer
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 ...
0
votes
0answers
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/...
0
votes
0answers
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 ...
0
votes
0answers
7 views
2
votes
1answer
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 ...
0
votes
1answer
66 views

Is there any simpler way to have for each sequence element the amount of succeeding larger elements than to implement an AVL tree?

I have a sequence. And now for each element in this sequence I would like to know how many subsequent elements are larger. Or, in other words, I have a sequence $a_1, \ldots, a_n$, and for each $1\leq ...
0
votes
1answer
24 views

Determining recursive enumerability of given languages

I came across following problem: $L=\{M$ is a turing machine $M$ accepts two strings of different length $\}$ $L=\{M$ is a turing machine $M$ accepts atleast two strings of different length $\}...
-1
votes
0answers
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 ...
-4
votes
0answers
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. ...
0
votes
1answer
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 ...
1
vote
0answers
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,...
0
votes
2answers
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))$$
0
votes
0answers
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 ...
4
votes
4answers
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 ...
0
votes
0answers
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 ...
1
vote
2answers
54 views

What other instructions are stored in the ROM?

Apart from the start-up instructions, what other programs are stored in the ROM?
2
votes
1answer
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 ...
0
votes
0answers
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?
0
votes
1answer
31 views

Does $f(n)=\theta(g(\log{n}))$ imply $f(n)=\theta(\log{g(n)})$?

I am learning about algorithmic complexities and I have this claim which I need to prove or disprove: $f(n)$ and $g(n)$ are asymptotically positive functions, if $f(n)=\Theta(g(\log(n))$ then $f(n)=\...
-2
votes
0answers
8 views

Find the width of the field

The computer has a byte addressable main memory of 2 16 bytes and block size of 8 bytes. Assume that a direct mapped cache consisting of 128 lines used with this computer. And separate into three ...
8
votes
1answer
201 views

is $P_{CTC} = BPP_{path}$?

I think that these two classes should be the same, but I can't find any literature about this and have a limited background on the topic. This is my reasoning, and I would like to know if (1) this is ...
1
vote
0answers
19 views

A pda that accepts all strings over an alphabet

If you were asked to construct a pda that recognizes all strings over the alphabet {a,b,c,d}, that is L={w | w belongs to (a,b,c,d)*} How would that be constructed? My idea is to have one state as ...
7
votes
2answers
783 views

Algorithms that run in polynomial time if P=NP

On Wikipedia, it says that that there are some algorithms that would run in polynomial time if and only if P=NP. They gave one example (without citation), but are there any others? I tried looking ...
0
votes
0answers
23 views

Asymptotics of reccurence relation

I need to tell whether $\quad\exists a \quad T(n) = \omega(n^2)$ $T(n) = T(\frac{n}{2}) + aT(\frac{n}{4}) + n^2\\\\ \forall n<10 \quad T(n) = 1$ And if there is such $a$ I need to find the ...
1
vote
1answer
24 views

center selection problem: Simple greedy algorithm

I am trying to understand the following text which defines a greedy algorithm for center selection problem: It would put the first center at the best possible location for a single center, then ...
14
votes
2answers
8k views

Efficient algorithm for retrieving the transitive closure of a directed acyclic graph

I'm trying to solve a graph problem (it's not for homework, just to practice my skills). A DAG $G(V,E)$ is given, where $V$ is the set of vertices and $E$ the edges. The graph is represented as an ...
0
votes
0answers
8 views
0
votes
0answers
7 views

Saving output of variable size from a Matlab function [closed]

I am running a Matlab function that finds all cycles in a directed graph. The problem is that sometimes the function returns one vector, but sometimes it returns several vectors. Moreover, the vectors ...
4
votes
2answers
521 views

Does the underlying computational calculus in type theories affect decidability?

I'm looking for a high-level explanation although if that isn't possible or difficult, I'd prefer references to books/papers. I understand that modern type theory is inspired by Curry-Howard ...
2
votes
1answer
48 views

What is an algorithm to find the largest rectangle of white space in an image?

Take an image, (the Google home page) is a good example. I want an algorithm to find the largest white rectangle in this image. That is to say, the largest rectangle that would fit in an area of ...
1
vote
1answer
70 views

Do data points mean Eigenfaces in higher dimensional space?

I saw the following animation at making sense of PCA , which shows blue data points. I am reading a paper on Eigenfaces which says that: "a typical image of size 256 by 256 becomes a vector of ...
1
vote
1answer
54 views

Converting DFA to Regular Expression Using State Removal

I'm trying to convert the following NFA to a regular expression. I've attached my work below and end up with the expression $aa^*bb^*$. As far as I can tell, this doesn't seem correct but I've been ...
1
vote
1answer
32 views

Converting this NFA-e to DFA

I came across this question about NFA-e and thought to convert it into DFA: This is what I did. $\begin{array}{|c|c|} \hline & a \\ \hline q_1&q_2 \\ \hline q_2&\phi \\ \hline q_3&...
0
votes
0answers
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 ...
0
votes
0answers
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$ ...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
4
votes
1answer
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 ...
0
votes
1answer
50 views

Can I find all the common subsequences between 2 sequences by using dynamic programming?

I need to know if there's a dynamic programming algorithm that returns all common subsequences between 2 sequences not just the longest one. Thank you.
0
votes
1answer
426 views

multiple sequence alignment using HMM and simulated annealing

Can anyone help me with Multiple Sequence Alignment (MSA) using Hidden Markov Model (HMM) by giving an example or a reference except these 2 references: 1-Eddy, Sea.R., et al.Multiple alignment using ...

15 30 50 per page
1
2 3 4 5
703