Problem Detail: I was trying to look my book computer architecture and design, but I can not find the answer for this question. what are-the key-advantages of pipelining? Asked By : Aida Answered By : Illimitable I Googled your question and found this Read More …
Blog
[Solved]: Sort doubly linked list efficiently
Problem Detail: How efficiently can a doubly linked list be sorted? The minimum I could get is $O(n^2)$. Can anyone suggest something better? Asked By : Rishika Answered By : FrankW Mergesort keeps its $Theta(nlog n)$ worst case on linked lists. Double-linking can’t Read More …
[Solved]: Number of words in the regular language $(00)^*$
Problem Detail: According to Wikipedia, for any regular language $L$ there exist constants $lambda_1,ldots,lambda_k$ and polynomials $p_1(x),ldots,p_k(x)$ such that for every $n$ the number $s_L(n)$ of words of length $n$ in $L$ satisfies the equation $qquad displaystyle s_L(n)=p_1(n)lambda_1^n+dots+p_k(n)lambda_k^n$. The language $L Read More …
[Solved]: How Dynamic programming can be used for Coin Change problem?
Problem Detail: As far as I can unserstand Dynamic programming stands simply for memoization (which is a fancy name for lazy evaluation or plain “caching”). Now, I read that there is we can reduce complexity of coin-change problem by truncating some Read More …
[Solved]: Is the halting problem specific to Turing machines?
Problem Detail: The proofs that the halting problem is undecidable seem to make very few assumptions about the kind of program/machine under consideration: just that the programs take one input and either loop or produce an output. Not just Turing machines Read More …
[Solved]: Is there a way to test if two NFAs accept the same language?
Problem Detail: Or at least generate a set of strings that one NFA accepts, so I can feed it into the other NFA. If I do a search through every path of the NFA, will that work? Although that will take Read More …
[Solved]: Can partial sorting help with lookup cost in arrays?
Problem Detail: Looking something up in an unsorted list is a task with time complexity $O(n)$. However, if the list is sorted, the time complexity is $O(log(n))$. That means it is sometimes worthwhile to sort an array. However, that is a Read More …
[Solved]: Splay tree with odd number of rotations
Problem Detail: When inserting an item into a splay tree, rotations are performed in pairs based on either a zig-zag or zig-zig pattern. When there is an odd number of rotations to be performed, one could either do the extra rotation Read More …
[Solved]: CLRS – Maxflow Augmented Flow Lemma 26.1 – don’t understand use of def. in proof
Problem Detail: In Cormen et. al., Introduction to Algorithms (3rd ed.), I don’t get a line in the proof of Lemma 26.1 which states that the augmented flow $fuparrow f’$ is a flow in $G$ and is s.t. $|fuparrow f’| =|f|+|f’|$ Read More …
[Solved]: difference between propagation speed and bandwidth in digital communication
Problem Detail: I want to know difference between propagation speed and bandwidth in digital communication.I know bandwidth is no of bits in one second and propagation speed of signal is distance traveled by signal is one second.Is there any relation between Read More …
