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
Computer Science

Top Questions

Ask Question
Active 1 Bountied Hot Week Month
5 votes
3 answers
4k views

Is there a faster than O(n^2) way to compute a vector of length n from another vector and an n by n matrix?

Peter Cordes
  • 831
9 votes
4 answers
1k views

Non-regular language whose prefix language is regular but not the whole set of words

John L.
  • 35.5k
11 votes
3 answers
2k views

Is Big-Theta a more accurate description of worst case run time than Big-O?

gnasher729
  • 25.9k
5 votes
2 answers
1k views

Why does the order of the nested loops matter when solving the Coin Change problem?

John L.
  • 35.5k
3 votes
3 answers
729 views

A solution with O(n) time complexity is always slower than a solution with O(nlog(n)) time complexity even though they have the same space complexity

Yves Daoust
  • 5,283
1 vote
7 answers
171 views

How to design a faster sort algorithm? Is there sort of meta-algoritm for it? Or we do not understand how better sort algorithms were discovered?

Michel
  • 313
0 votes
2 answers
183 views

Combining fork() and algorithms

Cort Ammon
  • 3,150
2 votes
2 answers
281 views

Fast identification of prime power factors?

D.W.♦
  • 145k
0 votes
1 answer
195 views

Are these functions computable?

Noah Schweber
  • 2,487
0 votes
2 answers
88 views

is it possible to compress a sequence of progressive unique numbers dramatically?

D.W.♦
  • 145k
-3 votes
1 answer
305 views

Can we solve the halting problem if we allow TM to print it's output and go into a loop?

raoof
  • 95
0 votes
2 answers
85 views

time complexity of sorting binary natural numbers

Mathew
  • 189
4 votes
1 answer
83 views

Optimal algorithmic complexity of "a nonrepetitive stack"?

John L.
  • 35.5k
0 votes
3 answers
74 views

Can we create a decision tree for any comparison sorting algorithm even if it is very complicated?

Yves Daoust
  • 5,283
0 votes
3 answers
74 views

Trading time for work; does this concurrency phenomenon have a name?

reinierpost
  • 4,726
2 votes
1 answer
102 views

Dijkstra as a greedy algorithm

John L.
  • 35.5k
1 vote
2 answers
89 views

Does the even-odd rule ever have false positives for deciding a point in a complex polygon?

John L.
  • 35.5k
0 votes
2 answers
50 views

Is assembly macros part of operative system / kernel, or lower down and more seen as hardware?

BipedalJoe
  • 101
2 votes
1 answer
49 views

What is the (intuitive) relation of NP-hard and #P-complete problems?

Yuval Filmus
  • 271k
1 vote
1 answer
78 views

Is it true that everything is a side effect in C?

George Glebov
  • 11
1 vote
2 answers
93 views

How can we prove that "extract almost minimum" operation in a priority queue cannot be done in o(log n)?

John L.
  • 35.5k
1 vote
2 answers
52 views

Asymptotics of $F(n) = n \times n^{\log_32}$

Yves Daoust
  • 5,283
0 votes
1 answer
108 views

Potential Method For Decimal Counter

Steven
  • 24.5k
0 votes
2 answers
49 views

Why executables aren't written in a way that the OS understand instead of machine code?

Yves Daoust
  • 5,283
0 votes
2 answers
60 views

What is good algorithm to decode morse code strings?

Ray Butterworth
  • 156
2 votes
1 answer
59 views

Find a key in a BBST for which sum of values of keys smaller then it - is maximal

Nathaniel
  • 7,568
0 votes
1 answer
59 views

How to convert the regular expression $\emptyset^*$ to an NFA?

Steven
  • 24.5k
1 vote
2 answers
58 views

does finite automate have memory?

user253751
  • 1,268
1 vote
1 answer
57 views

Why not $O(n^{\log_ba})$ for case 1 of the Master Theorem instead of $O(n^{(\log_ba) - \epsilon})$?

John L.
  • 35.5k
1 vote
1 answer
34 views

Complexity of multiplying bivariate polynomials of degree n

D.W.♦
  • 145k
1 vote
2 answers
56 views

How does the SMT solver Z3 handle conditional statements in a constraint?

MvB
  • 33
1 vote
2 answers
43 views

What is this definition of orthogonality in programming language trying to convey?

Steve
  • 329
0 votes
2 answers
43 views

Estimate which components to replace, to not only save electric energy but also improve the computer's performance

D.W.♦
  • 145k
1 vote
1 answer
69 views

Show that $TIME(\sqrt{n})$ = $TIME(1)$

Yuval Filmus
  • 271k
0 votes
1 answer
53 views

Is my DFA optimal?

Hendrik Jan
  • 28.2k
3 votes
1 answer
52 views

Counting integers $n \leq x$ with a given prime signature

D.W.♦
  • 145k
0 votes
1 answer
51 views

Can an algorithm decide whether any DFA accepts an infinite language? What is its time complexity?

Steven
  • 24.5k
0 votes
1 answer
63 views

How does instruction set architecture affects clock rate?

Paul A. Clayton
  • 2,948
3 votes
0 answers
76 views

Approximation algorithm for minimising $x_i+y_i$ for monotonically increasing sequence $x_i$ and monotonically decreasing sequence $y_i$ [closed]

AspiringMat
  • 533
1 vote
2 answers
46 views

Search for largest element in 1st monotonic subarray with an array consisting of 3 monotonic subarrays

greybeard
  • 915
-2 votes
2 answers
58 views

How to check if an positive integer can be represented as a sum of integers

Yves Daoust
  • 5,283
0 votes
1 answer
57 views

Set of Turing machines that accepts at least one input in bounded time

D.W.♦
  • 145k
1 vote
2 answers
57 views

Algorithm to find if there exists an assignment such that all equality and inequality constraints are satisfied

Tassle
  • 2,229
1 vote
1 answer
44 views

Does this DFA prove closure under Perfect Shuffle?

Hendrik Jan
  • 28.2k
2 votes
1 answer
44 views

Storing game traces (e.g. Chess, Othello) in a minimal number of bits

Yves Daoust
  • 5,283
0 votes
0 answers
71 views

Search for complete bipartite subgraph of graph

D.W.♦
  • 145k
-2 votes
0 answers
69 views

Looking for a book for learning about circuits & arithmetization

user93353
  • 69

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

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.