Skip to main content
PlsWork's user avatar
PlsWork's user avatar
PlsWork's user avatar
PlsWork
  • Member for 7 years
  • Last seen more than a month ago
3 votes
1 answer
136 views

Equivalence of dfferent TM definitions

3 votes
1 answer
2k views

Right moving turing machines and FSA's

3 votes
1 answer
814 views

Compute visible vertices of a polygon

3 votes
1 answer
87 views

Comparison of two line segments along a ray

2 votes
1 answer
185 views

Tight bound on the number of intersections between a line and a triangulation

2 votes
1 answer
466 views

Semi decidability proof

2 votes
0 answers
582 views

Why is there no FPTAS for the maximum independent set problem?

2 votes
1 answer
3k views

Approximating maximal independent set with a minimal vertex cover approximation

2 votes
2 answers
980 views

Compute median in unsorted array in $\mathcal{O}(\log{}n)$ space and $\mathcal{O}(\log{}n)$ passes

1 vote
1 answer
769 views

Algorithm for finding 2 missing items in a stream of integers

1 vote
2 answers
1k views

Using visible line segments to compute a visibility polygon

1 vote
0 answers
36 views

Read nodes of a BST in blocks of size $k$ and traverse it in $\mathcal{O}(log_kn)$

1 vote
1 answer
337 views

Basic approximation algorithms understanding

1 vote
1 answer
97 views

Algorithm which finds the maxmal solution that satisfies the following constraints

1 vote
1 answer
27 views

Find the appropriate product

1 vote
1 answer
170 views

Polynomial time reductions between two problems

0 votes
1 answer
304 views

Determine the optimal strategy and maximize the reward

0 votes
1 answer
466 views

Proving unsatisfiability of a propositional formula

0 votes
0 answers
98 views

I/O-Efficient graph coloring

0 votes
1 answer
60 views

Algorithm for finding a matrix which satisfies certain constraints [closed]

0 votes
0 answers
58 views

Robust orientation test

0 votes
1 answer
255 views

Triangulating a simple polygon via its trapezoidal map