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 …
Blog
[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]: 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]: 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]: 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]: 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]: Compute square root using (bit) additions and shifts as primitives
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 …
[Solved]: Collectively pay the bill problem
Problem Detail: There are $n$ people at a table. The $i$th person has to pay $p_i$ dollars. Some people don’t have the right bills to pay exactly $p_i$, so they come up with the following algorithm. First, everyone puts some of Read More …
[Solved]: What is the Big O of T(n)?
Problem Detail: I have a homework that I should find the formula and the order of $T(n)$ given by $$T(1) = 1 qquadqquad T(n) = frac{T(n-1)}{T(n-1) + 1},. $$ I’ve established that $T(n) = frac{1}{n}$ but now I am a little Read More …
[Solved]: How come {ww} isn’t regular when {uv | |u|=|v|} is?
Problem Detail: As we know, using the pumping lemma, we can easily prove the language $L = { w w mid w in {a,b}^* }$ is not a regular language. However, the language $L_1 = { w_1 w_2 mid |w_1| = Read More …
