0
votes
1answer
10 views

Proving complexity of computing product of matrices

If $A$ is a non-singular $n\times n$ matrix, $B$ is an $n\times p$ matrix, and $C$ is a $p\times n$ matrix (where $1\le p \ll n$), how does one prove that the complexity of $$D=A^{-1}(BC)$$ is $\frac{...
2
votes
1answer
19 views

Are some real world compression algorithms sometimes producing unexpectedly large files?

Lossless compression is not magic. It just gives the common patterns a short notation, compensating by the less common patterns ending up with a longer notation. By that logic, all lossless ...
0
votes
0answers
6 views

Scheduling problem shared ressources

I'm trying to build a mathematical model of the following problem. Given m parallel packaging lines and the production orders (POs) for the day on each line, we place a cleaning activities between 2 ...
0
votes
1answer
12 views

Embedding high dimensional vectors into low dimensional space preserving similarity

I have a collection of high dimensional vectors such as $\vec{a}_{i} \in \mathbb{R}^{n}$ where $n$ is 3000. What I want to do is to embed these vectors into a space such as $\vec{b}_{i} \in [0, 255]^{...
0
votes
0answers
17 views

Is there exist an external radix sort algorithm?

Is a version of radix sort that can work in list that do not fix in memory? Or other linear time sorting algorithm that can work in that way?
0
votes
0answers
28 views

Data Compression Algorithm for Less repetitive pattern (redundancy) [on hold]

Context: Lossless Data compression (source coding) algorithms heavily rely on repetitive pattern (redundancy) Questions Which data compression method/algorithm deals with less repetitive ...
0
votes
0answers
17 views

Why Transmission depends on the Interference of other Links

I was reading Congestion aware channel allocation with route scheduling in wireless cognitive radio mesh network, (by Jia et el, Computers and Electrical Engineering 39 (2013) 1346–1357) and I found- ...
1
vote
3answers
268 views

Using Data Compression on the output of Data Compression

Context: Lossless Data compression (source coding) algorithms heavily rely on repetitive pattern (redundancy) Questions Is there a data compression method/algorithm that uses another data ...
0
votes
0answers
22 views

Computational Complexity of Exponential Expression Divisibility?

Garey and Johnson mentions the problem of 'Exponential Expression Divisibility" as "Not known to be in NP or co-NP, but solvable in pseudo-polynomial time using standard GCD Algorithms". Pseudo-...
0
votes
0answers
12 views

Minimal hypergraph transversals

the exact complexity for hypergraph transversal problem is yet unknown and is an open research problem. However, I would need a fast way to compute, on paper, the minimal transversal of a hypergraph. ...
2
votes
0answers
31 views

Overflow of integer counter in distributed systems

I've just been introduced to Paxos. There is notion of the of value that is incremented each time a new proposal is send. To provide order for proposals, something like time. What happens when this ...
-1
votes
1answer
41 views

how to computer-scientifically remove virus on my laptop [on hold]

My laptop got some virus. The model is ASUS VivoBook E200HA-US01-GD. The problem is, I don't trust these antivirus softwares. Is there a way to remove virus using computer science?
-3
votes
0answers
8 views

ImageCreate() php in ubuntu [duplicate]

i've got an error in ubuntu.Can you guys help me?plzzz :( imagepng(Image_QRCODE_H.png): failed to open stream: Permission denied in /var/www/html/qrcode/phpqrcode/qrimage.php on line 43
-2
votes
0answers
15 views

ImageCreate() php in ubuntu [on hold]

i've got an error in ubuntu.Can you guys help me?plzzz :( imagepng(Image_QRCODE_H.png): failed to open stream: Permission denied in /var/www/html/qrcode/phpqrcode/qrimage.php on line 43
1
vote
1answer
20 views

Complexity of matrix inverse via Gaussian elimination

I'm trying to determine the exact complexity of finding an $n\times n$ matrix inverse of $A$. If it is known that the complexity of Gaussian elimination is $\frac{2}{3}n^3 + \frac{1}{2}n^2+O(n)$, then ...
0
votes
0answers
11 views

Input/Output encoding using LSTM for time series prediction

I have a rather basic problem with understanding LSTM neural networks. My basic problem is predicting a timeseries of data points. Each time step gives me a single value which can be encoded as a ...
3
votes
0answers
41 views

Solving systems of boolean equations

So I have a system of equations where varibles range over $\{0,1\}$ and the only operation is logical or ($\lor$). Each equation is of the one of two forms 1) $a = b \lor c$ 2) $1 = a \lor b$ where ...
1
vote
0answers
13 views

