Newest Questions

1 vote

0 answers

49 views

I have been trying to solve the following problem from ericksons algorithms: 20)c) Let P be a set of n points evenly distributed on the unit circle, and let S be a set of m line segments with ...

5 votes

2 answers

153 views

First of all, I do know that it is not known whether or not $\overline{SAT}$ is in NP. But to me, it clearly looks like it is in NP. Given a Boolean formula φ with n variables, we nondeterministically ...

-1 votes

1 answer

41 views

$$T(n) = T\big(\frac{ n}{2}\big) + \Theta(1)$$ Hi, I'm resolving this recurrence relation through Master Theorem. I would like to know my solution is correct. $\alpha = 1$ $\beta =2,ドル $f(n) = \Theta(...

-4 votes

0 answers

63 views

Turing machine for {a^i b^j | j is divisible by i, i ≥ 2, j ≥ 2} Some example strings in the language are as follows: i.aabbbb ii.aaabbb iii.aaabbbbbbbbb iv.aaaaabbbbbbbbbbbbbbbbbbbb Some example ...

1 vote

1 answer

58 views

I'm reading this paper (Tactic Learning and Proving for the Coq Proof Assistant written by Blaauwbroek et al). In section 3 (Proof Recording) it mentions one-shingles and two-shingles : After ...

0 votes

1 answer

31 views

I am trying to determine if the language A={w#x∣w,x∈{a,b}* and x is a substring of w} is a context-free language or not. I have tried to apply the pumping lemma for context-free languages to prove ...

0 votes

1 answer

113 views

To compute the $n$th Fibonacci number, a recursive algorithm is as follows: ...

0 votes

1 answer

29 views

In the book of Papadimitriou. Combinatorial optimization, there is the instance of Linear Programming (LP) s.t. \begin{equation} \begin{split} &{\rm minimize:\;} c_1x_1 + c_2x_2 + c_3x_3,\\ &{\...

2 votes

1 answer

91 views

Consider the linkedin queens problem - our queens move like a rook + king on a nxn chessboard with coloured regions. The goal of the game is to place exactly queen in every row, column and coloured ...

0 votes

0 answers

36 views

The Internet is full of claims that an $LL(1)$ grammar cannot be ambiguous, left-recursive, or not left-factored. But is the statement "An $LL(1)$ grammar cannot be non-left-factored or left-...

0 votes

1 answer

32 views

I'm giving my students proofs of code correctness using loop invariants and induction, and I'm constantly running up against a notational problem. It's not the end of the world, but it is a ...

-4 votes

0 answers

53 views

I am attempting to formalize this structural lattice math; Mathematical Formalism Let $\Lambda$ be a finite cubic lattice of size $N \times N \times N$ with periodic boundary conditions, isomorphic to ...

1 vote

1 answer

75 views

A classic result is that a if a language is not regular its decision problem requires more than constant memory (i.e. $\Omega(\log \log n)$). I am wondering if there are similar results for other ...

0 votes

0 answers

44 views

Turing machines are defined over a discrete memory tape. Is it possible to use a continuous memory tape (i.e. symbolically) instead of a discrete one. Will such a machine be more powerful? https://en....

1 vote

2 answers

222 views

I’ve been reading about the Model Context Protocol (MCP) and how it lets LLMs interact with tools like email, file systems, and APIs. One thing I don’t fully get is the idea of moving "memory" from ...