Question Detail: Most probably, this question is asked before. It’s from CLRS (2nd Ed) problem 6.5-8 — Give an $O(n lg k)$ time algorithm to merge $k$ sorted lists into one sorted list, where $n$ is the total number of elements Read More …
Blog
Difference between cross edges and forward edges in a DFT
Question Detail: In a depth first tree, there are the edges define the tree (i.e the edges that were used in the traversal). There are some leftover edges connecting some of the other nodes. What is the difference between a cross Read More …
Why can’t DFS be used to find shortest paths in unweighted graphs?
Question Detail: I understand that using DFS “as is” will not find a shortest path in an unweighted graph. But why is tweaking DFS to allow it to find shortest paths in unweighted graphs such a hopeless prospect? All texts on Read More …
Algorithm that finds the number of simple paths from $s$ to $t$ in $G$
Question Detail: Can anyone suggest me a linear time algorithm that takes as input a directed acyclic graph $G=(V,E)$ and two vertices $s$ and $t$ and returns the number of simple paths from $s$ to $t$ in $G$. I have an Read More …
Getting negative cycle using Bellman Ford
Question Detail: I have to find a negative cycle in a directed weighted graph. I know how the Bellman Ford algorithm works, and that it tells me if there is a reachable negative cycle. But it does not explicitly name it. Read More …
When can a greedy algorithm solve the coin change problem?
Question Detail: Given a set of coins with different denominations $c1, … , cn$ and a value v you want to find the least number of coins needed to represent the value v. E.g. for the coinset 1,5,10,20 this gives 2 Read More …
The convoy effect in process scheduling
Question Detail: As I understand the convoy effect, in the context of vehicular traffic in a road system. A slow moving group of vehicles passes through the system, slowing traffic even in areas which were not directly affected by the convoy. Read More …
Regular expression for the strings without a particular substring
Question Detail: How can we design a regular expressions without particular substrings. The goal of this is to create language L which won’t contain a particular substring (i.e. 110) for the case of a regular expression without substring $110$, I Was Read More …
Why does randomized Quicksort have O(n log n) worst-case runtime cost?
Question Detail: Randomized Quick Sort is an extension of Quick Sort in which pivot element is chosen randomly. What can be the worst case time complexity of this algo. According to me it should be $O(n^2)$. Worst case happens when randomly Read More …
Performance differences between Go-Back-N and Selective Repeat ARQ protocols?
Question Detail: This is what I know: GBN weakness is the fact that when the window size is too large, the number of packets in the pipeline grows and one packet error causes the retransmition of many packets unnecessarily. Selective Repeat Read More …
