Problem Detail: Question: Given an $n$-bit natural number $N$, how to compute $lceil sqrt{N} rceil$ using only $O(n)$ (bit) additions and shifts? The tip is to use binary search. However, I could not achieve the required complexity (I got $O(n^2)$). Read More …
Author: ignougroup
[Solved]: PDA recognising all strings with a $1$ in the second half
Problem Detail: My professor gave us an old exam to look over for our final exam and I am having a hard time understanding the push down automata problem he gave. In the problem it says: Let $Sigma = {0,1}$ and Read More …
[Solved]: What is a “contradiction” in constructive logic?
Problem Detail: In Practical Foundations for Programming Languages, Robert Harper says If for a proposition to be true means to have a proof of it, what does it mean for a proposition to be false? It means that we have a Read More …
[Solved]: How does one efficiently produce all binary sequences with an equal number of 0’s and 1’s?
Problem Detail: A binary sequence of length $n$ is just an ordered sequence $x_1,ldots,x_n$ so that each $x_j$ is either $0$ or $1$. In order to generate all such binary sequences, one can use the obvious binary tree structure in the Read More …
[Solved]: HamCycle to HamPath reduction
Problem Detail: I’ve seen a reduction that’s done by adding another vertex to the graph and creating a path through that vertex. Why do I need to add a vertex? Cant I just remove an edge? Lets say the graph with Read More …
[Solved]: Can any finite problem be in NP-Complete?
Problem Detail: My lecturer made the statement Any finite problem cannot be NP-Complete He was talking about Sudoku’s at the time saying something along the lines that for a 8×8 Sudoku there is a finite set of solutions but I can’t Read More …
[Solved]: Tree data structure for fast merges
Problem Detail: I need trees that have the following properties: Each node in the tree has two values associated with it – a key and an associated opaque data element. An internal node in the tree has unbounded number of children. Read More …
[Solved]: Does immutability in functional programming really exist?
Problem Detail: Although I work as a programmer in my daily life and use all the trendy languages (Python, Java, C, etc) I still have no clear view of what functional programming is. From what I’ve read, one property of functionally Read More …
[Solved]: Can we make a problem harder than NP and coNP if they are not equal?
Problem Detail: Let us assume that $mathsf{NP} neq mathsf{coNP}$. Consider the graph 3-colorability problem. Since $mathsf{NP} neq mathsf{coNP}$ implies $mathsf{P} neq mathsf{NP}$ and 3-coloribility is $mathsf{NP}$-complete and its complement is $mathsf{coNP}$-complete , we have: 3-coloribility is not in $mathsf{P}$, i.e. there Read More …
[Solved]: Fast algorithm for interpolating data from polar coordinates to cartesian coordinates
Problem Detail: I have a set of solution nodes generated over a polar grid. I would like to convert / interpolate these solution nodes onto a Cartesian grid: That is, using the image above, for each node in the Cartesian grid Read More …
