All Questions
44,851
questions
1
vote
2
answers
48
views
How to disambiguate CFG with unary/binary minus and binary prefix operator
I'm designing an expression language that's trying to (a) be maximally compatible with a different ambiguous language; and (b) be LR(1).
I'm facing the current fragment of the language:
$$
\begin{...
- 689
-2
votes
0
answers
36
views
What is algorithm fairness?
I am not getting the meaning of algorithm fairness. Consider the RAM model, quicksort, mergesort,all pair shortest algorithms they all are not biased as per my understanding.
Please provide a ...
- 11
-4
votes
1
answer
32
views
what will be the space complexity of the following?
if two vectors are used for ex,
vector<vector> temp;
vector temp2;
then what will be the space complexity, will it be O(n) or O(n^2)?
1
vote
1
answer
57
views
determining whether a context-free language is regular
I was wondering how to determine (with proof) whether the context-free language generated by the following context-free grammar $G$ is regular, where $S$ is the start variable and $a$, $b$ are the non-...
- 279
1
vote
1
answer
27
views
if $RA$ is context-free, is $A$ context-free?
If $RA$ is context-free for a regular language R, is $A$ context-free?
I think this statement is true. Let G be the CFG given by the rules $S_0\mapsto LA_1, S\mapsto LA_1, A_1\mapsto SA_2 | RS | 1, ...
- 279
0
votes
1
answer
18
views
Landau Notation/Big O notation
In our class the following exercises/examples were given:
Compute/find $n_0$ and c from the formal definition of each Landau symbol to show that:
$n^{2/3} \in \Omega(log^8(n))$.
Then in the Solution ...
- 173
0
votes
2
answers
55
views
Why is there a difference between the meaning of the word 'statement' in programming and linguistics?
In linguistics, the word 'statement' means something that is true or false, closer to a declarative sentence, but in programming, the meaning is closer to an imperative sentence.
What is the reason ...
- 13
0
votes
1
answer
23
views
P vs. NP problem and understanding "worst case complexity"
Suppose that $P \not= NP$. Then my understanding is not all instances of NP-complete problems can be solved in polynomial time. That is for every NP-complete problem, there are a colleciton of ...
- 237
0
votes
0
answers
29
views
How to prove reverse of DFA?
How does one formally prove that, given a DFA $M=\langle Q,T,\delta,q_0,F\rangle$, the following NFA $M^R = \langle Q_R, T, \delta_R, q_R, F_R\rangle$ recognizes the reverse of M's language?
We build $...
- 99
1
vote
0
answers
36
views
Are there any (theoretical-esque) computer science "competitions" at Undergrad level similar to Putnam?
I have searched for a bit eventually arriving at well known websites like codeforces, atcoder, codewars, codinggame or the various OJs.
They mostly involve solving tasks where usually the main focus ...
- 11
0
votes
0
answers
22
views
Good resources on polyhedral compilation
I'm looking for good introductory resources (books, articles, notes, websites, videos, e.t.c.) on polyhedral compilation. I'm especially interested in applications related to deep learning / GPU ...
- 101
0
votes
1
answer
22
views
Expected value of Markov chain after nth steps
A Markov chain $\{ X_n, n \geqslant 0\}$ with states 0, 1, 2 has the transition probability matrix $$P= \begin{bmatrix} \frac12 & \frac13 & \frac16 \\ 0 & \frac12 & \frac23 \\ \frac12 &...
- 143
2
votes
2
answers
118
views
Is there a working O(1)-space flood fill algorithm?
This is a purely theoretical question: among the known flood fill algorithms, there is one which does not require any dynamically-sized data structures, explicit or implicit: the so-called Walk-based ...
- 129
0
votes
1
answer
9
views
Checking for equality before calculating product of a matrix with inverse of another matrix
I have an operation that is performed many times and is thus performance sensitive where I need to calculate product of a matrix and inverse of a matrix as below. Both matrices are 4x4 and consist of ...
- 167
1
vote
1
answer
22
views
construct language in ${\sf BPP \backslash (RP \cup coRP)}$ assuming $\sf RP \neq ZPP$
Problem
This is a HW problem from CMU 15-455 (hw10, p1(a)), spring 17 by Ryan O'Donnell.
Assume $L \in {\sf RP \backslash ZPP}$. Define
$$ L' = \left\{ (x, y) : \text{either $x \in L$ and $y \notin L$,...
- 118
2
votes
0
answers
58
views
Playing with boxes: NP-hard? [Graph Theory]
You are playing with boxes on a $K_{1, n}$-$\textbf{subdivision}$ graph $G:=(V, E)$ whose number of vertices is odd, i.e., $|V| \equiv 1$ (mod $2$) with a given central point $C$ such that $\forall v \...
- 121
0
votes
0
answers
27
views
How should I imagine $M_w[\epsilon]\downarrow$ for the empty halting problem or $M_w[w]\downarrow$
I'm learning about computability problems e.g. reducing the general halting problem to the halting problem on a blank tape. But before I can understand this problem I first have to understand what ...
- 3
1
vote
1
answer
41
views
The relationship between a perfect binary tree and a complete & full binary tree
I am reading the book "Cracking the coding interview". In Chapter 4 they cover basic tree concepts.
It says there that a complete binary tree is a binary tree in which every level of the ...
- 111
0
votes
1
answer
25
views
Argument for an $\epsilon$ free LL(1) grammar being in LR(0)?
I am trying to understand the reason as given in this answer
If an ε-free grammar is not LR(0), then there is some state with both a shift and a reduce
action. Since the grammar is ε-free, that state ...
- 265
2
votes
1
answer
22
views
Fast algorithm for Graph Edit Distance to vertex-labeled Path Graph
Let $G$ be a vertex-labeled directed graph with unique labels $L$. Let $G_P$ be a path graph with the same vertex labels and the same number of vertices as $G$.
I know that in the general case ...
- 23
1
vote
1
answer
19
views
Finding articulation points
I have learnt about both articulation points and bridges and I have understood the algorithm used to find the number of bridges in O(n) time which is Tarjan's algorithm. But now, can I simply say that ...
- 127
0
votes
1
answer
29
views
prove that the unique language $A$ such that $AB$ is context free for all languages B is the empty set
Prove that the unique language $A\subseteq \Sigma^*$ such that $AB$ is context free for all languages $\subseteq \Sigma^*$ is the empty set.
If $A$ is not the empty set, there should be a way to ...
- 279
1
vote
1
answer
38
views
Is there a way to find the fixed size subsequence sum in an N by M array that is the closest to a given N-dimensional vector?
Basically, I need to solve the multivariate case of the "closest subsequence sum to a given value K" problem, which is solved with dynamic programming as far as I understand. Let's say I ...
- 13
-1
votes
0
answers
28
views
Please suggest an efficient algorithm to process around tenthousand orders per second for a financial system
Can you guys recommend me a fastest algorithm which can process more than ten thousand orders per second.The purpose of the algorithm is to process these orders and thus to update or save those data ...
- 99
0
votes
1
answer
35
views
Unpacking the notion of "hardest instances" for NP-complete problems
Suppose, for the sake of argument, that it was proved that $P \not= NP$. Then, this would imply that for every $NP$-complete problem, there is a "hardest instance" of the problem that ...
- 237
-1
votes
0
answers
21
views
Design a protocol that issues O(√n log n) many OR-queries and finds the indices of all √n many 1’s
Consider a Boolean string x ∈ {0, 1}^n
to which you have OR-query access:
You can send an oracle a subset S ⊆ [n], and the oracle will answer if there is any 1 in the
entries of x indexed by S or not. ...
- 1
1
vote
0
answers
47
views
Do all NP-Complete problems run in $O(c^n)$ time, as opposed to $O(c^{n^k})$?
According to the Wiki article on NP-Completeness, NP-Complete problems can be solved in $O(c^{n^k})$ time (I'll call this EXP-POLY time). However, shouldn't the bound on all their run times be the ...
- 453
1
vote
1
answer
30
views
How is slope error calculated for Bresenham’s Algorithm for both 2D and 3D?
I've been working with Bresenham’s Algorithm in 2D and understand it is derived from the following logic:
y = mx+c
To get the slope error at a given point, the following equation is used:
d2 is the ...
- 13
2
votes
0
answers
24
views
Balanced Assignment Problem with updatable cost
I have a problem that can be reduced to an assignment problem. (this is related to some cryptography problems)
Which means we have a set $A$ of $n$ agents and an equal size set $T$ of tasks as well as ...
- 21
0
votes
3
answers
69
views
Super-linear parallelism or speedup in parallel matrix multiplication algorithms
I'm reading this slides from a MIT course on parallel software performance. They introduced the concepts of Work $T_1$, Span $T_\infty$ and Parallelism (ratio $T_1/T_\infty$). What is called ''...
- 23
1
vote
0
answers
28
views
Bounding function for Travelling Salesman Problem
I have been studying the Branch and Bound paradigm. I came across an approach to solve the Travelling Salesman Problem using branch and bound where a specific kind of bounding function was used. I've ...
- 11
0
votes
0
answers
45
views
How to decide complexity affected by 'magic number'?
Suppose a language $L$ can be decided far more efficiently with a pre-computable (but expensive) 'magic number', then how should we classify the complexity of $L$?
For example, if we can only prove $L ...
- 118
-3
votes
0
answers
25
views
5-stage pipeline CPI
Assuming processor with 5-stage pipeline (Base CPI=1.0). Data hazards cause average penalty of 1 cycle for floating point operations. Int ops run at max throughput. Predict-branch-not-taken technique ...
- 1
-1
votes
0
answers
34
views
Why must all of the computer components indirectly get power from motherboard?
I understand that all of the components of the computer needs power to operate, and they get power from the motherboard.
Why must the computer components indirectly get power from the motherboard but ...
1
vote
2
answers
30
views
Can all non-quantum physical systems be efficiently simulated on a classical computer?
Is it true that simulating classical physical systems is in P, i.e. can be done efficiently on Turing machines or are there known exceptions? I'm thinking of chaotic systems but I'm also curious more ...
- 141
2
votes
0
answers
35
views
Belt-based mechanical computers
I've seen a lot of mechanical computers based on gears and rigid rods, but none so far that consequently use belts (not chains) for transmission of information.
Belts allow for easy negation (by ...
0
votes
1
answer
16
views
Difference between a stochastic environment and non-deterministic environment
I have been reading AIMA by Russell and Norvig, where they talk about different types of environments an agent may encounter. Here, they have described stochastic and non-deterministic environments ...
0
votes
0
answers
35
views
Use of break statement in this solution, and time complexity
Note: I had posted this question on Stack Overflow, and got a suggestion to post it to CS Stack Exchange.
The original question:
You are given a list A of N integers. Here, N is an even number. ...
- 1
0
votes
1
answer
42
views
Does order of elements in a set matter in Dijkstra's Algorithm?
When we use a set for doing Dijkstra's Algorithm, we use a pair of {distance,node} which we insert in a set. Most of the articles say that the first element of pair should be the distance , else we ...
0
votes
1
answer
38
views
A* pseudocode problem
What is the difference between this two pseudocode and which one should i implement?
...
0
votes
0
answers
33
views
How to refactor grammar to remove reduce/reduce conflict?
I have the following grammar with some examples of valid expressions:
foo
sum( foo )
...
- 101
0
votes
1
answer
114
views
Did I invent a new data structure?
I needed to implement a priority queue for a project I'm working on and had this idea. In a priority queue BST implementation wouldn't it be more efficient if the poll node pointed to its parent since ...
1
vote
1
answer
26
views
Are there any "fast" algorithms for defragmenting memory?
This is about memory, not files or filesystems.
So in a typical process, imagine you have a string "Hello world" that later gets changed to "Hello". Or a list of 100 objects later ...
- 129
1
vote
1
answer
23
views
Edit distance into a DCFL
I would like to generate helpful parser errors, telling the user how to fix their program.
Specifically I have a deterministic context-free language $L$, given in the form of an $LR(1)$ grammar. I ...
- 689
-1
votes
0
answers
24
views
Hungarian Assignment Algorithm Implementation - Why not work on this matrix? [duplicate]
I implemented the Hungarian algorithm according to this guide: 16:48
and there is one matrix that
The application I wrote does not bring a result,
Can you go through my code in Hungary algorithm ...
- 1
1
vote
2
answers
49
views
Existence of some search algorithms
The lowest time complexity of search algorithms for sorted lists is $$O(n)=logn$$.
The lowest time complexity of sorting algorithms is $$O(n) = nlogn$$
So in order to be able to use a search ...
- 119
-2
votes
0
answers
18
views
how to achieve the maximum height in red black trees?
As we know, the maximum height of a red black tree is 2* log (n+1).
So lets say we have six nodes [1,2,3,4,5,6].
How to insert them to achieve the maximum height ?
- 1
0
votes
2
answers
50
views
If A is reducible to B, assuming A is hard, why can't "B is easy" update our belief to A is easy?
The concept of reducibility in computability theory is very confusing for me.
For example, as described in Micheal Sipser's Introduction to the theory of computation, I understand that if language A ...
3
votes
0
answers
85
views
Do Knuth-Morris-Pratt and Booth’s LCS algorithm work in linear time on lists of strings? [migrated]
As a subroutine for an algorithm we’re working on, we need to compute the lexicographically minimal rotation (or least circular shift) of a list of strings.
The problem is well-known and several ...
1
vote
1
answer
30
views
Find the placement of gates on 2D points that minimizes the total distance of all paths to be made
Suppose we have a 6 vertices graph. We also have 6 gates. Each gate is attributed a path.
For example,
Gate 'A' will have to go to 'B'- 'C' - 'D' and 'E'
Gate 'B' will have to go to 'D'
Gate 'C' will ...
- 113