User nir shahar

39 votes

Accepted

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

answered Apr 22, 2021 at 20:03

39 votes

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

graphs dijkstras-algorithm

answered Aug 19, 2021 at 10:08

29 votes

Accepted

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

turing-machines

answered Aug 9, 2021 at 7:40

13 votes

Is an integer variable constant or logarithmic space?

asymptotics

answered Apr 18, 2021 at 19:43

10 votes

Accepted

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

spanning-trees

answered Apr 5, 2021 at 14:03

10 votes

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

complexity-theory time-complexity np-hard np p-vs-np

answered May 3, 2021 at 10:49

9 votes

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

turing-machines

answered Aug 10, 2021 at 12:12

8 votes

Accepted

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

combinatorics discrete-mathematics mathematical-foundations

answered Mar 1, 2021 at 14:21

7 votes

Accepted

What is this algorithm computing and how to prove it?

factoring

answered Jul 26, 2021 at 12:16

6 votes

Accepted

What algorithm do SVMs use to minimize their objective function?

machine-learning svm simplex

answered Feb 22, 2021 at 15:35

5 votes

Accepted

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

computer-architecture logic cpu binary

answered Feb 26, 2021 at 22:36

5 votes

Accepted

Polynomial time optimization problems belong to which complexity class?

complexity-theory optimization complexity-classes

answered May 2, 2021 at 19:44

5 votes

Why are all regular languages in P?

complexity-theory

answered Jun 9, 2021 at 17:03

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$/}$?)

regular-expressions natural-language-processing

answered Jun 22, 2021 at 11:42

5 votes

tautology vs satisfiability

complexity-theory turing-machines computability reductions np

answered Jul 21, 2021 at 14:17

5 votes

Accepted

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

complexity-theory turing-machines reductions

answered Nov 11, 2021 at 17:18

4 votes

Accepted

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

computer-architecture computation-models

answered Oct 20, 2021 at 11:00

4 votes

All possible sum of each array combination

algorithms time-complexity combinatorics

answered Nov 30, 2021 at 17:20

4 votes

Accepted

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

graphs depth-first-search connected-components topological-ordering

answered Dec 10, 2021 at 21:17

4 votes

Accepted

Sharing a requested secret number not knowing which

number-theory security encryption

answered Jul 25, 2021 at 12:55

4 votes

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

algorithms polynomials

answered Jul 3, 2021 at 15:14

4 votes

Can a non deterministic finite automaton go into infinite loop?

turing-machines automata finite-automata theory

answered Sep 2, 2021 at 7:48

4 votes

Should the certificate for NPSPACE be polynomial in size?

complexity-theory space-complexity

answered Jun 17, 2021 at 7:21

4 votes

Accepted

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

time-complexity asymptotics

answered May 10, 2021 at 20:07

4 votes

Accepted

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

algorithms linked-lists

answered May 14, 2021 at 10:59

4 votes

Set theory pertaining to category theory and functional programming

sets functional-programming category-theory

answered May 14, 2021 at 14:46

4 votes

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

context-free formal-grammars ambiguity

answered Apr 20, 2021 at 11:22

4 votes

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

time-complexity dynamic-programming recursion memoization

answered Jul 14, 2020 at 13:34

4 votes

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

algorithms recommendation-systems

answered May 27, 2020 at 11:38

4 votes

Accepted

Modified shortest path problem

algorithms graphs shortest-path dijkstras-algorithm

answered Jun 1, 2020 at 14:19

Stack Exchange Network

current community

your communities

more stack exchange communities

495 Answers

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

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

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

Is an integer variable constant or logarithmic space?

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

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

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

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

What is this algorithm computing and how to prove it?

What algorithm do SVMs use to minimize their objective function?

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

Polynomial time optimization problems belong to which complexity class?

Why are all regular languages in P?

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

tautology vs satisfiability

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

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

All possible sum of each array combination

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

Sharing a requested secret number not knowing which

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

Can a non deterministic finite automaton go into infinite loop?

Should the certificate for NPSPACE be polynomial in size?

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

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

Set theory pertaining to category theory and functional programming

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

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

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

Modified shortest path problem