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 …
Category: Uncategorized
[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]: Equivalent Straight Line Embedding of a Planar Graph Drawing on a Grid
Problem Detail: An embedding of a graph G on a surface Σ is a representation of G on Σ in which points of Σ are associated to vertices and simple arcs are associated to edges in such a way that: the Read More …
[Solved]: Counting inversion pairs – $n^2$ results in $n log n$ time?
Problem Detail: The number of possible inversions in an array is bounded by $binom{n}{2}$, i.e $frac{n(n-1)}{2} in O(n^2)$. How it is possible to calculate $O(n^2)$ results in $O(nlog n)$ time using something like modified merge sort? (sample algo : http://www.geeksforgeeks.org/counting-inversions/). Asked Read More …
[Solved]: Decrease space complexity, how will time complexity increase?
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 …
[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 …
[Solved]: Asymptotic lower bound on the number of comparisons needed to find the intersection of unsorted arrays
Problem Detail: A homework problem in my current CS class asks us to produce a comparison-based procedure for taking (essentially—there are some poorly-specified rules about duplicates) the set intersection of $k$ unsorted arrays of at most $n$ elements each. For full Read More …
