# All Questions

28,854 questions
1answer
48 views

### What is the fastest algorithm to establish whether a linear system in $\mathbb{R}$ has a solution?

I know the best algorithm to solve a linear system in $\mathbb{R}$ with $n$ variables is Coppersmith-Winograd's algorithm, which has a complexity of $$O\left(n^{2.376}\right).$$ How much easier is ...
1answer
23 views

### jump to MMIO address

In the ARM architecture, what happens on executing a jump instruction whose jump target address is an MMIO address (or in paging mode, a virtual address that is mapped to an MMIO address)? Would this ...
2answers
29 views

### Are Big-Theta functions asymptotic monotonically non decreasing?

For example, suppose $f(n) = \Theta(n^2)$, then does that mean for any sufficiently large $n$, $f(n) \le f(n+1)$? Is it a general case for all Big-Theta?
2answers
49 views

### Is $f(cn)$ always $O(f(n))$ for constant $c$ and any function $f$?

This seems to be true for any function I can think of, but I'm not quite sure how to prove it. Is there a proof of this proposition for any such function or a counter-example?
0answers
11 views

### Superposition calculus: Elimination of redundant atoms

Bachmair and Ganzinger (1991), 'Rewrite-Based Equational Theorem Proving With Selection and Simplification', section 5.2, 'Simplification and Deletion Techniques', page 17, 'Elimination of redundant ...
1answer
15 views

### Algorithm for blending/merging shapes together like liquid

This is a basic example of how 2 circles would come together: A more complex example would be an arbitrarily shaped polygon like a country on earth, merging with another one or a circle. All of the ...
0answers
55 views

### Undecidability of the “Single-Halting Problem”

I have to show for a turing machine S that is taking another TM T and a word x as input and only halt for one specific T and x, that it is not decidable. The idea is now to reduce it to the halting ...
0answers
27 views

### Time complexity of Dijkstra's algorithm for sparse graph

I'm not sure I understand the answer to this question: As I understand it, the algorithm runs in O((E+V) * log(V)) with binary heap. Thus when, E = V^2/log(V), ...
1answer
77 views

### Who first introduced the pushdown automaton?

I'm interested in learning more about the history of automata theory and have tracked down many of the original papers on Turing machines, finite automata, and the like. However, I'm having trouble ...
2answers
44 views

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?
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 ...
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 ...

15 30 50 per page