Problem Detail: This question stems from a few answers and comments on a question I posted in signal processing found here. I guess I am a little confused. Are there any concrete differences between realtime software/hardware and just a regular PC? Read More …
Blog
[Solved]: Free variables of (λx.xy)x and bound variables of λxy.x
Problem Detail: I was solving exercises on Lambda calculus. However, my solutions are different from the answers and I cannot see what is wrong. Find free variables of $(lambda x.xy)x$. My workings: $FV((lambda x.xy)x)=FV(lambda x.xy) cup FV(x)={y} cup {x}={x,y}$. The model Read More …
[Solved]: Proving that finding wheel subgraphs is NP-complete
Problem Detail: Can you help me with this problem ? Given an undirected graph $G$ and an integer $n$, prove that determining whether the graph has wheel on $n$ vertices $W_{n}$ (a wheel $W_{i}$ is such that $i$ nodes form a Read More …
[Solved]: Euclidean Steiner Tree Question in Approximation Algorithms
Problem Detail: Given $n$ points in $mathbf{R}^2$, define the optimal Euclidean Steiner tree to be a minimum (Euclidean) length tree containing all $n$ points and any other subset of points from $mathbf{R}^2$. Prove that each of the additional points must have Read More …
[Solved]: What’s an intuitive distinction between semi-computable problems and noncomputable problems/functions?
Problem Detail: The definitions I’ve found were highly technical and using terms I’ve never seen before. Say, I have a certain irrational number e that I get get closer and closer to with a computer and I want to determine if Read More …
[Solved]: Formally describing a new domain specific programming language
Problem Detail: I am about to implement a domain specific language for representation of social learning conventions. Part of the implementation is a formal description of a language – its ‘calculus’, symbols and logical expressions. My approach would be to describe Read More …
[Solved]: Why is the transform in Schönhage–Strassen’s multiplication algorithm cheap?
Problem Detail: The Schönhage–Strassen multiplication algorithm works by turning multiplications of size $N$ into many multiplications of size $lg(N)$ with a number-theoretic transform, and recursing. At least I think that’s what it does because there’s some other cleverness and I really Read More …
[Solved]: From Guido’s essays, how does this function avoid quadratic behavior in a string concatenation algorithm?
Problem Detail: I am reading one of Guido van Rossum’s essays on optimization in Python. We are interested in converting a Python list of integers to their character equivalents. Here’s the straightforward algorithm. def f3(list): string = “” for character in Read More …
[Solved]: What precisely is infinite ambiguity in a grammar?
Problem Detail: From what I’ve read, an example of infinite ambiguity is usually given in a form of a loop: $S rightarrow aA A rightarrow B B rightarrow A B rightarrow b$ But a grammar is called ambiguous if there’s more Read More …
[Solved]: Is there a canonical definition of “pure” function?
Problem Detail: StackOverflow pointed me here, so the question might be a bit in a layman’s terms. Wikipedia defines pure functions as In computer programming, a function may be described as a pure function if both these statements about the function Read More …
