You can compute recursively as below:
We use f(n) to represent the number of comparisons which the
Quick-Sort algo needs to take running on an array of n elements.
Answer to question 1:
f(n) = 2 * f(n/2) + n
We can observe the following sequence of equations:
f(n) = 4 * f(n/4) + 2 * n/2 + n =
The question would be complete if we know what order of notation is
needed for solution.
On 23.08.2010 15:32, Chi Hoang wrote:
I don't think so, I've have wriiten a kart-trie:
http://sourceforge.net/projects/kart-trie which is basically a
patricia-tree or radix-tree. Such a tree has maximum
Just do a little changes on your given function, that may help you
understand it:
We denote the transformed function as heap_compare_new:
int heap_compare_new(priority_queue *q, int i, int count, int x)
{
if ((count = k) || (i q-n) return(k-count);
/* change */
if (q-q[i] x) {
count++;
/*
Let us assume that the point are given in the form of (x1,x2,xn).
where n 1 and n is a natural number. Let the given point P is (xp1,
xp2,, xpn). Then we have the following algorithm.
For each of the point K = (a1,a2,...an) do the following
1. Set d := sqrt [(a1-xp1)^2 + (a2-xp2)^2 + ...
On 2010-8-25 20:25, Terence wrote:
1. Calculate the length of both list (A, B).
2. Find the position in the longer list corresponding to the head of
shorter list, and copy the previous digits to output list C.
(Or for simplicity, appending 0 to the shorter list so as to get
the same
Sorry for the mistake of addition vs subtraction. See my previous post
for some clarifications on the addition procedure.
The procedure of subtraction is similar.
To calculate C=A-B:
1. Compare A and B, (first compare length. If length is equal, compare
the digits from first to last).
If
Guys the problem is similar to lcs with just a little difference that
here we don't have to maximize the lenght of subsequence but we have
to maximize the sum for a given number of elements(k) which should be
in non-decreasing order.
ex :
input : 6 4 2 7 5 8 7 8 k=4
output : 6+7+8+8=29
--
@anurag
I meant the sorting without using any auxiliary data structure .Also we
have to put the element in the tree and carry out a traversal for every
element we insert in the tree .This takes O(n*logn) time ,
If one can sort the elements using a stack in O(n) time , we better sort
with this
For the sequence ABCADGH ACDH is a subsequence..
On Wed, Aug 25, 2010 at 10:02 PM, Vikas Kumar dev.vika...@gmail.com wrote:
can you define what here subsequence means?
On Wed, Aug 25, 2010 at 9:32 PM, Rahul rv.wi...@gmail.com wrote:
@Jaswanth
It will be really kind if you will state the
can you please explain more in detail the logic for XORing the index.
On 22.08.2010 07:53, UMarius wrote:
@Nikhil : I considered the array to be a linked list. xoring the
indexes helps when you don't know how many elements you have.
Marius.
On Aug 22, 5:04 am, Nikhil
@ jashwant raj,rahul
i think we have to sort array in non-decreasing order e.g. increasing
order
1 way . 2,4,1,4,8,6,7,9 1,2,4,4,6,7,8,9 it will take max(nlogn)
time with best sorting algo... also if use counting sort it will take
(n+k) time
2.way else in unsorted array it will
@Anand, @Abhishek
Thanks for the code and discussion.
However I am not clear as to how the approach suggested is running in
O(n) time. We are dividing and calling bitonicmerge() on two parts
recursively. So this should run in O(n log n) time complexity as
shown below
T(n) = n/2 + 2T(n/2) = n/2
Let A[1..n] be an array such that the first (n − √n) elements are
already sorted
(though we know nothing about the remaining elements). Give an
algorithm that
sorts A in substantially better than (n log n) steps.
This question is from chapter 4 : Algorithm Design Manual by S Skiena
--
You
Give all possible methods to flatten a binary tree to a linked list.
for eg.
50
/ \
25 60
/ \ / \
530 55 75
should be flattened to 5-25-30-50-55-60-75
PS: note that the tree should be converted to the LL and no separate
LL should be formed.
--
You
Can't we use bubble sort on remaining elements?
On Thu, Aug 26, 2010 at 5:25 PM, sourav souravs...@gmail.com wrote:
Let A[1..n] be an array such that the first (n − √n) elements are
already sorted
(though we know nothing about the remaining elements). Give an
algorithm that
sorts A in
merge sort or quick sort or insert last root(n) element . This will take max
n time . now merge the last root(n) element with the starting element .this
will take n time . so final time complexity is nnlog(n)
Rahul
--
You received this message because you are subscribed to the Google
ooops wrong approach... :(
On Thu, Aug 26, 2010 at 10:44 PM, Naveen Kumar
naveenkumarve...@gmail.comwrote:
Can't we use bubble sort on remaining elements?
On Thu, Aug 26, 2010 at 5:25 PM, sourav souravs...@gmail.com wrote:
Let A[1..n] be an array such that the first (n − √n) elements are
I can only figure out the inorder traversal...
On Thu, Aug 26, 2010 at 9:59 AM, krazee koder aravindhr...@gmail.com wrote:
Give all possible methods to flatten a binary tree to a linked list.
for eg.
50
/ \
25 60
/ \ / \
5 30 55 75
should be flattened
Am 26.08.2010 18:59, schrieb krazee koder:
Give all possible methods to flatten a binary tree to a linked list.
for eg.
50
/ \
25 60
/ \ / \
530 55 75
should be flattened to 5-25-30-50-55-60-75
PS: note that the tree should be converted to the
No, you are wrong here.
The inorder sequence should be 5 - 25 - 30 - 50 - 55 - 60 -75.
The preorder sequence should be 50 - 25 - 5 - 30 - 60 - 55 - 75
The postorder sequence should be 5 - 30 - 25 - 55 - 75 - 60 - 50
Below is the analysis (from wikipedia):
To traverse a non-empty binary tree
@ bittu
input : 6 1 4 8 3 7k=2
output : 6 + 8 =14
it's not 7+8=15 which wud be the case if ul apply sorting and take k
largest elements.
if i got ur point correct.
Rahul Verma
NIT Allahabad
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks
At first, store the pointer to the first node in inorder traversal (in this
case 5) because its going to be the head of the list.
Then use the following logic.
flattenTree(TreeNode node) {
if (node is leaf node)
return node;
if (node.left exists) then
@Rahul
Agree with your approach. When you say merge the last root(n)
elements with the starting elements, it means you are doing something
like merge sort using an additional O(n) space. Correct me if I am
wrong. This should give O(n) overall time complexity.
How about an in - place approach?
how to rearrange the pointers ??
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more
Hi Sourav,
I will first inplace sort the last √n elements in O(n) and then merge the
two sorted arrays in O(n).
The only problem: O(n) merging will not be inplace.
On Thu, Aug 26, 2010 at 5:25 PM, sourav souravs...@gmail.com wrote:
Let A[1..n] be an array such that the first (n − √n) elements
@saurav
I dont think in place approach is possible . This will end up taking n^2
time .
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send
26 matches
Mail list logo
