All Questions

Filter by
Sorted by
Tagged with
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{...
user avatar
-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 ...
user avatar
  • 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)?
user avatar
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-...
user avatar
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, ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 $...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 &...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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$,...
user avatar
  • 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 \...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
-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. ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ''...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
-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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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. ...
user avatar
  • 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 ...
user avatar
0 votes
1 answer
38 views

A* pseudocode problem

What is the difference between this two pseudocode and which one should i implement? ...
user avatar
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 ) ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
-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 ...
user avatar
  • 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 ...
user avatar
-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 ?
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 113

15 30 50 per page