Top Questions

2 votes
3 answers
1k views

Find 1s in almost all 0 array using comparisons only

1 vote
2 answers
69 views

Resources on Moore and Mealy Machines

4 votes
1 answer
151 views

Tseitin formula on 2-connected graph

4 votes
1 answer
132 views

Size of the certificate as a property of the problem

1 vote
1 answer
67 views

What is the role of diagonalization in the proof of undecidability of the halting problem?

0 votes
2 answers
62 views

regular expression for $\{w\in \{a,b\}^*\mid |w|_a \mod 2 = 0\}\setminus \Sigma^*aab\Sigma^*$

0 votes
1 answer
70 views

Deciding if a language is CFL or in $P$

0 votes
3 answers
49 views

How Many Times Would The Assembler Load and Store i

6 votes
0 answers
80 views

Problem of constructing binary sequence with least possible 1s under given constraint

0 votes
1 answer
36 views

Is my understanding of Eta reduction correct?

2 votes
1 answer
46 views

How to solve the recurrence $ T(n) = 4T\left(\frac{n}{2}\right) + \frac{n}{\lg n} $ in terms of $\Theta$?

0 votes
1 answer
46 views

Can the MST's "cut property" be derived from the "cycle property" and vice versa?

3 votes
1 answer
70 views

Why $2n−1$ comparisons are sometimes necessary to correctly merge two sorted sequences [duplicate]

1 vote
1 answer
48 views

Proof that nondeterministic TM runs in exponential time

0 votes
2 answers
38 views

why didn't ASCII/utf-8 used 00000000 to represent char 0 or rather any other character

1 vote
2 answers
37 views

How to Solve the Recurrence Relation $T(n) = 8T\left(\frac{n - \sqrt{n}}{4}\right) + n^2$ in terms of $\Theta$?

2 votes
0 answers
45 views

Approximate the parity function in L1-norm

0 votes
1 answer
44 views

Why finding the largest element in a min-heap using a comparison-based algorithm takes Ω(logn) time?

0 votes
0 answers
41 views

PDA equivalent to an $\varepsilon$-free PDA

1 vote
2 answers
24 views

Is $L = \{ \langle G,k\rangle \mid G $ has a simple cycle at length $k \}$ in P or in NP

-3 votes
0 answers
36 views

Huffman and its enhancement technique called blocking

0 votes
0 answers
33 views

Show 3-colorable graph with hamiltonian cycle is NP-Complete

1 vote
1 answer
31 views

Knapsack Problem: Find Top-K Lower Profit Solutions

2 votes
1 answer
31 views

Maximum of a tritonic array

2 votes
1 answer
18 views

Is limiting the input type in subclasses legitimate (does it give a stronger or the same specification)?

1 vote
0 answers
29 views

Choosing one element from each partition that minimize the difference between max and min

0 votes
1 answer
21 views

Is $O(n^{f(n)})$ superexponential if $f(n)$ is a polynomial function such that $f(n) > n$ as $n$ approaches $\infty$?

0 votes
0 answers
26 views

Are they talking about virtual memory in this article?

0 votes
1 answer
20 views

Find a negative cycle linearly?

0 votes
1 answer
20 views

Model checking algorithms

0 votes
0 answers
25 views

Is this version of SAT NP-Complete?

3 votes
0 answers
22 views

Finding a set of edges $E$ such that every $s$-$t$-path contains at least 2 edges from $E$

0 votes
1 answer
17 views

Table driven parser vs Recursive Descent parser

1 vote
1 answer
21 views

Constrained Maximum Flow Minimum Cost

1 vote
1 answer
16 views

Best internal representation of a random variable to enable iterative sampling and interpolation/regression

0 votes
1 answer
15 views

The Atlas system word addresses

0 votes
0 answers
19 views

Want to plot rectangles given their width,height and the cartesian origin (0,0)

0 votes
0 answers
18 views

Find maximum sum subgrid under constraint

2 votes
0 answers
18 views

Issue understanding how control signals are pipelined in a RISC architecture

0 votes
0 answers
18 views

The language made from the context free Language (CFL) is also a CFL? [duplicate]

0 votes
1 answer
19 views

Convert ternary constraint into set of binary

0 votes
0 answers
14 views

Textbooks to study machine learning as a TCS/FM/symbolic AI researcher

-2 votes
0 answers
14 views

Find the asymptotic execution time of the program in explicit form if for known recurrence relation: 𝑇(𝑛) = 𝑂(1), 𝑛=0; 𝑎𝑇(𝑛−1)+𝑂(𝑛),𝑛≥1,𝑎>1

0 votes
1 answer
13 views

how to polynomially check if a given boolean formula is unsatisfiable

1 vote
1 answer
12 views

Can you identify this assignment problem and efficient solutions or estimates?

0 votes
0 answers
11 views

How can I reduce the complexity of an inverse DFT where I have a uniform frequency series being evaluated at non-uniform target points?


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