Problem Detail: If I have this pseudocode: for i=0 to n/2 do for j=0 to n/2 do … do anything …. The number of iterations is $n^2/4$. What is the complexity of this program? Is it $O(n^2)$? What is the intuition Read More …
Author: ignougroup
[Solved]: What Is The Complexity of Implementing a Particle Filter?
Problem Detail: In a video discussing the merits of particle filters for localization, it was implied that there is some ambiguity about the complexity cost of particle filter implementations. Is this correct? Could someone explain this? Asked By : DorkRawk Answered By Read More …
[Solved]: how do I find a undecidable subset of a set that’s decidable?
Problem Detail: Given that Let S = {a | |a| is odd}. I know that since S is decidable, but does there exist a subset within S that is undecidable? Asked By : user3277633 Answered By : Yuval Filmus Hint: For every language Read More …
[Solved]: Is there a “sorting” algorithm which returns a random permutation when using a coin-flip comparator?
Problem Detail: Inspired by this question in which the asker wants to know if the running time changes when the comparator used in a standard search algorithm is replaced by a fair coin-flip, and also Microsoft’s prominent failure to write a Read More …
[Solved]: Difference between Binomial and Fibonacci heap (marking)
Problem Detail: I am confused why Binomial heaps do not utilize marking. Concerning Fibonacci heap children: Each tree in a Fibonacci heap is allowed to lose at most two children before that tree needs to be “reprocessed” at a later step. Read More …
[Solved]: Adding a node between two others, minimizing its maximum distance to any other node
Problem Detail: We are given an undirected graph weighted with positive arc lengths and a distinguished edge $(a,b)$ in the graph. The problem is to replace this edge by two edges $(a,c)$ and $(c,b)$ where $c$ is a new node, such Read More …
[Solved]: Understanding Multilevel Caches
Problem Detail: I’m reading multi-level cache and came across a question through which i got confused. I’ve read that Between processor and Cache Word/ Byte is transfered Between Cache and Main memory Block(Block of words) is transfered. If there is a Read More …
[Solved]: Please explain a greedy algorithm in a naive manner
Problem Detail: I am a beginner in the topic of algorithms. I have a query about Greedy Algorithms. From what I understand, if there is a function and we are supposed to find its maxima/minima, if we find the local maxima/minima, Read More …
[Solved]: Is the shadow ray in a Whitted ray tracer occluded by transparent objects?
Problem Detail: In a Whitted ray tracer, each ray-object intersection spawns a transmitted ray (if the object was translucent), a reflected ray and a shadow ray. The shadow ray contributes the direct lighting component. But what happens if the shadow ray Read More …
[Solved]: SAT not reducible to 2SAT
Problem Detail: Why is the reduction $textbf{SAT} leq_P textbf{3SAT}$ possible, but $textbf{SAT} leq_P textbf{2SAT}$ not possible, given, that $textbf{SAT}$ is $textbf{NP}$-complete, $textbf{2SAT} in textbf{NP}$ and $textbf{3SAT} in textbf{NP}$? Asked By : Anderson Answered By : mdxn I believe the asker is wanting to Read More …
