user avatar
user avatar
user avatar
nir shahar
  • Member for 2 years, 2 months
  • Last seen this week
39 votes
Accepted

Time complexity $O(m+n)$ Vs $O(n)$

39 votes

Example of a graph with negative weighed edges in which Dijkstra's algorithm does work

29 votes
Accepted

How can a Turing machine compare two strings without modifying them?

13 votes

Is an integer variable constant or logarithmic space?

10 votes
Accepted

Algorithm to get any spanning tree not necessarily a minimum spanning tree

10 votes

Is there any NP-hard problem which was proven to be solved in polynomial time or at least close to polynomial time?

9 votes

How can a Turing machine compare two strings without modifying them?

8 votes
Accepted

Is discrete math enough for computer science ? Or there other Math topics that I should also learn With it?

7 votes
Accepted

What is this algorithm computing and how to prove it?

6 votes
Accepted

What algorithm do SVMs use to minimize their objective function?

5 votes
Accepted

How do computers *really* work? (at the most basic level)

5 votes
Accepted

Polynomial time optimization problems belong to which complexity class?

5 votes

Why are all regular languages in P?

5 votes
Accepted

An integer (a string of digits) is $\text{/[0-9][0-9]$\ast$/}$. (Why isn't it just $\text{/[0-9]$\ast$/}$?)

5 votes

tautology vs satisfiability

5 votes
Accepted

Why can't I use a polynomial-time reduction for proving P-completeness?

4 votes
Accepted

Can there be a computer without software (only hardware)?

4 votes

All possible sum of each array combination

4 votes
Accepted

What is the relation between Topological Sort and Strongly Connected Components?

4 votes
Accepted

Sharing a requested secret number not knowing which

4 votes

Given x find a polynomial such that pol(x)=a for a known a?

4 votes

Can a non deterministic finite automaton go into infinite loop?

4 votes

Should the certificate for NPSPACE be polynomial in size?

4 votes
Accepted

Is $\frac{n}{\log n} \log \frac{n}{\log n} = O(n)$?

4 votes
Accepted

Measuring the length of a "loop" in a linked list in $O(n)$ Time?

4 votes

Set theory pertaining to category theory and functional programming

4 votes

Proving that $X\to aX|Y$, $Y \to Yab|b$ is unambiguous

4 votes

How do I calculate the time complexity of this memoized algorithm?

4 votes

Algorithm for ensuring that each element ends up in its specified range when composing a list

4 votes
Accepted

Modified shortest path problem

1
2 3 4 5
17