All Questions
48,499
questions
19
votes
1
answer
438
views
Is there an O(n log n) algorithm for 4D line simplification?
The Ramer-Douglas-Peucker algorithm for line simplification has worst-case $O(n^2)$ runtime. For suitably distributed random inputs, it has expected $O(n \log n)$ runtime complexity. In 2D, there are ...
- 5,390
17
votes
1
answer
987
views
The number of different regular languages
Given an alphabet $\Sigma = \{ a,b \}$, how many different regular languages are there that can be accepted by an $n$-state non-deterministic finite automaton?
As an example, let us consider $n=3$. ...
- 1,901
-1
votes
1
answer
13k
views
Can someone show me step-by-step how to calculate the primitive operations of this algorithm?
See the example algorithm below from my course notes, I don't follow the operation counting in the inner loop. Can someone walk me through this step-by-step?
Here's the algorithm:
...
- 109
-1
votes
3
answers
280
views
Computer Science - System Security : How to Prove that KISS principle is Implemented in Security? [closed]
I basically have this homework question that needs me to support the below statement.
Any suggestions on how i could go around proving it ?
the Exact Question was :
"The KISS principle is ...
- 19
1
vote
1
answer
216
views
why recursive languages does not come under Chomsky hierarchy? [duplicate]
why recursive languages does not come under Chomsky hierarchy ? why Chomsky did not classified
it? any real life resemblance of recursive language something that i can connect it with like regular ...
2
votes
1
answer
714
views
Best algorithm for correlation between time series?
I have some biological data (ECG), which are quite chaotic in nature, and and some other data; that are not chaotic but related in some way, like fatigue. I want to find out how the time series, ...
- 121
5
votes
1
answer
2k
views
Complexity of bitwise AND operation on bit string regular expressions
Given two regular expressions of bit strings $B_1$ and $B_2$ of the same length (stated mathematically, $B_1,B_2 \in \{0,1\}^m$) that use only grouping and repetition, what is the optimal running time ...
- 51
11
votes
2
answers
717
views
Is the reversal of a minimal DFA also minimal?
The question is pretty much in the title. Is there ever a time where some language $L$ can be accepted by a minimal DFA with $n$ states, but $L^R$, the reversal of $L$, can be accepted by a DFA with $...
- 29.8k
4
votes
2
answers
378
views
Minimizing Cost by minimizing delay
There is a complete binary tree with its leaves as components of some system
The values from one node to another gives propagation time for a signal to propagate from one junction to another
For the ...
- 43
2
votes
1
answer
76
views
Filing systems using index blocks
I know that a disadvantage of the index block system is that it can be wasteful of space if the files involved are mostly small in size, as index blocks are allocated from free space as required and ...
- 143
2
votes
1
answer
222
views
Why do servers use ECC memory? [closed]
I understand that ECC checks for errors and corrects them automatically without the knowledge of the operating system or user. I don't understand however why servers often use ECC memory?
- 143
0
votes
1
answer
3k
views
Help with a dynamic programming solution to a pipe cutting problem
I'm trying to complete a problem where I have to design and implement a dynamic programming solution to the following problem
You have to cut a metal pipe into several pieces. To do so, you bring ...
- 235
0
votes
0
answers
170
views
Coq: default values for vectors
Let's say there is a vector of length $n$:
Require Import Vector.
Variable T:Type.
Variable n:nat.
Variable v:t T n.
"list" gives a function "nth" that demands a ...
- 101
-3
votes
1
answer
399
views
Automata Theory Questions: Rule Trees, Context-Free Grammar, Proving Ambiguity [closed]
I'm currently taking a class in Automata Theory and it's kicking my butt. I have an assignment that my teacher gave me that consists of three questions. I have no idea where to start. My teacher and I ...
- 5
9
votes
1
answer
11k
views
NFAs with more than one initial state
I'm trying to give a meaningful definition for NFAs with more than one initial state. I know from the formal definition in Wikipedia that it is possible to have more than one initial state, it ...
- 143
4
votes
1
answer
437
views
Building Simple Parse Trees
I am trying to learn how to build parse trees.
I have watched videos and tried to do some on my own, but am a little lost.
In this example, I am given the following:
$$
\begin{align*}
&S\to(L) ...
- 41
3
votes
3
answers
4k
views
Can't understand why the DP Subset Sum algorithm is not polynomial
I can not understand why the dynamic programming algorithm for the Subset Sum, is not polynomial.
Even though the sum to find 'T' is greater than the total sum of the 'n' elements of the set , the ...
- 397
1
vote
1
answer
91
views
How can an LBA check legality of TM transitions without extra memory?
In Sipser's book there is a proof that an emptiness of LBA is undecidable, with the help of reduction to A_$_{\text{TM}}$.
The reduction is proposed in the following manner:
we receive a TM $M$ and a ...
- 175
-1
votes
1
answer
121
views
NP hardness of Partition
I'm trying to show that PARTITION is NP-hard. I'm not sure if what I have is correct so I'll write what I have. I tried to reduce it from SUBSET_SUM:
$$PART= \{S\subset\mathbb{Z}|\exists C \subset S: ...
- 339
2
votes
1
answer
252
views
Is polynomial time reducibility reversible?
If a language $A$ is reducible to some language $B$, does it follow that $B$ is reducible to $A$?
My guess is no, it having something to do with the function $f$ in the definition of $A$ reducing to $...
- 269
11
votes
3
answers
2k
views
Algorithm to match numbers with minimum number of moves
This is a sort of edit-distance question, and is very easy. I am just quite brain dead on this subject and can't figure it out so far.
Given a series of numbers, e.g.
...
- 337
2
votes
2
answers
2k
views
Minimising height of a 2-3-4 tree
I'm wondering how a set of keys could be assigned to nodes in a 2-3-4 tree in order to minimize the height of the tree?
Does the sequence of insertion matter with 2-3-4 trees?
- 143
1
vote
1
answer
552
views
Show that the running time of the build_heap function is $O(n)$
Given the following two functions, prove that the build_heap function, which transforms an array A into a max-heap-sorted array A' runs in $O(n)$.
...
- 135
1
vote
1
answer
86
views
Mutual Information in a Binary Erasure Channel
Imagine a Binary Erasure Channel as depicted on Wikipedia.
One equation describing the mutual information is:
$$
\begin{align*}I(x;y)
&= H(x) - H(x|y) \\
&= H(x) - p(y=0) \cdot 0 - p(y=?) ...
- 13
0
votes
1
answer
495
views
NP Completeness of 3-SAT problem [closed]
I have started reading on algorithmic complexity for my thesis work. Already have studied on Polynomial time reducibility, NP-Complete, NP-Hard. Now trying to prove NP completeness of some of the ...
- 19
10
votes
1
answer
4k
views
Why does introsort use heapsort rather than mergesort?
As part of a homework assignment covering implementation of introsort I'm asked why heapsort is used rather than mergesort (or other $O(n\log(n))$ algorithms for that matter).
Introsort is a ...
- 211
2
votes
1
answer
722
views
Iterated logarithm $\log^* n$
I am to come up with a function based on these premise:
Give an example of a function which is $o(\log^k n)$ for any fixed $k$, but which is also $\omega(1)$.
The answer is the iterative logarithm $\...
- 21
4
votes
1
answer
8k
views
Can you recognize or decide if a Turing Machine has an infinite sized language?
That is, can you build a Turing Machine that, if given a Turing Machine as input, can decide (or at least recognize) if the inputted Turing Machine has an infinite number of strings in its language?
...
- 141
5
votes
5
answers
2k
views
Optimal Algorithm for checking if a number is a multiple of three
I'm just starting a course on Computational Number Theory and have very little Computer Science background but definitely know enough about the big-O notation.
I currently have an assignment to work ...
- 247
1
vote
0
answers
174
views
Maximum memory accessible by the CPU [closed]
I've read multiple times (for example in some of the answers to this question https://stackoverflow.com/questions/8869563/how-much-memory-can-be-accessed-by-a-32-bit-machine) that a CPU with 32 bit ...
- 111
-1
votes
1
answer
176
views
Find a maximal subgraph on a tree with conditions
Given a tree, find a path on which every vertex has at most 4 leaves (can have 0 as well) and is the "biggest" (has the maximum amount of vertices possible - including the leaves).
Time complexity: $O(...
- 279
3
votes
0
answers
133
views
Prove or disprove that every $L$ in this class is a CFL iff $L$ is equivalent to a substitution
Let $L$ be a language with every string of the form $(w_i\#)^*$ with $w_i\in\{0,1\}^*$. Set $w'\sim w$ if there is a permutation $\pi_1$ such that $w_i=w'_{\pi_1(i)}$ for all $i$. If additionally $\...
- 630
4
votes
1
answer
465
views
How to perform local search on simple paths?
I have a local search problem.
The set of valid solutions are all the simple paths (i.e. without repeated nodes) from a node $S$ to a node $T$ in a directed graph.
The question is: given a current ...
- 75
1
vote
1
answer
73
views
Need of reducing problems if we already know that a problem is undecidable
In the Reducibility chapter of Sipser's Theory of Computation book, an example is:
We reduce A(TM) to HALT(TM). And then we claim that if H decides HALT(TM), then A decides A(TM), but since A(TM) is ...
4
votes
1
answer
58
views
Should we not reuse constants in tableaux proofs?
I am trying to understand the proof of the following using tableaux:
$$
\exists x\forall y.r(x,y) \to \forall x \exists y . r(x,y)
$$
This is how it works out:
$$
(1) \space \exists x \forall y .r(x,...
- 41
24
votes
3
answers
4k
views
Are all pseudo-random number generators ultimately periodic?
Are all pseudo-random number generators ultimately periodic? Or are they periodic at all in the end?
By periodic I mean that, like rational numbers, they in the end generate a periodic subsequence...
...
- 1,624
1
vote
1
answer
419
views
Reducibility in Computability Theory
In Sipser's book of Theory of Computation, related to Reducibility, it's written
if A is undecidable and reducible to B, B is undecidable.
The confusion is, only a solution to B determines a ...
1
vote
2
answers
76
views
Recurrence doesn't add up [duplicate]
I made a recurrence tree and guessed that solution to $T(n)=2T(n-2)+n$ is $O(2^{n/2})$ and I am now trying to prove this through substitution. These are my steps so far, but I can't get it to pass for ...
- 121
2
votes
2
answers
2k
views
Is $a^n b^m$ never regular if n and m have some relation between them?
I know what regular and context free language are and how regular language needs finite memory and other stuff.
What concerns me is that I think if $a^nb^m$ such that $n$ and $m$ have some relation ...
3
votes
1
answer
2k
views
What is the standard way to choose a new leader in Multi-Paxos?
If you are unfamiliar with multi-Paxos or paxos, the following link might be a good refresher on it:
http://amberonrails.com/paxosmulti-paxos-algorithm/
or the paper by Leslie Lamport:
http://...
- 3,040
7
votes
1
answer
744
views
Relationship between graph expansion and conductance
I'm quite confused about the exact relationship between the expansion of a graph and its conductance. My first question is:
Could someone point me to a reference that discusses both of these notions? ...
- 73
10
votes
2
answers
516
views
Is there a canonical definition of “pure” function?
StackOverflow pointed me here, so the question might be a bit in a layman's terms.
Wikipedia defines pure functions as
In computer programming, a function may be described as a pure
function if ...
- 203
0
votes
3
answers
254
views
Bipartite Matching in the Plane
I'm currently working on a problem that I came across:
You are given a set $B$ of $n$ points in the plane, and a set $R$ of $n$ points in the plane. Each point is given by its coordinates. I have ...
- 17
13
votes
1
answer
3k
views
Which NP-Complete problem has the fastest known algorithm?
In terms of worst-case asymptotic runtime, which NP-complete problem has the fastest-known (exact) algorithm and what is the algorithm? Is there something known that is faster than $O(n^2*2^n)$?
3
votes
1
answer
2k
views
Why is the set of NFA that accept all words in co-NPSPACE?
In Sipser's book there is a section describing how to decide
$\qquad\displaystyle \mathrm{ALL}_\mathrm{NFA} = \{ \langle N \rangle \mid N \text{ is an NFA}, L(N) = \Sigma^*\}$
in polynomial space. ...
- 133
0
votes
1
answer
167
views
How to cluster a large movie dataset ??
I have to cluster a movie dataset of 10000 movies. A movie has attributes like Genres, Actors, Directors, Year. Earlier I thought that we can use a simple clustering algorithm like k-medoids and the ...
- 101
0
votes
2
answers
95
views
solving recurrence by substitution, calculations doesnt add up
I have this recurrence $p(n) = 2p(n-2) + n$, and I have guessed that the solution is $O(n^2)$, however, when I do the following calculations, I cannot get the inequality to hold
$p(n-2) \leq c(n-2)^2$...
- 9
4
votes
1
answer
155
views
Placing 1d items in a 2d grid with constraints
I'M looking for an algorithm (preferably polynomial) for the following problem:
Input:
- an M x N grid, where each square can be either empty or occupied
- a list of items
- a list of constraints
...
- 141
2
votes
1
answer
1k
views
Is there C++ code that takes infinite time to compile?
Is C++ as a formal language recursively enumerable? If yes, is there any invalid C++ code that takes "infinite" time to compile?
- 455
-2
votes
1
answer
723
views
MIS algorithm for Tree in O(log* n) time
I know Distributed Graph Coloring algorithm in O(log* n)
which is given at P11: Vertex Coloring
Same for Maximal Independent Set [MIS] they gave remark like algorithms exist in O(log* n) time at P70: ...
user9665