Fast generalised suffix array construction: lower than O(n^2 log n)

There is a lot in the literature about linear time constructions for suffix arrays; DC3, radixSA46, and more... However, these, I believe, are only for suffix arrays; with a single string input. Are ...
1
vote
0answers
44 views

Is there a philosophical counterpart question to P != NP?

Gödels motivation to prove his incompleteness theorems was the philosophical statement "This sentence is wrong.". Is there a philosophical counterpart to the statement P != NP? For example such ...
-3
votes
0answers
17 views

how to uninstall windows 10 on my mac? [on hold]

I clicked a windows 10 ad link on my macbook then it just wiped my drive and put a windows 10 on it. I think the ad link is a spam, now my mac runs windows 10 instead of mac os. How to fix this?
-1
votes
0answers
14 views

How does first instruction get executed in virtual memory environment?

Currently I'm reading about virtual memory , Now I'm stuck at how CPU generate first virtual address for a process ? how page table is formed ? How this setup had been made?
2
votes
0answers
17 views

Why do we use expectation in reinforcement learning? [migrated]

In reinforcement learning we use lot of expectations, what's the logic behind them? Like in reward function, we use expected return instead of return, in value functions V and action-value functions ...
2
votes
1answer
25 views

Why not space out memory allocations?

In ext4 file system, the files are spaced out as far apart as reasonably possible to allow for efficient reallocation. Why do we not do this in memory? Why not allocate one memory as page 20, and the ...
2
votes
1answer
20 views

Identification and the definition of data type

A frequently cited definition of data type is that it is a set of values and a set of operations of those values. I've never read any mention along the lines of a type must be capable of being ...
3
votes
0answers
30 views

SSA Phi to Registers

I'm working on an LLVM-like kit for .Net - because this is something that's lacking in .Net and I really want to learn the more advanced compilation theory. I'm really struggling to find anything ...
0
votes
1answer
38 views

Deep DFS traverse on graph

First, the question is based on http://stackoverflow.com/questions/2893470. By chess rules, the (undirected) graph generated from the above problem is the following: $$ \begin{array}{ccccc} 3 &...
2
votes
1answer
38 views

Processing weighted points of interest. Is there a name for this task/algorithm?

