All Questions

1
vote
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 ...
0
votes
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 ...
2
votes
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?
1
vote
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?
0
votes
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 ...
0
votes
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 ...
-1
votes
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 ...
0
votes
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), ...
5
votes
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 ...
2
votes
2answers
44 views

Solving $T(n) = 3T(n-1) + 2$

I am trying to get better at solving recurrence relations, so I am making my own simple relations and try to solve them. I have made the following recurrence: $$T(n) = 3T(n-1) + 2, \quad\quad T(1) = ...
0
votes
0answers
27 views

Merging two splay trees whose ranges may overlap in $O(\log N)$

I have two splay trees, $A$ and $B$. When every element in $A$ is smaller than every element in $B$, we can merge them in $O(\log N)$. My question is; when all elements of $A$ are not necessarily ...
-1
votes
0answers
30 views

Program in C++/C# for modifying images [on hold]

I want to make a C++ program that has as imputs an image $D\subset\mathbb{C}$ and a complex function $f:\mathbb{C}\to\mathbb{C}$, which move the pixel $p_{mn}$ of the picture (we associate to this ...
2
votes
1answer
62 views

Max flow and Matching problem

Where can i find a list of problems reducible to max flow and matching problems. I need such examples to learn and practice .
1
vote
0answers
34 views

Error detection in sequence of integers

Let's say I receive a large sequence $s$ of numbers $n_0$, $n_1$, $n_2$, $\ldots$ Later I expect to receive the same sequence $s^*$ with the same numbers $n_0$, $n_1$, $n_2$, $\ldots$ but errors ...
0
votes
0answers
40 views

What do return 0,return 1 & return -1 mean and what they return to whom? [on hold]

I have noticed that in main the function of c program return 0 , return 1 or return -1 is used. I searched for the same in internet and saw that return is equivalent to exit and 0 status means that ...
2
votes
2answers
34 views

Decidability of $SEQ_{CFG} = \{⟨G,H⟩ \mid \text{$G,H$ are CFGs and $L(G) ⊆ L(H)$}\}$

How can I prove that $SEQ_{CFG} = \{⟨G,H⟩ \mid \text{$G,H$ are CFGs and $L(G) ⊆ L(H)$}\}$ is decidable ? I know that $EQ_{CFG} = \{⟨G, H⟩ \mid \text{$G,H$ are CFGs and $L(G) = L(H)$}\}$ is not.
3
votes
2answers
236 views

Bucket computation, cutting array with lines

Given an NxN array, drawing a line from the edge's midpoint to the opposite field how can the N buckets be found covering the majority of the line's path? A visual aid: Is there a better way to ...
1
vote
0answers
20 views

Understanding Dynamic Frequency Warping (not Dynamic Time Warping)

I am implementing a paper which need Dynamic Frequency Warping as a component. They have written very briefly about this algorithm and cite to this paper: Voice transformation using PSOLA technique (...
1
vote
2answers
32 views

Choosing heuristic for A* algorithm where cost is less than absolute distance

Looking for information on choosing a heuristic for instances where the cost of traversing an edge can be less than one. For example, say movement is allowed in the cardinal directions. Should all ...
1
vote
0answers
21 views

Implementation of Babai's GI algorithm

Babai proved that there is a quasi-polynomial-time algorithm for graph isomorphism. Has anyone implemented this algorithm? I think the code will be easier to understand than his paper, because of the ...
1
vote
2answers
21 views

System restarted before transaction is committed

Consider the following log sequence of two transactions on a bank account, with initial balance 12000, that transfer 2000 to a mortgage payment and then apply a 5% interest. ...
2
votes
1answer
33 views

Reasoning about resources: “resource logics”?

Are there extensions of predicate logic which focus on resource models, possibly even in actor models? And if so, would it be possible to reason on a meta-level on how many resources should be ...
1
vote
1answer
38 views

Reducing a graph without changing its chromatic number

Does reducing a graph (removing or replacing vertices or edges) without changing its chromatic number has a specific name? Take this cactus graph as an example (although my question is about an ...
0
votes
0answers
21 views

Finite State Automata for English regular main verbs

I would like to build an FSA to recognise english regular main verbs. E.g. walk, play, call, look, etc... with following morphological forms: (1) base form, (2) third person singular (-s), (3) present ...
0
votes
0answers
19 views

Relevance of the ZeroSum game to Heuristic search?

A question was posed to me as to the relevance of the ZeroSum game to Heuristic search algorithms. I know that the zero sun game is a theory in which one persons gain is exactly balanced to another ...
1
vote
1answer
33 views

Space and time complexity of $L = \{a^nb^{n^2} \mid n≥1\}$

Consider the following language: $$L = \{a^nb^{n^2} \mid n≥1\}\,$$ When it comes to determining time and space complexity of a multi-tape TM, we can use two memory tapes, the first one to count $n$, ...
1
vote
1answer
38 views

Constructing a pushdown automaton that accepts L*

Would appreciate if you could take a look at what I did and help me finish it. Given a pushdown automaton that accepts a language $L$ by final state, construct a pushdown automaton that accepts $L^*...
1
vote
2answers
42 views

Either find a perfect matching, or return a witness that none exist [duplicate]

I am looking for a polynomial-time algorithm that takes as input a bipartite graph $(X\cup Y, E)$, and returns one of two options: If a perfect matching exists, it returns the matching; Otherwise, it ...
0
votes
0answers
18 views

Numpy Array of Strings [on hold]

I am not sure that this question is suitable for here, but since it is about data science python module, that is numpy, I decided to post it. In python, empty string consumes 49 bytes because it ...
2
votes
0answers
20 views

How does the free program identifiers (fpi) extend over constraints and type schemes in $HM(X)$?

Chapter 10 of Advanced Topics in Types and Programming Languages; gives a very comprehensive description of type inference by constraints solving. They introduce the free program indentifiers of an ...
-2
votes
0answers
19 views

4-Way Set Associative Cache - which sets will be evaluated? [on hold]

A computer has got a 4-way set associative cache. 4 Bit Offset 4 Bit Set 21 Bit Tag The processor acces the memory adress 0x000164A2. Which sets will be evaluated in order to find a cache-hit?
1
vote
1answer
27 views

is $0^x1^y$ context-free?

given that L is regular, does the following make a context-free language?: i) $\{0^x1^y \mid 0^{x+y} \in L\}$ ii) $\{0^x1^y \mid 0^{x-y} \in L\}$ since L is regular, i presumed that i) can be put ...
1
vote
1answer
14 views

