Problem Detail: I’m confused about the complexity of the following code: for(i=1; i<=n; i = 2*i) for(j=1; j<=i; j++) print A[j] I know that the first loop is logn, but I’m confused on what the second for loop would be since Read More …
Category: Uncategorized
[Solved]: What specifically makes quantum computers useful?
Problem Detail: I know that quantum computers are able to process a superposition of all possible states with a single pass through the logic. That seems to be what people point to as being what makes quantum computers special or useful. Read More …
[Solved]: Difference between virtual memory and job pool
Problem Detail: Both virtual memory and job pools store the processes temporarily on disk and bring them to memory at some later stage, so what is the actual difference in between them? What I guess is that when a process is Read More …
[Solved]: Runtime of the optimal greedy $2$-approximation algorithm for the $k$-clustering problem
Problem Detail: We are given a set 2-dimensional points $|P| = n$ and an integer $k$. We must find a collection of $k$ circles that enclose all the $n$ points such that the radius of the largest circle is as large Read More …
[Solved]: Sort deck of cards with least no of moves
Problem Detail: We have n cards with each card numbered from 1 to n. All cards are randomly shuffled but all cards are visible We are allowed only operation MoveCard(n) which moves the card with value n to the top of Read More …
[Solved]: Time complexity of an enumeration of SUBSET SUM instances
Problem Detail: An instance of the SUBSET SUM problem (given $y$ and $A = {x_1,…,x_n}$ is there a non-empty subset of $A$ whose sum is $y$) can be represented on a one-tape Turing Machine with a list of comma separated numbers Read More …
[Solved]: Prove the red blue separation problem is NP-complete
Problem Detail: Consider the following problem: given a set of $m$ red points and $n$ blue points in the plane, find a minimum length cycle that separates the red points from the blue points. That is, the red points are inside Read More …
[Solved]: Smallest(k) in red-black tree. How is it O(logn)?
Problem Detail: Is it the same as find minimum for a binary search tree? I know recoloring runs in O(logn) and rotations are O(1). Even if we are wanting it to find the ‘k-th’ smallest key in the red-black tree. Could Read More …
[Solved]: NP-complete decision problems – how close can we come to a solution?
Problem Detail: After we prove that a certain optimization problem is NP-hard, the natural next step is to look for a polynomial algorithm that comes close to the optimal solution – preferrably with a constant approximation factor. After we prove that Read More …
[Solved]: Every graph with $delta(G) ge 2$ has a cycle of length at least $delta(G)+1$?
Problem Detail: I’m reading up on graph theory using Diestel’s book. Right on the outset I got confused though over proposition 1.3.1 on page 8 which reads: Proposition 1.3.1. Every graph G contains a path of length $delta(G)$ and a cycle Read More …
