# All Questions

28,862 questions
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 ...
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 ...
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?
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 ...
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)
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?
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 ...
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 ...
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?
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 ...
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 : ...
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, ...
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 ...
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,...
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 ...
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 || ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
20 views

### Order of Traversal in Bidirectional Dataflow Analysis

Does order of traversing CFG matter in solving bidirectional dataflow problems, from a performance perspective?
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?
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 ...
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 ...
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 ...
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 ...
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 ...
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-...
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 ...
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 ...
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 ...
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?
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 ...
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 ...
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 ...
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$$ ...
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[...
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 ...
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 ...
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 ...
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: ...
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$$ ...
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$ ...
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.