Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

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

6 votes
8 answers
3k views

Advantages of linked lists over arrays?

9 votes
1 answer
2k views

Why rectangle packing is NP-hard but maybe not in NP?

10 votes
1 answer
2k views

Would it make sense to use an array of linked lists for a Priority Queue, given a fixed number of priorities?

3 votes
2 answers
1k views

Length of a regular expression

3 votes
2 answers
771 views

Determining if an NFA accepts an infinite language in polynomial time

3 votes
2 answers
1k views

Is this language a context-free language or not?

8 votes
1 answer
690 views

Conjecture: a half of a pairing context-free language must be a regular language

2 votes
2 answers
607 views

An α-good tree with n nodes has height O(log n)

3 votes
2 answers
280 views

Number of Inversions found in Selection sort vs Exchange sort

4 votes
2 answers
449 views

Spanning tree - minimum difference between smallest and largest weight

3 votes
1 answer
853 views

How does the 'proof' of the Cook-Levin theorem, actually prove the Cook-Levin theorem?

2 votes
2 answers
515 views

How can I apply binary search to find two adjacent increasing elements in an unsorted array?

3 votes
2 answers
288 views

Find an upper bound for T(n) = T(n/2) + T(n/2 + 1) using the Substitution Method base case fails

1 vote
3 answers
343 views

Finding a DFA for concatenation

4 votes
2 answers
204 views

Similarities and differences between Unit and Bottom types?

2 votes
1 answer
522 views

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

5 votes
3 answers
90 views

If $L$ is regular then so is $\{y \mid \exists x \, xyx \in L\}$

2 votes
2 answers
312 views

Graph Injective-Homomorphism Problem

0 votes
2 answers
177 views

How do we check $x ≠ y$ in $PDA$ for $L = \{xy | x, y \in (0 + 1)^*, |x| = |y|, x ≠ y\}?$

0 votes
1 answer
274 views

Sets of problems in different models of computation and cardinality

2 votes
4 answers
242 views

What exactly is pumping length in pumping lemma?

5 votes
1 answer
161 views

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

1 vote
2 answers
152 views

Clarification regarding linear boolean functions!

3 votes
2 answers
91 views

what are all the domains of computer sciences?

1 vote
4 answers
71 views

Why is $a^{\log_b n}$ the same as $n^{\log_b a}$?

-1 votes
2 answers
241 views

Maximum difference between maximum and minimum frequency in a subarray

2 votes
3 answers
113 views

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

0 votes
2 answers
144 views

Finding Median value given a tuple (value, frequency) in O(n) worst case time complexity

1 vote
1 answer
171 views

Undecidability in optimal data compression

1 vote
2 answers
158 views

Problem size and how it's different than the input for an algorithm

1 vote
1 answer
155 views

Proof that 2-sat is P-hard?

3 votes
1 answer
190 views

Shannon's result that some Boolean functions require exponential circuits

1 vote
2 answers
54 views

Find largest set of players that never played against eachother

2 votes
2 answers
83 views

Are reversed reverse preorder traversals equivalent to a postorder traversal?

1 vote
1 answer
213 views

Time complexity when taking certain elements and iterating over them?

3 votes
1 answer
180 views

Amortized analysis on a dynamic table that grows its size by $\sqrt{size} $

2 votes
2 answers
83 views

Exponential Time Hypothesis and the input size vs number of variables

2 votes
1 answer
136 views

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

2 votes
2 answers
62 views

What is the lower bound on retrieving an item in a collection if no arrays(Random access memory) are allowed?

0 votes
3 answers
78 views

How is pipelining possible?

2 votes
1 answer
118 views

Sorted list of counters in constant time

1 vote
1 answer
135 views

A small issue regarding the proof of Savitch's Theorem

1 vote
1 answer
133 views

Find a path with given weight and the minimum number of edges on a tree

2 votes
1 answer
214 views

Show all chains per user

3 votes
1 answer
46 views

Why can't $QBF$ be reduced to $SAT$

1 vote
1 answer
95 views

Proving transitivity in an intuitionistic type theory without the K rule

0 votes
2 answers
92 views

Maximum subarray sum of given length range

1 vote
1 answer
88 views

Language of Turing machines that go through some configuration infinitely many times on empty input


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