Computer Science
nir shahar
Profile Activity
Summary Answers Questions Tags Badges Bookmarks Bounties Reputation All actions

424 Answers

Votes Activity Newest
39
Example of a graph with negative weighed edges in which Dijkstra's algorithm does work
Aug 19 at 10:08
37
Time complexity $O(m+n)$ Vs $O(n)$
Apr 22 at 20:03
28
How can a Turing machine compare two strings without modifying them?
Aug 9 at 7:40
13
Is an integer variable constant or logarithmic space?
Apr 18 at 19:43
10
Is there any NP-hard problem which was proven to be solved in polynomial time or at least close to polynomial time?
May 3 at 10:49
10
Algorithm to get any spanning tree not necessarily a minimum spanning tree
Apr 5 at 14:03
9
How can a Turing machine compare two strings without modifying them?
Aug 10 at 12:12
8
Is discrete math enough for computer science ? Or there other Math topics that I should also learn With it?
Mar 1 at 14:21
7
What is this algorithm computing and how to prove it?
Jul 26 at 12:16
6
What algorithm do SVMs use to minimize their objective function?
Feb 22 at 15:35
5
tautology vs satisfiability
Jul 21 at 14:17
5
An integer (a string of digits) is $\text{/[0-9][0-9]$\ast$/}$. (Why isn't it just $\text{/[0-9]$\ast$/}$?)
Jun 22 at 11:42
5
Why are all regular languages in P?
Jun 9 at 17:03
5
Polynomial time optimization problems belong to which complexity class?
May 2 at 19:44
5
How do computers *really* work? (at the most basic level)
Feb 26 at 22:36
4
Can a non deterministic finite automaton go into infinite loop?
Sep 2 at 7:48
4
Sharing a requested secret number not knowing which
Jul 25 at 12:55
4
Given x find a polynomial such that pol(x)=a for a known a?
Jul 3 at 15:14
4
Should the certificate for NPSPACE be polynomial in size?
Jun 17 at 7:21
4
Set theory pertaining to category theory and functional programming
May 14 at 14:46
4
Measuring the length of a "loop" in a linked list in $O(n)$ Time?
May 14 at 10:59
4
Is $\frac{n}{\log n} \log \frac{n}{\log n} = O(n)$?
May 10 at 20:07
4
Proving that $X\to aX|Y$, $Y \to Yab|b$ is unambiguous
Apr 20 at 11:22
4
Modified shortest path problem
Jun 1 '20 at 14:19
4
Algorithm for ensuring that each element ends up in its specified range when composing a list
May 27 '20 at 11:38
3
Is it true that $P = coNP$?
Oct 18 at 22:32
3
What is the meaning of the pipe symbol here?
Sep 15 at 14:31
3
Question about "with high probability"
Aug 3 at 7:12
3
Number of queries for $NP^{NP}$
Jul 5 at 16:21
3
Is it true that PRIMES are in SPARSE?
Jun 17 at 12:46
1
2 3 4 5
…
15

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.