Problem Detail: If the alphabet is countably infinite, then is the number of finite-length strings over this alphabet countably or uncountably infinite? Asked By : Vivek Barsopia Answered By : David Richerby It’s countable. The set $S_ell$ of strings of length $ell$ is $SigmatimesdotstimesSigma$, which Read More …
Blog
[Solved]: Get the nth lexicographic string of “all” possible combinations of an alphabet
Problem Detail: Is there a way to find the nth string of characters from an alphabet, without having to store “all” of the combinations? Example: Alphabet $A = {a,b,c}, n=12$. All possible combinations in lexicographic order are $C = {a, ab, Read More …
[Solved]: Rigorous proof for validity of assumption $n=b^k$ when using the Master theorem
Problem Detail: The Master theorem is a beautiful tool for solving certain kinds of recurrences. However, we often gloss over an integral part when applying it. For example, during the analysis of Mergesort we happily go from $qquad T(n) = Tleft(leftlfloor Read More …
[Solved]: How to prove $(n+1)! = O(2^{(2^n)})$
Problem Detail: I am trying to prove $(n+1)! = O(2^{(2^n)})$. I am trying to use L’Hospital rule but I am stuck with infinite derivatives. Can anyone tell me how i can prove this? Asked By : Sid Answered By : Yuval Filmus You Read More …
[Solved]: Adapting neural network
Problem Detail: I have on a few occasions trained neural networks (back propagation networks) with some rather complicated data sets (backgammon positions and OCR). When doing this, it seems that a lot of the work involves trying out different configurations of Read More …
[Solved]: Is Green’s the best 16-input sorting network so far?
Problem Detail: Every paper says that Green’s construction is the best 16-input sorting network as for now. But why does Wikipedia says: “Size, lower bound: 53”? I thought “lower bound” meant:”If there exists at least an algorithm that can…”. Am I Read More …
[Solved]: Finding the largest 3-clique-free induced subgraph
Problem Detail: Consider this problem: Given an undirected graph $G = (V, E)$, find $G’ = (V’, E’)$ such that: $G’$ is an induced subgraph of $G$ $G’$ has no 3-cliques $|V’|$ is maximal So the least number of vertices must Read More …
[Solved]: Efficient compression of unlabeled trees
Problem Detail: Consider unlabeled, rooted binary trees. We can compress such trees: whenever there are pointers to subtrees $T$ and $T'$ with $T = T'$ (interpreting $=$ as structural equality), we store (w.l.o.g.) $T$ and replace all pointers to $T'$ with Read More …
[Solved]: How to find specificity of a regex match?
Problem Detail: I’m thinking about a routing system. Imagine I have the two following regexes pathpart1/pathpart2 => specific match that routes to controller1 .* => catch-all that routes to controller2 And I let them match on a URL, e.g. ‘pathpart1/pathpart2’. They Read More …
[Solved]: Adjacent house , dynamic programming problem
Problem Detail: I have to be honest this is a homework problem, but I just need to discuss this with some one. The problem is there is a row of n houses, with different profit e.g profit1 for house 1, it Read More …
