Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.

Sign up to join this community
Anybody can ask a question
Anybody can answer
The best answers are voted up and rise to the top

Top Questions

3 votes
2 answers
1k views

Length of a regular expression

2 votes
1 answer
514 views

Is there an algorithm that in some cases is an improvement of BFS in the same way A* is an improvement of Dijkstra?

2 votes
3 answers
107 views

Find the smallest difference between two numbers in a DS in O(1) time

4 votes
1 answer
145 views

Is the set of languages satisfying the pumping lemma closed under concatenation?

2 votes
2 answers
78 views

Are reversed reverse preorder traversals equivalent to a postorder traversal?

0 votes
3 answers
72 views

How is pipelining possible?

2 votes
1 answer
114 views

Disprove: if L is decidable then Prefix(L) is decidable

1 vote
1 answer
79 views

How to find parameter sets for a big-O expression to be fixed-parameter tractable?

3 votes
1 answer
65 views

Allocating m rooms of varying capacity to n booking requests of varying sizes

1 vote
1 answer
59 views

How to convert AFA to ε-NFA / NFA / DFA?

1 vote
2 answers
45 views

Why is $A_{TM}$ not mapping reducible to $E_{TM}$?

0 votes
1 answer
74 views

I think I have discovered a new sorting algorithm using binary search tree [closed]

0 votes
1 answer
73 views

Finding a Hamiltonian Cycle in a directed graph - graph problem

0 votes
1 answer
72 views

Is there a hash-map implementation optimized to favor key lookups based on frequency (if key is referenced the most then it is searched first)?

0 votes
1 answer
56 views

Why is there a 'true' statement as precondition in the following loop invariant

0 votes
1 answer
56 views

Does a constant time compression algorithm proves that P=NP?

0 votes
1 answer
64 views

Dynamic routing algorithm

1 vote
2 answers
49 views

Pushdown automaton that accepts $a^{2k} b^{3k}$, without multiple pop

2 votes
1 answer
62 views

prove that if L is context-free then L' = {w2#w1 | w1#w2∈L} is context-free

0 votes
2 answers
47 views

A little confusion with Big Theta time complexity

1 vote
1 answer
41 views

Algorithm to calculate lower incomplete gamma function

0 votes
1 answer
39 views

Walk from vertex u to vertex v on complete graph, formula for number of walks of length k

1 vote
1 answer
38 views

How many different boolean functions exist up to permutation of its $n$ variables

1 vote
2 answers
48 views

Since there is no such thing as infinite memory, can we say that all pushdown automata and Turing machines are actually very big DFA?

2 votes
1 answer
37 views

Find a context-free grammar for uc^nd^nv where the number of a's and b's in uv are equal

0 votes
1 answer
46 views

Cosine distance in a space, and cheating?

1 vote
1 answer
25 views

Can Boolean circuits of polylog depth represent all Boolean functions?

0 votes
0 answers
50 views

Binary compression algorithm with decompress by index

1 vote
1 answer
38 views

Is finding the union of all minimum hitting sets NP-hard?

1 vote
2 answers
38 views

Formal mathematical resolution for Recurrence Relations

0 votes
1 answer
48 views

Find $k$ shortest paths in linear time

1 vote
1 answer
27 views

Find the largest subset of unpaired elements [duplicate]

1 vote
0 answers
43 views

$\epsilon$-Testing the property of subsequence non-existence

1 vote
1 answer
33 views

Time Complexity of ${n \choose k}$

1 vote
1 answer
25 views

If predicate P is partially-decidable, is ¬P decidable, partially decidable or undecidable?

0 votes
0 answers
40 views

What can be the topic of my assignment for presentation about overall computing performance?

-3 votes
0 answers
33 views

The Language of All Palindromes - Is it CFL?

0 votes
0 answers
31 views

Undirected unweighted sub-graph enumeration with threshold on node value

1 vote
0 answers
30 views

Split Bipartite Graph

-1 votes
0 answers
30 views

Flow in Ford-Fulkerson algorithm

0 votes
0 answers
29 views

Find a set K of k vertices in a graph such that the distance between any vertex to the closest vertex in K is minimized

-3 votes
0 answers
29 views

Fixed parameter tractability Big O

1 vote
1 answer
22 views

Why do we use {+1, -1} in place of {0, 1} for the Fourier analysis of boolean functions?

1 vote
1 answer
17 views

Efficient search of a large set of documents to find documents that only contain a particular set of words

0 votes
1 answer
28 views

The average time complexity of linear search with weighted probability

-3 votes
0 answers
27 views

Its about automata [closed]

2 votes
0 answers
27 views

Universal register machine that recognizes the image of a partial function

2 votes
0 answers
27 views

$y$-Fast Tries: Why not partition into groups of $\Theta(\log^2 M)$ elements?


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