[algogeeks] Re: Matrix Searching

[Tushar]

For a large list of words,
"At each location, look 
for the character before/after that character in the word on opposite 
sides of the initial location, and continue from there"

Is it like:
frequency count of 'a' is smallest

'a' is in 2 words "available" and "alpha"

shall we check for 'v' near 'a'; if found then look for the complete word
OR
look for 'v' and 'i' on both sides of 'a'; if found then search for 
remaining characters in both directions
OR
look for 'l' and 'b' on both sides of 'a'; if found then search for 
remaining characters in both directions
OR
look for 'l' 'a'; if found then search for remaining characters in that 
direction
OR
look for 'h' 'a'; if found then search for remaining characters in that 
direction

Is this what we should be doing?

On Saturday, 15 September 2012 01:43:14 UTC+5:30, Don wrote:
>
> I had to do something like this with a large list of words to search 
> for. If you're just looking for one word, look for the first letter, 
> and when you find it, look at adjacent locations for the second 
> letter. If found, continue in that direction matching letters until 
> you either match the whole word or don't. 
>
> But for a big list of words to search for, it was faster to do 
> something like this: 
> Build a frequency count for each character, along with a list of 
> ordered pairs indicating where that character is located. Then, to 
> look for a word, find the character with the smallest frequency count 
> and step through the list for that character. At each location, look 
> for the character before/after that character in the word on opposite 
> sides of the initial location, and continue from there. 
>
> Don 
>
> On Sep 14, 2:47 pm, Arun Kindra  wrote: 
> > *You have given any n*n matrix in which characters are stored and you 
> have 
> > to search that a given word is present or not.(words can be 
> horizontally, 
> > vertically, diagonally)* 
>

-- 
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/-/tKJcCEYJsjAJ.
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] help to give DP solution

[Ravi Ranjan]

@atul

agreed with u dat it can be solved through hungarian method.. but what
about the condition a[i][i] entry is invalid
if all elements lie on diagonal n d sum is also maximum den a[i][i]
condition will be violated but Hungarian method still works

-- 
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.

[algogeeks] infibeam placement procedure

[saket]

some one with infibeam visited their college please tell their proceure and 
also give some questions asked in written and interviews .

-- 
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/-/BoXLkxnlckEJ.
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.

[algogeeks] infibea

[saket]

some one please tell infibeam recruitment process this year,also tell some 
questions if possible.

-- 
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/-/dVM0MrjRAmUJ.
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.

[algogeeks] Hackathon in NCR, Mid october register yourself now for the event

[Nitin Naresh]

we are hosting a hackathon in October 

12th  evening to 14th evening.

The theme is to develop something 

related to mobile. you can build 

anything from a construction app, to 

women security app on a mobile so its 

not a constraint but rather an enabler.

More Details at

http://www.opencoffeeclub.in/event/22

-- 
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/-/C7rfu9VmUFYJ.
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] help to give DP solution

[atul anand]

typo error :-
and each *row* *as cost

On Sun, Sep 16, 2012 at 12:44 AM, atul anand wrote:

> correct me if i am wrong ,
> it seems similar to Hungarian algorithm.
> here each column can be considered as persons P(p0,p1,p2,..pn) and each as
> cost of job say X(x0,x1,x2,x3,x4xn).
>  Hungarian algorithm tells how to find minimal but here its maximal...so i
> guess changes in the algo will give the outputl
>
>
> On Sat, Sep 15, 2012 at 9:10 PM, Rahul Kumar Patle <
> patlerahulku...@gmail.com> wrote:
>
>> A 2D array of order A[N][N] is given, considering entry A[i][i] as
>> invalid you have to select one element from each row such that
>> 1. Selected elements does not belong to same column.
>> 2. Sum of selected element has maximal.
>>
>>
>> --
>> Thanks and Regards:
>> Rahul Kumar 
>> Patle
>> M.Tech, School of Information Technology
>> Indian Institute of Technology, Kharagpur-721302, 
>> India
>> Mobile No: +91-8798049298, +91-9424738542
>> Alternate Email: rahulkumarpa...@hotmail.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.

Re: [algogeeks] help to give DP solution

[atul anand]

correct me if i am wrong ,
it seems similar to Hungarian algorithm.
here each column can be considered as persons P(p0,p1,p2,..pn) and each as
cost of job say X(x0,x1,x2,x3,x4xn).
 Hungarian algorithm tells how to find minimal but here its maximal...so i
