Re: [algogeeks] second smallest in array
http://ideone.com/FqnSq see the link for tournament method On Wed, Oct 24, 2012 at 5:12 PM, rahul sharma rahul23111...@gmail.comwrote: for this shall we process all items and parallely calculate first and second max. or tournament methos i best for thsi.. if tournament method is best can anybody provide me with code with tournament method to find second smallest.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: give the algo or program to find second largest element in a list using tournament method
can anybody tell why this code is not giving correct output for finding
second smallest using tournament method?
my approach is same as @Don approach
On Wed, Sep 5, 2012 at 12:16 PM, shashi kant shashiski...@gmail.com wrote:
Heap's good but the i think problem clearly mentions Tournament sort
use this
https://blogs.oracle.com/malkit/entry/finding_kth_minimum_partial_ordering
although you can do a Inplace tournament sort ...swapping the
corresponding elements
level 1. adjacent pairs
level 2: between pairs apart by 1 place n so on (2,4,8..)
until there is only one element left in there without a pair.this
gives u least element
Now instead of using a Multimap , use a simple array with size equal to
original array and store the element that defeated each corresponding
element.
Get all those elements defeated by the least element ... that number
should be of order O(n)
get the second least element out of it in O(n) time.
*Shashi Kant *
*Think positive and find fuel in failure*
http://thinkndoawesome.blogspot.com/
*System/Software Engineer*
*Hewlett-Packard India Software Operations.
*
On Wed, Sep 5, 2012 at 4:11 AM, Dave dave_and_da...@juno.com wrote:
@Don: Nope. Constructing a heap can be done in O(n). See, e.g.,
http://www.diku.dk/forskning/performance-engineering/Jesper/heaplab/heapsurvey_html/node9.html
.
Dave
On Tuesday, September 4, 2012 10:24:25 AM UTC-5, Don wrote:
Constructing a max-heap is O(n*log n)
However, the problem asked for a solution using tournament method.
If you ignore that requirement, an O(n) solution is trivial, and
doesn't require the additional storage of a heap:
int first = max(A[0], A[1]);
int second = min(A[0], A[1]);
for(i = 2; i N; ++i)
{
if (A[i] = first)
{
second = first;
first = A[i];
}
else if (A[i] second)
second = A[i];
}
// First and second now contain 1st and 2nd largest values in A
Don
On Sep 3, 5:04 am, bharat b bagana.bharatku...@gmail.com wrote:
Construct a max-heap -- O(n)..
call delete() 2 times .. -- O(logn)..
=== O(n) time..
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/bKzs-wHLSoIJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
//To implement tournament code...
#includeiostream.h
#includemath.h
#define size 10
class node
{
public:
char c;
int freq;
int beaten;
node *left,*right;
node *parent;
node(char c1=0,int freq1=0,node *l=0,node *r=0)
{
c=c1;
freq=freq1;
left=l;
right=r;
beaten=freq1;
}
};
class array
{
public:
node *root;
array()
{
root=0;
}
int size1;
int heapsize;
int length;
node *b[size];
node *a[size];
void insert();
void buildheap();
void minheapify(int i);
node* extractmin();
void heapinsert(node *p);
void tour();
void display();
void display1(node *);
void decrease(int i);
void traverse()
{
traverse(root);
}
void traverse(node*);
void minimum();
int left(i)
{
return 2*i;
}
int right(i)
{
return 2*i+1;
}
};
//Min heap
void array::buildheap()
{
heapsize=length;
for(int i=(floor(length/2));i=1;i--)
{
minheapify(i);
}
}
void array::minheapify(int i)
{
int l,r,smallest;
node *temp;
l=left(i);
r=right(i);
if(l=heapsize a[l]-freq a[i]-freq)
{
smallest=l;
}
else
{
smallest=i;
}
if(r=heapsize a[r]-freq a[smallest]-freq)
{
smallest=r;
}
if(smallest!=i)
{
temp=a[i];
a[i]=a[smallest];
a[smallest]=temp;
minheapify(smallest);
}
}
void array::heapinsert(node* k)
{
heapsize=heapsize+1;
a[heapsize]=k;
decrease(heapsize);
}
void array::minimum()
{
couta[1];
}
node* array::extractmin()
{
node* min;
if(heapsize1)
return 0;
min=a[1];
a[1]=a[heapsize];
heapsize=heapsize-1;
minheapify(1);
return min;
}
void array::decrease(int i)
{
node* temp;
while(i1
Re: [algogeeks] Re: give the algo or program to find second largest element in a list using tournament method
@Darpan can you implement it without using the multimap and with the same
(divide and conquar) approach.
On Mon, Sep 3, 2012 at 6:25 PM, Darpan Baweja darpan.bav...@gmail.comwrote:
hope this might helps
code:- http://ideone.com/mtHem
used divide and conquer approach
and stored all the beaten elements in the multimap with key is the element
which has beaten them
with key as winner return maximum element stored in multimap
On Mon, Sep 3, 2012 at 3:31 PM, sangeeta goyal sangeeta15...@gmail.comwrote:
@bharat is it tournament method??
On Mon, Sep 3, 2012 at 2:34 PM, bharat b bagana.bharatku...@gmail.comwrote:
Construct a max-heap -- O(n)..
call delete() 2 times .. -- O(logn)..
=== O(n) time..
On Fri, Aug 31, 2012 at 1:46 AM, Don dondod...@gmail.com wrote:
While the list length is more than one
Take 2 elements from the head
Select the larger of the two
If the smaller is greater than the largest beaten by the larger
Then set the largest beaten by the larger to the value of
the smaller
Add the larger to the tail of the list
When this completes, you'll have one element containing the largest
and second largest values.
typedef struct
{
unsigned int value;
unsigned int largestBeaten;
} element;
unsigned int secondLargest(queueelement elements)
{
while(elements.length() 1)
{
element A = elements.dequeue();
element B = elements.dequeue();
if (A.value B.value) swap(A,B);
if (A.largestBeaten B.value) A.largestBeaten = B.value;
elements.enqueue(A);
}
return queue.head().largestBeaten;
}
On Aug 30, 12:53 pm, sangeeta goyal sangeeta15...@gmail.com wrote:
@Don can you give the algorithm for the same??
how would you implement it??
On Thu, Aug 30, 2012 at 10:03 PM, Don dondod...@gmail.com wrote:
The second largest element is the largest element beaten by the
winner.
So if you implement a tournament in which each element keeps track
of
the largest element it has beaten, you'll get the second largest
naturally.
Don
On Aug 29, 9:15 am, Sangeeta sangeeta15...@gmail.com wrote:
give the algo or program to find second largest element in a list
using
tournament method
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*DARPAN BAWEJA*
*Final year, I.T*
*NIT Allahabad*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: give the algo or program to find second largest element in a list using tournament method
@Don nice solution using max heap.it is very simpler to understand
On Tue, Sep 4, 2012 at 8:54 PM, Don dondod...@gmail.com wrote:
Constructing a max-heap is O(n*log n)
However, the problem asked for a solution using tournament method.
If you ignore that requirement, an O(n) solution is trivial, and
doesn't require the additional storage of a heap:
int first = max(A[0], A[1]);
int second = min(A[0], A[1]);
for(i = 2; i N; ++i)
{
if (A[i] = first)
{
second = first;
first = A[i];
}
else if (A[i] second)
second = A[i];
}
// First and second now contain 1st and 2nd largest values in A
Don
On Sep 3, 5:04 am, bharat b bagana.bharatku...@gmail.com wrote:
Construct a max-heap -- O(n)..
call delete() 2 times .. -- O(logn)..
=== O(n) time..
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: give the algo or program to find second largest element in a list using tournament method
@bharat is it tournament method??
On Mon, Sep 3, 2012 at 2:34 PM, bharat b bagana.bharatku...@gmail.comwrote:
Construct a max-heap -- O(n)..
call delete() 2 times .. -- O(logn)..
=== O(n) time..
On Fri, Aug 31, 2012 at 1:46 AM, Don dondod...@gmail.com wrote:
While the list length is more than one
Take 2 elements from the head
Select the larger of the two
If the smaller is greater than the largest beaten by the larger
Then set the largest beaten by the larger to the value of
the smaller
Add the larger to the tail of the list
When this completes, you'll have one element containing the largest
and second largest values.
typedef struct
{
unsigned int value;
unsigned int largestBeaten;
} element;
unsigned int secondLargest(queueelement elements)
{
while(elements.length() 1)
{
element A = elements.dequeue();
element B = elements.dequeue();
if (A.value B.value) swap(A,B);
if (A.largestBeaten B.value) A.largestBeaten = B.value;
elements.enqueue(A);
}
return queue.head().largestBeaten;
}
On Aug 30, 12:53 pm, sangeeta goyal sangeeta15...@gmail.com wrote:
@Don can you give the algorithm for the same??
how would you implement it??
On Thu, Aug 30, 2012 at 10:03 PM, Don dondod...@gmail.com wrote:
The second largest element is the largest element beaten by the
winner.
So if you implement a tournament in which each element keeps track of
the largest element it has beaten, you'll get the second largest
naturally.
Don
On Aug 29, 9:15 am, Sangeeta sangeeta15...@gmail.com wrote:
give the algo or program to find second largest element in a list
using
tournament method
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: give the algo or program to find second largest element in a list using tournament method
@Don can you give the algorithm for the same?? how would you implement it?? On Thu, Aug 30, 2012 at 10:03 PM, Don dondod...@gmail.com wrote: The second largest element is the largest element beaten by the winner. So if you implement a tournament in which each element keeps track of the largest element it has beaten, you'll get the second largest naturally. Don On Aug 29, 9:15 am, Sangeeta sangeeta15...@gmail.com wrote: give the algo or program to find second largest element in a list using tournament method -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Dynamic programming problem
give explaination On Fri, Dec 16, 2011 at 11:14 AM, atul anand atul.87fri...@gmail.comwrote: use dynamic programming to solve this problem :- here is the algo:- result[S]; result[0]=1; index; for i=0 to len(coins[]) c=coins[i]; for k=c to S index=k-c; result[k]= result[k] + result[index]; end end print result[S]; On Fri, Dec 16, 2011 at 10:52 AM, Sangeeta sangeeta15...@gmail.comwrote: Given a list of N coins, their values (V1, V2, ... , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want), or report that it's not possible to select coins in such a way that they sum up to S. For a better understanding let's take this example: Given coins with values 1, 3, and 5. And the sum S is set to be 11. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] request of ebook..(Data Structures and algorithms made easy:)
i also need that book On Mon, Sep 26, 2011 at 6:00 AM, Amit Mittal amit.mitt...@gmail.com wrote: plz send me that book too On Mon, Sep 26, 2011 at 3:28 PM, Ishan Aggarwal ishan.aggarwal.1...@gmail.com wrote: plz send me that book to I also need that book... On Sun, Sep 25, 2011 at 9:37 PM, sarath prasath prasathsar...@gmail.comwrote: hi every one.. pls do give me the link if u find or have, about this book.. title name:Data Structures and Algorithms Made Easy: 700 Data Structure and Algorithmic Puzzles author:Narasimha Karumanchi ISBN-10: 145654988X ISBN-13: 978-1456549886 publisher:careermonk.. pls do send to this email id...prasathsar...@gmail.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Kind Regards Ishan Aggarwal [image: Aricent Group] Presidency Tower-A, M.G.Road,Sector-14 Gurgaon,Haryana.122015 INDIA Phone : +91-9654602663 ishan2.aggar...@aricent.com puneet.ar...@aricent.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] c doubt
thnx all...i got it :) On Thu, Jul 14, 2011 at 2:13 AM, Anika Jain anika.jai...@gmail.com wrote: As in base 10 we say 552.5 is same as 5.525 *10^2 , here 2 is the exponent of base 10.. so similarly in binary nos. for base 2 here if i make 101.00110011.. to 1.0100110011.. *2^2 my exponent is 2.. now in storage of floats exponent is stored as exponent +127 i.e here 2 +127 so we get 1001 On Thu, Jul 14, 2011 at 2:03 AM, Kamakshii Aggarwal kamakshi...@gmail.com wrote: @anika:can u please explain the meaning of this line.. so i here get an exponent of 2 as 2 here.. now in exponent 8 bits this exponent is stored as 127+exponent so here it becomes 1001.. On Wed, Jul 13, 2011 at 11:44 PM, Piyush Kapoor pkjee2...@gmail.comwrote: thanks,i hv just entered 2nd year,so most probably i will study this year -- *Regards,* *Piyush Kapoor,* *CSE-IT-BHU* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards, Kamakshi kamakshi...@gmail.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] c doubt
thanx i got it :)
On Mon, Jul 4, 2011 at 2:05 PM, Sandeep Jain sandeep6...@gmail.com wrote:
If you try to visualize the internal representation.
You've allocated 10 bytes.
| h | e | l | l | o |
| h | i |\0 |\0 |\0 |
Since these are stored in linear form, so the actual representation would
be
| h | e | l | l | o | h | i |\0 |\0 |\0 |
Now a[0] points to 'h' in the first row, and printf starts to print
characters one by one till it finds null, i.e. \0
Thus it prints from hellohi
And similarly printing a[1] prints only hi
Regards,
Sandeep Jain
On Mon, Jul 4, 2011 at 1:48 PM, Sangeeta sangeeta15...@gmail.com wrote:
#includestdio.h
#includestring.h
void main()
{
char a[2][5]= {
hellodear,
hi};
printf(%s%s,a[0],a[1]);
}
output:hellohi hi
explain?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