Is there a name for the following problem? Is there a measure of quality of a given solution? How can we even define what a proper solution is? Context: I want to detect long lines (most lines over ...
-3
votes
0answers
22 views

i want to learn about graphical user interface [on hold]

I want to learn about Graphical User Interface that is to create Textbox,Buttons, logo for desktop programming, can you suggest a good book. It should be published latest.
2
votes
1answer
38 views

Negligible functions in definitions of statistical closeness and computational indistinguishability

Statistical closeness implies computational indistinguishability. Is there any (simple) relationship between negligible function that is used in definition of statistical closeness and negligible ...
-3
votes
0answers
16 views

How to resolve WIN 10 Expiration Issue [on hold]

Could someone help me in resolving my problem....please! The problem is that my win 10 is going to expire on august 20 , 2016 as per notification, please help me what can I do?
0
votes
0answers
12 views

Which implementation algorithms in the updated Lexers and Parsers are more advanced and efficient? [on hold]

I want to write a lexer and parser based on C# language in new microsoft framework .NET Core. So I have investigation about the knowledge of implementation similar libraries. Comparison of parser ...
0
votes
0answers
10 views

What is the time complexity of min-heap based solution to calendar rendering problem

Question: You are given a set of events in a day. Each event has a start and end time. Find the maximum number of concurrent events Solution: First convert events into an array of "Event ...
1
vote
1answer
37 views

Time complexity of the fast exponentiation method

I am trying to analyse the time complexity of the fast exponentiation method, which is given as $$x^n= \begin{cases} x^\frac{n}{2}.x^\frac{n}{2} &\text{if n is even}\newline x.x^{n-1} &...
1
vote
0answers
22 views

Understanding N process Peterson's algorithm

The intuitive informal description of two process Peterson's algorithm for process 0 can be given as follows: ...
0
votes
0answers
7 views

Preparing precedence graph from fork and join code

I was referring to this page which defines fork, join and precedence graph as follows: When the statement ...
7
votes
2answers
75 views

Why is first-order logic (without arithmetic) VALIDITY only recursively enumerable, and not recursive?

Papadimitriou's "Computational Complexity" states that VALIDITY, the problem of deciding whether a first-order logic (without arithmetic) formula is valid, is recursively enumerable. This follows from ...
2
votes
0answers
12 views

Clustering with probabilities / vector quantization with arbitrary distance measures

Suppose I'm given $n$ points $x_1,\dots,x_n$ in some space $\mathcal{S}$ (think: $\mathbb{R}^d$), and probabilities $p_1,\dots,p_n$ that form a probability distribution (so $p_1 + \dots + p_n=1$). ...
1
vote
1answer
41 views

What is the complexity of Array[n] and Object.value

I faced a great doubt about the Complexity of two ways of calling a information. First I have an Array, if I call an array in a program like this: print array[0] ...
0
votes
2answers
67 views

AC-3 Algorithms on CSP problem, What is happened when enocunter to an empty domain variable?

Suppose We Applying Arc-Consistency (AC3) algorithms on one Constraint Satisfaction Problem, if domain of one variable be empty, what is the next step of this algorithm? According to This Link and ...
0
votes
0answers
32 views

How can I find the “thinner” path from a cloud of coordinates? [migrated]

Following up with this, I have a bunch of coordinates and I draw them on a bitmap image as a coordinate system. Now, I would like to get rid of all the noise, and filter coordinates to give a "clearer"...
2
votes
0answers
20 views

Typed representation of a memory model

Assume a simple procedural language, where statements write and read from local memory via references and procedures accept arguments of n different scalar types (say floats, ints and strings) and ...
3
votes
1answer
85 views

Clarification on the inapproximability of set cover

I'm trying to understand the inapproximability of the minimum set cover problem. The wikipedia page states that it is hard to approximate within a factor of $(1-o(1))\ln n$ and that $n$ refers to the ...
3
votes
1answer
27 views

Minimum number of transpositions

Let's have two permutations $A$ and $B$ of $n$ numbers. What is the minimal number $m$ of transpositions to transform $A$ to B in the worst case? After analysing some algorithms my guess is that $m \...
0
votes
1answer
57 views

Does the fact that there exists a polynomial time quantum algorithm for integer factorization suggest that integer factorization is in P?

Just as the title says: Does the fact that there exists a polynomial time quantum algorithm for integer factorization suggest that integer factorization is in P? Additionally, if one could show that a ...
0
votes
0answers
31 views

Why does my Genetic Algorithm not work for higher number of individuals?

I am using a cooperative coevolutionary genetic algorithm, the algorithm is given in A cooperative coevolutionary approach to function optimization by DeJong et. al. (1994), for optimizing a 62 ...
1
vote
0answers
23 views

Approximate Nearest Neighbour Problem in Spherical Setting

There has been significant literature in solving the (Approximate) Nearest Neighbour Problem in the spherical setting in the $\mathbb{R}^n$ using Angular and Spherical LSH and other lattice sieving ...
0
votes
0answers
12 views

Linear equation in n variables with non negative solution [migrated]

The problem is that given a positive integer y and n positive integers x1 , x2 , ... , xn does there exist non negative integers ...
0
votes
0answers
5 views

When a trained RNN is tested, is the number of time-steps same for every input?

I am a beginner in deep learning so bear with me. If I want to unfold the RNN in order to represent the relation of output to the input as a non-recursive functions I would have to know the number of ...
0
votes
2answers
38 views

Proving that a CFG generates a language [duplicate]

Is a suitable way to prove that any given CFG generates (or not) any given language to draw its total language tree? What if the tree is infinite? What would then be a better way to prove that a ...
1
vote
2answers
71 views

Estimating the complexity of an algorithm by looking at code

Time complexity seems rather a difficult notion for people who were not professionally trained in math or computer science. I understand it informally and can high-level compare which one is better ...

15 30 50 per page