guess changes in the algo will give the outputl

On Sat, Sep 15, 2012 at 9:10 PM, Rahul Kumar Patle <
patlerahulku...@gmail.com> wrote:

> A 2D array of order A[N][N] is given, considering entry A[i][i] as invalid
> you have to select one element from each row such that
> 1. Selected elements does not belong to same column.
> 2. Sum of selected element has maximal.
>
>
> --
> Thanks and Regards:
> Rahul Kumar 
> Patle
> M.Tech, School of Information Technology
> Indian Institute of Technology, Kharagpur-721302, 
> India
> Mobile No: +91-8798049298, +91-9424738542
> Alternate Email: rahulkumarpa...@hotmail.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.

Re: [algogeeks] Pivot postion of quick sort

[atul anand]

typo error :-
we can make it *independent** of this input format

On Sat, Sep 15, 2012 at 11:56 PM, atul anand wrote:

> pivot position plays important role in determining  the time complexity of
> the algorithm.
> suppose array is already sorted then if you go by obvious means by
> selecting pivot element as the 1st element of the input array,then
> recurrence will be :-
> T(n)=T(n-1)+theta(n)
> hence complexity of the algo will be O(n^2).
> actually if you form a recurrence tree you will see that it form like a
> skewed tree , so at every stage you are not dividing the problem into 2
> parts.
>
> if we are lucky we will have pivot element arnd the center of the
> array,now this will divided the problem into T(n/2)+theta(n) = nlogn.
>
> so suppose you are competing in sorting challenge and me as your opponent
> will give you sorted input so that i can get a plus point over your algo.
>
> so how can we avoid this ??
> now as  we know by now that time complexity is dependent on the input
> format(inc/dec order or nearly sorted).we can make it interdependent of
> this input format by randomizing the input sequence OR we select random
> pivot instead of selecting 1st element as pivot.
> This is know as randomized quick sort.now quicksort will no longer
> dependent on the input sequence but worst case complexity still remain
> O(n^2) , because if your random generator function given input as sorted
> sequence complexity still be O(n^2).
>
> On Sat, Sep 15, 2012 at 7:43 PM, sulekha metta wrote:
>
>> hi every one!!
>>  how does pivot position effect the efficiency in quick sort
>> algorithm
>>  thanks in advance
>>
>>  --
>> 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] Pivot postion of quick sort

[atul anand]

pivot position plays important role in determining  the time complexity of
the algorithm.
suppose array is already sorted then if you go by obvious means by
selecting pivot element as the 1st element of the input array,then
recurrence will be :-
T(n)=T(n-1)+theta(n)
hence complexity of the algo will be O(n^2).
actually if you form a recurrence tree you will see that it form like a
skewed tree , so at every stage you are not dividing the problem into 2
parts.

if we are lucky we will have pivot element arnd the center of the array,now
this will divided the problem into T(n/2)+theta(n) = nlogn.

so suppose you are competing in sorting challenge and me as your opponent
will give you sorted input so that i can get a plus point over your algo.

so how can we avoid this ??
now as  we know by now that time complexity is dependent on the input
format(inc/dec order or nearly sorted).we can make it interdependent of
this input format by randomizing the input sequence OR we select random
pivot instead of selecting 1st element as pivot.
This is know as randomized quick sort.now quicksort will no longer
dependent on the input sequence but worst case complexity still remain
O(n^2) , because if your random generator function given input as sorted
sequence complexity still be O(n^2).

On Sat, Sep 15, 2012 at 7:43 PM, sulekha metta wrote:

> hi every one!!
>  how does pivot position effect the efficiency in quick sort
> algorithm
>  thanks in advance
>
>  --
> 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.

[algogeeks] Pivot postion of quick sort

[sulekha metta]

hi every one!!
 how does pivot position effect the efficiency in quick sort
algorithm
 thanks in advance

-- 
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.

[algogeeks] help to give DP solution

[Rahul Kumar Patle]

A 2D array of order A[N][N] is given, considering entry A[i][i] as invalid
you have to select one element from each row such that
1. Selected elements does not belong to same column.
2. Sum of selected element has maximal.


-- 
Thanks and Regards:
Rahul Kumar Patle
M.Tech, School of Information Technology
Indian Institute of Technology, Kharagpur-721302,
India
Mobile No: +91-8798049298, +91-9424738542
Alternate Email: rahulkumarpa...@hotmail.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.