Hottest Questions Today

4

votes

2

answers

2k

views

Contradiction proof for inequality of P and NP?

answered 14 hours ago David Richerby 70.9k

0

votes

0

answers

14

views

3SAT formula with only positive variables [on hold]

satisfiability 3-sat

modified 4 hours ago Travis Wells 20

0

votes

0

answers

25

views

Circular Doubly Linked List find length with single pointer

algorithms complexity-theory data-structures

modified 5 hours ago motis10 118

1

vote

1

answer

18

views

Why isn't DIV necessarily in P?

complexity-theory formal-languages time-complexity

answered 5 hours ago D.W.♦ 104k

0

votes

2

answers

20

views

Check whether all elements are different

algorithms hashing

modified 6 hours ago Apass.Jack 14.6k

0

votes

0

answers

12

views

What would be a good way to prove NP-Completeness of Min-satisfiablity problem

np-complete satisfiability

asked 5 hours ago spiky 1

-1

votes

0

answers

29

views

Algorithm recovers solutions to all constrained n2*n2 Sudoku grids

algorithms sudoku

modified 7 hours ago Travis Wells 20

1

vote

3

answers

52

views

How does sum of first $k$ integers equal $k(k+1)/2$ [on hold]

mathematical-analysis

modified 8 hours ago Kyle Jones 5,857

0

votes

1

answer

34

views

How do you compute the Pareto Front of a set?

algorithms optimization sets pareto

modified 8 hours ago Apass.Jack 14.6k

-1

votes

0

answers

11

views

Clustering algorithms which accept number of clusters [on hold]

algorithms clustering

asked 9 hours ago Maryam Abdirad 1

1

vote

1

answer

49

views

Vertex Cover of size at most $\log n$

complexity-theory vertex-cover

modified 9 hours ago Pål GD 7,290

0

votes

0

answers

13

views

Should I use lamport logical clock or vector clock or something else?

distributed-systems

modified 10 hours ago user1870400 101

0

votes

1

answer

31

views

How does the memory of a 64bit and 32bit processor work

memory-hardware memory-access memory-allocation

modified 15 hours ago gnasher729 12.2k

1

vote

0

answers

54

views

for two languages in $NP$ does one of them karp reducible to another?

reductions np

modified 13 hours ago D.W.♦ 104k

8

votes

3

answers

514

views

How to count in linear time worst-case?

algorithms search-trees hash-tables

modified 22 hours ago Peter Taylor 1,356

0

votes

0

answers

17

views

Bus topology cable links

data-structures

asked 14 hours ago Piyush Yadav 1

1

vote

1

answer

23

views

Turing machine - compare two words

turing-machines comparison

answered 16 hours ago Peter Leupold 740

4

votes

0

answers

24

views

Number of strings at given edit distance

combinatorics strings edit-distance word-combinatorics

modified 15 hours ago Discrete lizard♦ 4,798

13

votes

2

answers

5k

views

What is a 'Key' in computer science?

terminology

modified 2 days ago Discrete lizard♦ 4,798

1

vote

2

answers

149

views

Is there a sorting algorithm of order $n + k \log{k}$?

algorithms sorting quicksort

modified 12 hours ago ryan 3,264

1

vote

1

answer

57

views

Why does $O(n \log n)$ seem so linear?

algorithm-analysis experimental-analysis

answered 23 hours ago Raphael♦ 58.3k

2

votes

1

answer

20

views

Representing an equality in an ILP

logic binary-trees linear-programming boolean-algebra integer-programming

modified 11 hours ago Bryce Kille 381

0

votes

0

answers

33

views

Finding a shortest path in graph

algorithms graphs

modified 16 hours ago xskxzr 4,367

2

votes

1

answer

47

views

Why is Graph Isomorphism downward self reducible?

complexity-theory reductions oracle-machines graph-isomorphism

answered 5 hours ago Apass.Jack 14.6k

4

votes

0

answers

33

views

Maximum weight independent set in a King's graph

graph-theory dynamic-programming

asked 22 hours ago Daniel 21

0

votes

0

answers

18

views

Definition of unbounded approximation ratio

algorithms graph-theory approximation

asked 20 hours ago Mahdi 6

0

votes

1

answer

19

views

Difference between auxiliary space v/s space complexity

complexity-theory space-complexity

modified 20 hours ago Discrete lizard♦ 4,798

1

vote

1

answer

31

views

How many ways to express N as sum of 2, 3 and 5?

dynamic-programming counting

modified yesterday jasli 56

0

votes

1

answer

42

views

Closed form solution of $T(n) = 5T(n-1) + n^2$ [on hold]

recurrence-relation

modified yesterday ryan 3,264

0

votes

1

answer

22

views

graphs - finding a shortest path length not achievable by breadth first search

graphs

answered yesterday jasli 56

27

votes

4

answers

4k

views

What did Turing mean when saying that “machines cannot give rise to surprises” is due to a fallacy?

turing-machines computability computation-models

modified Apr 22 at 15:47 mowwwalker 219

0

votes

1

answer

26

views

What is the time complexity of this method?

time-complexity

answered yesterday jasli 56

1

vote

3

answers

50

views

Shifting and adding to get multiplication values?

multiplication

answered 13 hours ago David Richerby 70.9k

1

vote

1

answer

57

views

Complexity of Merge Sort that splits in a random position

complexity-theory time-complexity mergesort

modified 21 hours ago EladAskenazi 11

0

votes

1

answer

24

views

radix-sort with different bases

sorting c radix-sort c++

answered yesterday Evil 8,126

0

votes

0

answers

25

views

Projection operator for constraints

constraint-satisfaction type-inference constraint-programming logic-programming

modified yesterday jack malkovick 42

-1

votes

0

answers

21

views

Advantage and disadvantage of increasing the page size (of the virtual memory)

virtual-memory

asked yesterday Red 1

0

votes

1

answer

48

views

3-DNF proves the algorithm is in P class

satisfiability decision-problem

answered yesterday D.W.♦ 104k

1

vote

1

answer

24

views

Merging and Unmerging Sets of Trees Efficiently

algorithms trees

answered yesterday D.W.♦ 104k

3

votes

2

answers

51

views

Lower bound of disjointness by discrepancy?

lower-bounds communication-complexity

modified yesterday Apass.Jack 14.6k

0

votes

0

answers

25

views

Is there any grammar parseable by LALR(1) but not LR(1)?

context-free formal-grammars ambiguity

asked yesterday gaazkam 120

0

votes

0

answers

24

views

3-DNF $\rho$ falsifiable

complexity-theory p-vs-np 3-sat check-my-answer

modified yesterday Root 46

1

vote

1

answer

119

views

reduction from 3-SAT to Subset Sum problem

complexity-theory automata reductions

modified yesterday Kyle Jones 5,857

0

votes

0

answers

14

views

What could happen if bitmap and data block not updated

filesystems storage

asked yesterday nihulus 110

-2

votes

0

answers

15

views

What is the average geodesic distance in a fully connected network/complete graph? [on hold]

graphs

modified yesterday Nina Lora 1

3

votes

2

answers

59

views

Fewest traversals to visit all vertices of DAG

algorithms graph-theory graph-traversal dag

modified yesterday ed94133 118

0

votes

0

answers

13

views

Recurrence Relation and Complexity Class [on hold]

algorithms time-complexity recurrence-relation complexity-classes

asked yesterday gooddayjay 1

2

votes

2

answers

46

views

Operator name in LL(1) computation

formal-languages context-free terminology formal-grammars

modified yesterday D.W.♦ 104k

Top Questions

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