Expecation of $u'^t v$ = $u^t v$

I have another question with dimensionality reduction. I have a matrix $S \in R^{k \times d}$ and S is in {$- \frac{1}{\sqrt k}, \frac{1}{\sqrt k}$} and i have two vector $u,v \in R^d $. I need to ...
0
votes
1answer
19 views

Can all Turing-computable problems be solved with a machine with finite tape and infinite controls?

We know all computer computable problems can be solved using the infinite tape and finite control system of the turing machine. Now think something different, let the tape is finite but the control ...
1
vote
1answer
36 views

Instructing operating system - Knowing it's functionalities

TL;DR: I would like to know how a programming language, the OS and drivers work together to perform a task. I (and we all) have used various softwares/modules/packages on the top of our OS which ...
1
vote
1answer
27 views

What's the worst case complexity of Robert W. Floyd's cycle detection algorithm?

Givens. I understand Floyd's algorithm can determine the length $\lambda$ of the loop and the length $m$ of the tail. The hare will not necessarily catch the tortoise on the first cycle, but it is ...
0
votes
0answers
18 views

In a Min-Cut problem, how many times do i need to run Karger's Algorithm in a given set of nodes?

Question: Given 22 nodes, how many times do I need to run Karger's algorithm in order to find A min-cut problem within an error range (say, <2 or between 0-1) ?
0
votes
1answer
32 views

Difference between stable marriage problem and assignment problem

What is the difference between the stable marriage problem and an assignment problem? Both refer to a matching problem in general but what is their specific difference? I can see clear differences in ...
0
votes
1answer
19 views

How can I calculate attenuation from signal strength values? [on hold]

I want to measure attenuation caused by a material. In order to do this, I first measured the signal strength of the access point which is my mobile phone (hotspot). Then, I wrapped my phone with the ...
1
vote
0answers
35 views

A look at an exact smallest grammar algorithm. How do we compute running time big-O?

A smallest grammar of a string $s$ over an alphabet $\Sigma$ is a smallest CFG $G$ such that $L(G) = \{s\}$, where size is the total number of symbols occuring on the right sides of production rules ...
0
votes
1answer
26 views

Normal form after decomposition of a relation

I came across a text recently which claims that if we perform a lossless decomposition of a relation R into smaller relations R1 and R2, and if R is in 3NF, both R1 and R2 are 3NF. I felt a bit ...
2
votes
1answer
100 views

What is the Big-Ω of the following function?

For the following function: $$ \sum_{n=1}^{2n}x+x^2 $$ It is easy to see the (tightest) Big-Oh is $O(n^3)$, but I am not so sure about the Big-Omega. Here is my attempt: $$ \sum_{n=1}^{2n}x+x^2 $$ $...
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 ...

15 30 50 per page