Problem Detail: The problem is defined as: Given a set of $N$ points $(x_1, x_2, x_3, ldots, x_n)$ and $L$ the fixed length of a segment. Find the number of maximum points which you can cover with a segment line of Read More …
Blog
[Solved]: Is the undecidable function $UC$ well-defined for proving the undecidability of Halting Problem?
Problem Detail: I am new to Computability Theory and find it is both amazing and confusing. Specifically, it is difficult for me to get through the undecidability of the well-known Halting Problem. Halting function: The Halt function takes an input a Read More …
[Solved]: How is IO a monad?
Problem Detail: I am learning the Haskell programming language. From what I am reading, Input/Ouput (IO) raises challenges for Haskell’s purity, since by definition we are interacting with the outside world. From Wikipedia: In a purely functional language, such as Haskell, Read More …
[Solved]: Expressive power of lexer + parser
Problem Detail: Most modern compilers split their syntax analysis into a lexical phase that is followed by a parsing phase. The lexical phase is given by a regular expression, while parsing is guided by a context-free grammar. What class of languages Read More …
[Solved]: Want to know the time complexity inner for loop which is partially iterating the array
Problem Detail: Question: Find out next increasing value of each element in this below array. int[] array = { 5, 2, 7, 10, 4, 12} e.g) 5’s nextIncreasingValue: 7 2’s nextIncreasingValue: 7 7’s nextIncreasingValue: 10 … 12’s nextIncreasingValue: -1 Implementation: for(int Read More …
[Solved]: Single-source shortest paths as a linear program
Problem Detail: I saw that I can formulate single-source shortest path as the following linear program: Given $G=(V,E)$ and $wcolon Eto R$ and with negative cycles, find $max,d(s,t)$ such that begin{align*} d(s,v) &le d(s,u)+w(u,v) quad forall (u,v)in E d(s,s) &=0 end{align*} Read More …
[Solved]: Could an NP-hard problem have a mechanical or physical solution method?
Problem Detail: Is there any NP-hard problem that we can find a mechanical “polynomial time” solution to? For example, suppose we construct a graph out of something physical, e.g. we have have pipes through which we can move water. If this Read More …
[Solved]: Regularity of unary languages with word lengths the sum of two resp. three squares
Problem Detail: I think about unary languages $L_k$, where $L_k$ is set of all words which length is the sum of $k$ squares. Formally: $$L_k={a^nmid n=sum_{i=1}^k {n_i}^2,;;n_iinmathbb{N_0};(1le ile k)} $$ It is easy to show that $L_1={a^{n^2}mid ninmathbb{N_0}}$ is not regular Read More …
[Solved]: Issue understanding the reduction of SAT to 3-SAT in poly time
Problem Detail: Reading this http://classes.soe.ucsc.edu/cmps102/Spring10/lect/17/SAT-3SAT-and-other-red.pdf, I came to know that reducing a clause $C_i$ from a $SAT$ instance containing more than 3 literals to a $3-SAT$ instance is done this way, Suppose $C_1$ is ${x_1, x_2, x_3, x_4}$. It’s equivalent representation Read More …
[Solved]: Quantum algorithms and quantum computation
Problem Detail: Is my (very high-level) understanding correct here regarding quantum algorithms — Quantum computers can process a massive amount of operations in parallel to the nature of qubits and their ability to have states that are superpositions of $|0rangle$ and Read More …
