All Questions

1
vote
2answers
52 views

Algorithm for closest available resource

My apologies if question is not in correct format. I don't post here often. I don't know what tags would be appropriate for this question, or even if this is an appropriate question. Looking for ...
0
votes
0answers
24 views

Computer Networks, bandwidth calculation

I don't know if this is the right place to ask this kind of questions, but I'm a little desperate and I can't find the answer to this Computer Networks exam question. "A point to point 1000 km ...
1
vote
0answers
6 views

When estimating camera motion from the fundamental matrix, why can translation only be recovered up to scale using epipolar geometry?

I was wondering once you have recovered the fundamental matrix F such that xFx' = 0. If you try to recover translation and rotation from F, I am told that this is possible only up to scale? Why so?
0
votes
2answers
19 views

calculation of Transitive Closure

This question is not from homework, but rather as preparation for the test: The calculation of place-in is a calculation in which the algorithm does not need space beyond the output size (beyond ...
0
votes
1answer
29 views

Applying minimax tree to this array [on hold]

Please tell me how I should apply minimax algorithm to the array $$ 15, 12, 14, 16, 11, 13$$ and make a tree?(I understand how minimax algorithm works but I can't apply it to an array)
0
votes
1answer
11 views

What is a genuine atomic multicast?

What is a genuine atomic multicast? What is the difference between a genuine and non-genuine atomic multicast?
1
vote
1answer
38 views

How to perform local search to find maximal induced subgraphs?

I'm looking for efficient ways to perform local search to find maximal induced subgraphs that satisfy certain properties : a tree, a forest or a bipartite subgraph for example. What I mean by local ...
1
vote
1answer
23 views

fixing a slightly broken BST tree

I'm stuck on this question, a BST is slightly broken only if there is a node with value x in which : there is at least one value less than x on its right branch or atleast one value greater than x on ...
0
votes
1answer
18 views

Does the Paxos algorithm use failure detectors?

Does the Paxos algorithm use failure detectors? If not, how can it solve consensus, given the impossibility result?
1
vote
1answer
38 views

How broad is the meaning of “algorithm”?

This is a purely terminological question. The word algorithm, as I have learnt it refers to something like an "effective method, a sequence of steps, for doing something". There are alternative ...
2
votes
1answer
45 views

Confusion about proof of undecidability of REGULAR TM in Sipser's book

in the book "Introduction to the Theory of Computation" by Michael Sipser there is an example of undecidable languages in which there is a language REGULR_TM which is described as follows : ...
3
votes
2answers
229 views

Transforming a byte with a subset of a small, fixed set of values and xor into any other value

If I have some collection of bits, -- a byte, say -- of arbitrary value then I can transform it into some other value by means of exclusive-oring it with a subset of (in this case) eight fixed values, ...
3
votes
1answer
91 views

d-ary heap implementation vs Fibonacci heap implementation Dijkstra performance comparions

Let's say that Dijkstra’s algorithm with the priority queue using a d-ary heap. if adjusting d, we can try to achieve the best runtimes for the algorithm with d being $\sim |E|/|V|$. Then for a ...
1
vote
0answers
27 views

Alternatives to directly connected networks for representing frequently-updated graphs

What are the relative merits of the various graph representations, such as adjacency matrix, edge list, adjacency list, directly connected network etc. Given that this graph will be frequently updated,...
0
votes
1answer
20 views

What's the difference between cache miss penalty and latency to memory?

Can I say that cache miss penalty includes latency to memory? My current understanding is that cache miss penalty is the time moving data from the layer closer to main memory to it. But I'm not sure ...
-1
votes
0answers
25 views

What's the difference between the given parse trees?

Could someone please explain what's the difference between the two parse trees in the given image and which is the right answer for the given question: Consider two binary operators && and || ...
0
votes
0answers
33 views

Can the pseudo-random-sequence generator be described as a finite state automaton?

I am thinking some real examples of FSAs in order to help me know how to use the model of the FSA. As I know, the pseudo-random-sequence generator should be a kind of DFAs or FSTs . But I cannot ...
2
votes
0answers
59 views

Equivalence between different Turing Machines and a definition of simulation

Im having some difficulty understanding how the following two concepts could be related. Equivalence between TMs as is commonly tought According to this site answer, to prove a standard TM model to ...
0
votes
1answer
19 views

How to find the angle of an arc to draw graphic

I would like to draw an arc from a specific point to a goal point, during the process of drawing a larger path. I would like to do it using bezier curves, which aren't adequate for modeling circular ...
2
votes
1answer
38 views

What is happening during “table walk”?

I am trying to understand what is a table walk. I have found when it occurs - whenever there is a TLB miss. If no descriptor is found – TLB miss occurs and further behavior depends on the ...
1
vote
1answer
44 views

RAM BSS model based (or its variant) computer recognizing Boolean languages

Can any RAM BSS model based machine, or machines which are variants, recognize boolean languages(languages such as P, NP, or the like)? If so which languages are recognizable by RAM/BSS nachines, or ...
4
votes
2answers
63 views

When is this even possible (even for a dense graphs) $|E| = \Theta (|V|^2)$

Wikipedia says that "a dense graph is a graph in which the number of edges is close to the maximal number of edges." and "The maximum number of edges for an undirected graph is $|V|(|V|-1)/2$". Then ...
0
votes
1answer
27 views

Why is a heap better than a linked list for implementation of a priority queue?

Using a heap, you have O(log(n)) insertion and O(log(n)) removal. Using a linked list, you have O(n) insertion and O(1) removal. Why is it better to have log-n for both than n for one and constant ...
1
vote
1answer
24 views

Is there an existing algorithm for this type of sorting?

This TED-ED video talks about some of the most basic sorting methods (bubble sort, insertion sort and quick sort,) in response to a scenario where a librarian ends up with a stack of 1,280 unsorted ...
1
vote
0answers
20 views

Order of Traversal in Bidirectional Dataflow Analysis

Does order of traversing CFG matter in solving bidirectional dataflow problems, from a performance perspective?
1
vote
0answers
15 views

The underlying type theory of HOL/Isabelle

Is there a good source on the type theory of HOL/Isabelle/other HOL-based LCF-style theorem provers?
1
vote
1answer
27 views

Intersection of two incomplete DFAs

Let assume that I have the following two automata A1 and A2 : I have to do the intersection of the two, so I did this : My question is related to the "∅". If I have two incomplete automata without ...
2
votes
1answer
23 views

Convert NURBS curve into Cubic Bezier Curve

From this: Maybe you already know this, but it's impossible to convert nurbs to bezier splines exactly because nurbs are rational functions, and bezier splines are polynomials. I don't understand ...
0
votes
0answers
19 views

Computational type theorists: how do you compare terms for equality here?

I am attempting to implement Simple Type Theory in the language D. How do you compare subterms to a term $R$ for the sake of computing the covering abstractors of $R$ in $M$? By reference (class ...
0
votes
0answers
17 views

Minimum spanning tree classification problem with adjacent neighbors

I am new to minimum spanning trees. But have used the last few days on a problem I think matches MST, but cannot really figure out the connection. The problem is a minimum cost problem where N ...
1
vote
2answers
29 views

Are all instructions eventually converted to zero-operand instructions?

Recently, my demonstrator said that all instructions are eventually converted to zero-operand instructions just before they get executed. yet another demonstrator said that this "doesn't make any ...
5
votes
1answer
723 views

What is the complement of a language?

If given any language L, how do I find the complement of said language? I lack the basic understanding required to determine if a language is co-recognizable. I understand that a language, $L$, is co-...
-2
votes
0answers
15 views

Why is it so difficult to implement memory protection in AmigaOS/AROS? [on hold]

The FAQ of AROS says: "This indicates that it's quite unlikely that the normal AmigaOS will never [sic] have MP like Unix or Windows NT.". Why is it so difficult to implement memory protection in ...
2
votes
3answers
43 views

When average , worst and best case time complexity happens in quick sort?

I know recurrence relation corresponding to quick sort worst case is $T(n)=T(n-1)+T(0)+\Theta(n)$ and time complexity is $O(n^2)$. This happens when we select pivot which is either largest element ...
1
vote
1answer
49 views

Proccess scheduling arrival time

If I have a set of processes, let's say 9 and I know the burst time and the waiting time for SJF algorithm and also know that processes arrive in groups of 3 processes at M1 moment, M2 moment, M3 ...
0
votes
0answers
10 views

Push Down Automata [on hold]

What is the purpose of stack in Push down Automata, does it has to do something with the word count of a language or just to push and pop the words of a language?
0
votes
2answers
30 views

Why is $\{a^nb^n \mid n \geq 1\}$ not type 3 (regular)?

My book states that the language $$L_1 = \{a^nb^n\mid n\geq 1\}$$ is of type 2 (context-free) but not of type 3 (regular) since there is no regular grammar to produce it. However, I can't really ...
2
votes
0answers
27 views

Is the language $L$ of coded CFG's Turing decidable?

Consider the following language $L$ = {$<G><w>$ | $G$ is a CFG and $w\in L(G)$} Now, I wish to prove that $L$ is Turing decidable. My gut tells me to construct a Turing machine that ...
-1
votes
0answers
13 views

Which book is the most definitive, yet elementary, discussion of C? C++? Python? [closed]

I in October 2018 completed the MITx course INTRODUCTION TO COMPUTER SCIENCE AND PROGRAMMING USING PYTHON on the edx.org web platform by scoring 97% marks. Besides that, I've also read the first few ...
2
votes
0answers
32 views

What is the compressibility of this simple “book”?

Compressibility is defined as $$C=\frac{2^{HN}}{2^{H_{max}N}}$$ The book is made up of a simple alphabet of only {a,b,c,d} which occur with probabilities $$P(a)=0.2, P(b)=0.4, P(c)=0.1, P(d)=0.3$$ ...
0
votes
0answers
23 views

Run time analysis of inner loop [duplicate]

What is the run time of the following piece of code in Big-Oh notation? The first loop runs n times in the worst case. But I am having difficulty in finding run time of nested loop which runs V / deno[...
0
votes
0answers
25 views

What is the ideal complexity of a task with (n-1)!/2^(n-1) possible threes?

I have n elements to connect. Each element has a given length. My objective is to connect all the elements, so that I get one large, with length sum of all elements. The elements must be connected the ...
2
votes
0answers
12 views

Relaxations for MILP with logical constraints

I have an LP with a (non-fixed) number of logical constraints in the form of $X_1 \rightarrow X_2$ (where $X_1$ and $X_2$ are linear functions inequalities of the $n$ input variables). To express ...
0
votes
0answers
17 views

Finding disjoint paths between any number of cell pair marked in nXn matrix

What should be algorithm to find all the disjoint paths between any number of pairs of cells given in matrix? We will say two paths will not intersect if there there is no cell common between any two ...
1
vote
1answer
25 views

Ketama hash explanation

(I originally posted this on stackoverflow but thought it would be a better fit here) I'm trying to understand the Ketama hash code used in consistent hashing. link and snippet below: ...
3
votes
1answer
38 views

Matrix Representation for logical gates?

I have been trying to find if there are other matrix type representations logical circuits, in the example below, $$\begin{bmatrix} 1 & 0\\ 1 & 1\\ \end{bmatrix} \equiv \, \, \Rightarrow$$ ...
0
votes
0answers
18 views

A linear ordering of G that puts v before w iff there is no path from w to v [closed]

Is the following a good enough proof? Let $G'$ be the graph $G$ with an edge $e$ added from $v$ to $w$. We note that a linear ordering of the form we are looking for must respect all edges of $G$ ...
0
votes
0answers
18 views

How to use a select case in visual basic? [closed]

If picked up in store customers gets charged regularly price. If shipped they get charged $5 extra.
0
votes
0answers
16 views

How to generate evenly distributed random numbers from the tics of a Geiger Counter?

How can I generate random numbers from the tics of a Geiger Counter? Say I have a file with the timestamps for every event. 0 325 456 920 .... The time spans ...
0
votes
0answers
7 views

Finding all possible exclusive cliques in a graph

TL;DR I need to find all possible ways to traverse an undirected cyclic, possibly disconnected graph to find all exclusive sets of connected nodes which satisfy certain criteria. There's a graph of ...

15 30 50 per page