Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Top Questions

12 votes
3 answers
2k views

Why are search problems assumed to have the structure of "find a path in a graph"?

5 votes
1 answer
705 views

What don't I understand in topological sort using DFS?

1 vote
1 answer
364 views

If coNP ⊆ NP, does that mean coNP = NP?

4 votes
2 answers
1k views

Global optimization of state assignments in a directed graph with a tree-based distance cost

5 votes
1 answer
200 views

Is TQBF in CNF is still PSPACE-complete

4 votes
2 answers
120 views

pumping lemma, concatenation of non-regular languages $a \neq b$

4 votes
1 answer
268 views

Do multi-acceptance/multi-language automata exist in literature?

3 votes
2 answers
73 views

How to Determining the Big O Complexity of a Recursive Function?

3 votes
1 answer
196 views

How to find a binary vector with minimized distance with a vector set?

1 vote
1 answer
174 views

How to solve a system of XOR equations in a cyclic graph?

1 vote
1 answer
128 views

Finding the smallest root

1 vote
1 answer
114 views

Why is the number of array accesses not considered in analyzing the complexity of mergesort?

2 votes
1 answer
128 views

Efficiently transforming non-recursive CFG into an NFA

2 votes
1 answer
121 views

Can CTL* express every model's behaviour

1 vote
1 answer
154 views

Why regular languages closed under this operation?

1 vote
2 answers
92 views

Proof that HALF-3SAT is in P

2 votes
1 answer
60 views

Minimum number of intervals from a set to cover all intervals of another set

0 votes
2 answers
67 views

Lossless compression collision such as 2 different files gives the same zip file after compression

-2 votes
2 answers
51 views

Precise definition of a brute force algorithm

2 votes
1 answer
91 views

Find best path in an alternating graph

0 votes
2 answers
40 views

Floating point operations in a zero padded Strassen multiplication

0 votes
2 answers
51 views

Why is ROM read only? And why do SSDs use it?

7 votes
1 answer
84 views

Is it decidable if $\text{MIN}(L(G))$ and $\text{MAX}(L(G))$ is context-free for a context-free grammar $G$?

1 vote
1 answer
93 views

Number of unique paths in a grid

0 votes
4 answers
71 views

Proof that the mind/brain is not a finite state machine by recognizing an unrecognizable language?

1 vote
1 answer
55 views

How many lower-case 6 letter words can I write so that every pair has exactly two matching letters?

0 votes
2 answers
41 views

(novice to compiler design) how does a recursive descent parser decide which nonterminal to parse if there are multiple

2 votes
1 answer
52 views

Number of graphs that almost contain a $k$-clique

1 vote
1 answer
65 views

Solving recurrence relation $T(n) = \max\{T(k)+T(n−k)+O(\min\{k, n-k\})\}$

2 votes
1 answer
30 views

Decidability of whether for a given $G$, $L(G)=\Sigma^+$? (or $L(G)=L$ where $L$ is fixed beforehand

0 votes
1 answer
80 views

Can this Binary Search Tree be optimal with $x$ expected comparisons?

-1 votes
1 answer
47 views

Finding negative cycles using the Bellman-Ford algorithm and a source node

1 vote
1 answer
47 views

How to prove a function is a bijection (name mangling)?

0 votes
1 answer
28 views

Why is the Time Complexity of DFS Algorithm O(|V| + |E|) instead of O(|E|)?

1 vote
1 answer
45 views

Efficient data structure for fast Insertions, lookups, and union operations on sets

1 vote
1 answer
45 views

Proving that the shortest simple path problem between two vertices 𝑠 and 𝑡 in a graph with given path upperbound be positive is NP-complete

0 votes
1 answer
71 views

A specific class of languages

0 votes
0 answers
89 views

Turing Machine transition table for checking a palindrome

0 votes
1 answer
42 views

What exactly is a lattice?

1 vote
1 answer
52 views

fast CRC computation

1 vote
2 answers
50 views

Is there a linear programming method that is polynomial in the number of variables, constraints and bitlength of numbers?

1 vote
1 answer
60 views

Trying to understand better the solution for $L \ regular \to L'=\left \{ xy^{R}z : xyz\in L\ , x,y,z\in\Sigma^{*} \right \} \ regular$

0 votes
2 answers
75 views

TOPS trillion operations per second to Tokens per second

2 votes
1 answer
73 views
+50

The existence of a (nearly) quadratic time algorithm for 2-steps shortest path or smallest triangle

0 votes
5 answers
44 views

Efficient data structure for multidimensional lookup

1 vote
2 answers
34 views

Understanding Time Complexity Calculation for Factorial and Exponential Algorithms

1 vote
1 answer
42 views

Graph Coloring Decision Problem Reduction to Prove NP-Complete

2 votes
1 answer
31 views

Equivalence between Reservoir Computing and Divination


Looking for more? Browse the complete list of questions, or popular tags. Help us answer unanswered questions.