Problem Detail: I have a problem whose lower bound of problem complexity is proven to be $O(n+m)$ (n < m) and I also come up with an algorithm whose time complexity is $ O(n+m)$, space complexity is $ O(n)$. (All on Read More …
Category: Uncategorized
[Solved]: Undecidability in the context of modern programming languages
Problem Detail: Imagine a program, executed by an interpreter to be a Turing Machine. Consider this code: x = read_input print x Does undecidability mean that there may possibly be an input to this program such that the program may never Read More …
[Solved]: Is the memory-runtime tradeoff an equivalent of Heisenberg’s uncertainty principle?
Problem Detail: When I work on an algorithm to solve a computing problem, I often experience that speed can be increased by using more memory, and memory usage can be decreased at the price of increased running time, but I can Read More …
[Solved]: Is this path finding problem in a 01-matrix NP-complete?
Problem Detail: The problem: Input: An $n times n$ matrix of 0’s and 1’s, and a position pos of this matrix (i.e. a pair of integers $i,j$ with $1 leq i,j leq n$) Output: YES if there exists a path Read More …
[Solved]: Why do we use Insertion Sort in the Bucket Sort?
Problem Detail: Bucket sort is a linear-time sort. Why do we use insertion sort in it? We know that insertion sort takes $O(n^2)$ time. Why can we not use any linear sort inside it? As we see, when in each bucket Read More …
[Solved]: Confusion in CLRS’s version of Prim’s algorithm
Problem Detail: The algorithm is as follows: MST-PRIM(G,w,r) 1 for each u ∈ G.V //initialization 2 u.key = ∞ 3 u.π = NIL 4 r.key = 0 5 Q = G.V //end initialization 6 while Q ≠ ∅ 7 u = Read More …
[Solved]: Generating constraints to solve dependently-typed metavariables?
Problem Detail: In dependent-types, Miller pattern unification is used to solve a decidable fragment of higher-order unification. This allows dependently-typed languages to contain metavariables or implicit arguments. There are many papers which describe, given a unification problem in the pattern fragment, Read More …
[Solved]: Are all NP-complete languages log-space reducible to each other?
Problem Detail: NP-complete languages are reducible to each other in polynomial time. Does this mean that they are also log-space reducible to each other? It seems as if this is true because in log-space, we can have polynomially many computations. Asked Read More …
[Solved]: What’s the difference between physically based rendering and global illumination?
Problem Detail: I know that Physically based rendering means we try to simulate how light actually works in real world and global illumination is bouncing back of light when it strikes a surface. But what’s actual difference between them and how Read More …
[Solved]: Karger’s algorithm: why does every vertex have degree at least the number of edges crossing a min cut?
Problem Detail: I’m currently watching a video on the analysis of Krager’s Algorithm, and I am confused about something. The analysis goes as follows: Fix a min cut $(A,B)$. Let $k$ = # of edges crossing $(A,B)$ , these edges will Read More …
