Re: [algogeeks] Most Optimal Palindrome?

You don't need to reverse anything. You reverse half the number and then compare positions, why not just compare things straight away? Also note that your solution is not n/2. Should the length be n it would be at least n operations. n/2 to reverse half the string and then n/2 comparisons. However,

Re: [algogeeks] Re: I am developing a new algorithm constructing Suffix Array and I want some knowledge on genome

It's just a plain text file, use whatever text editor you like On 8 August 2014 10:42, wtx...@gmail.com wrote: > *I downloaded the file chr22.dna. I don't know what software should be > used to browse the contents and view its data pattern. This file is really > what I need to view its data pat

Re: [algogeeks] Re: I am developing a new algorithm constructing Suffix Array and I want some knowledge on genome

Almost certainly yes, but that website also gives the links to the files used in the benchmark. So you can just check yourself. On 8 August 2014 10:23, wtx...@gmail.com wrote: > Here is Google Suffix array testing result website. > > https://sites.google.com/site/yuta256/sais > > I want to know

Re: [algogeeks] Re: Implement lastindexofastring(String s1,String s2)

What I suggested is optimal and doesn't require you to reverse the strings. It's not hard to see that it takes O(n + m) which cannot be improved on. Additionally it works for any other search algorithm than KMP. On 7 April 2014 20:41, Dan wrote: > Depends on what language you are using??? > >

Re: [algogeeks] Implement lastindexofastring(String s1,String s2)

You barely have to modify the algorithm. Just store the index of the most recent occurrence instead of reporting it, then report whatever you have stored right at the end. On 2 April 2014 19:25, pawan yadav wrote: > Hi All, > How can we do the following problem in efficient way : > > Implement

Re: [algogeeks]

Because then it's not a random shuffle? If you randomly shuffle something the order you currently have should be just as likely as any other On 28 January 2013 12:29, shady wrote: > Why do we use Fisher Yates > algorithm

Re: [algogeeks] Re: Minimum sum of Array

How is it a huge improvement? Your O(SN) is the same time as the dynamic programming solution for 0-1 knapsack isn't it? On 8 January 2013 14:44, Don wrote: > Yes, that is true. However, trying to find the optimal partition is > equivalent to the 0-1 knapsack problem, which is exponential time.

Re: [algogeeks] Re: Printing all inversions in an array

Practical efficiency? If you want to print out n^2 things then you can't do it in less than n^2. If you can come up with an encoding that represents more than one inversion then great. However, that doesn't change the fact that you can't individually print out n^2 things in under n^2 time. Look up

Re: [algogeeks] Re: Printing all inversions in an array

That statement is only very superficially similar. Counting them is saying how many of them there are, it doesn't necessarily require you to look at/compute each one. So it is not the same as printing them. If you're saying I want to print out each inversion individually then it's going to be n^2

Re: [algogeeks] all subarray with sum zero

Because you sort the array you may have values such that the indices are in the wrong order e.g your 'end' position is less than your 'start' position. You need to check for this, however if you use an inplace sorting algorithm this becomes easier. Additionally you may have up to O(n^2) occurrences

Re: [algogeeks] Contiguous Sub sequence

in 0 or repeated elements... > correct me if i am wrong... > > On 9/2/12, atul anand wrote: > > @navin : hashMap can be used to do it in O(n) time. > > > > On 9/2/12, Carl Barton wrote: > >> Your approach sounds like the optimal (and linear) algorithm f

Re: [algogeeks] Contiguous Sub sequence

Your approach sounds like the optimal (and linear) algorithm for the submass finding problem. But if I recall correctly that only works in linear time if the input is entirely positive integers? Maybe I'm being stupid but wont checking that array be quadratic? On 2 September 2012 20:02, Navin Kuma

Re: [algogeeks] Contiguous Sub sequence

1. Calculate the sum of every prefix of the array O(n) 2. Store as pairs (sum, index) and sort by sum using a stable sort. Observation: Sum of every factor can be expressed as the difference between the sum of 2 prefixes. 3. for each entry search for the corresponding difference such the inde

Re: [algogeeks] TRIE problem

There's no reason why a trie or a tree node couldn't be used to 'represent' more than one word. Although you'd take a penalty in the complexity for searching etc. On 31 August 2012 15:33, Navin Kumar wrote: > Can we store multiple words in single TRIE node by using linked list or > some other da

Re: [algogeeks] O(n) solution is there or not!!

I still don't understand. There's far quicker suffix array construction algorithms than O(n^2 log n)? There's O(n) algorithms On 20 August 2012 23:27, pankajsingh wrote: > Thanks.carl and atul.!!.@carl-i got lgn due to string comparison sort > while making the suffix array..:) > > -- > You recei

Re: [algogeeks] O(n) solution is there or not!!

Yeah sorry, misread the question then had a quick attempt :) I don't see where you get the lg n from though. I didn't do any binary searches. On 19 August 2012 22:53, pankajsingh wrote: > @carl- got ur point..but complexity is more..suffix array takes > o(n^2lgn)..considering string comparisons

Re: [algogeeks] O(n) solution is there or not!!

Oh, I actually read the question totally wrong. I think this idea is linear, but it's late so I'm not sure. 1. Calculate suffix array and lcp array for the text. 2. Calculate the longest common prefix between your text and the first entry in your suffix array and initialise a variable called tota

Re: [algogeeks] O(n) solution is there or not!!

Or a suffix tree would work. Pre process it to answer Lowest common ancestor queries. On 19 August 2012 21:51, Carl Barton wrote: > Just calculating the suffix array solves the problem if you do it with the > LCP array as well. You don't need to 'use' the suffix array so

Re: [algogeeks] O(n) solution is there or not!!

Just calculating the suffix array solves the problem if you do it with the LCP array as well. You don't need to 'use' the suffix array so to speak. On 19 August 2012 21:45, pankajsingh wrote: > Is there any O(n) solution this question...I Cleared all the testcases but > my solution is not O(n) a

Re: [algogeeks] Re: Number Theory (Power of 3 )

ord size, extend the tables of powers > of 2 and of 3 and change the for loop limit. > > Dave > > On Dec 5, 9:36 am, Carl Barton wrote: > > Ah I see, in which case could you not generalise your solution for all > > integers? > > By taking into account the size

Re: [algogeeks] Re: Number Theory (Power of 3 )

for a solution using bit manipulation, and > modulus and division are arithmetic operations, not bit operations. > > Dave > > On Dec 5, 8:56 am, Carl Barton wrote: > > @Dave Yours only works for a certain subset of all possible powers or 3 > > doesn't it? So WgpShashank

Re: [algogeeks] Re: Number Theory (Power of 3 )

@Dave Yours only works for a certain subset of all possible powers or 3 doesn't it? So WgpShashank's would be more general? On 5 December 2011 14:30, Dave wrote: > @WgpShashank: Yours is an O(log n) solution. Mine is O(1). > > Dave > > On Dec 5, 6:21 am, WgpShashank wrote: > > @SAMMM have a lo

Re: [algogeeks] Re: Algm

Heapsort and any other comparison sort have a lower bound of O(nlogn). Radix sort gets around this as it isn't a comparative sorting algorithm. It instead groups numbers by their significant digits (keeping original order), normally by count sort as mentioned above. Applying this for each signific

Re: [algogeeks] Algm

Bit confused by your n^3. Could you clarify? In the mean time Radix is an O(n) sorting algorithm. Where n is the length of the array. On 14/11/2011, Vijay Khandar wrote: > Which is the sorting algm sorts the integers [1...n^3] in > O(n). > a)Heapsort > b)Quicksort > c)Mergesort > d)Ra

Re: [algogeeks] Algo for in-place Stack Reversal.

An in place algorithm is one which only uses a constant amount of extra memory. So recursion is a problem as it will use an implicit stack of size O(n) which is linear extra memory, not constant. On 7 October 2011 15:16, .itoa wrote: > But , let's say if we do by recursion , then could you expl

Re: [algogeeks]

Depends which quarter you're measuring. Bricks aren't a uniform cuboid so wont be 1kg per quarter On 16 August 2011 12:16, sukran dhawan wrote: > > which college are u from? > -- Forwarded message -- > From: ravinder s > Date: Tue, Aug 16, 2011 at 4:15 PM > Subject: [algogeeks]

Re: [algogeeks] Re: island puzzle

It's been posted quite a few times recently. Just check the mailing list. On 30 May 2011 18:46, himanshu kansal wrote: > guys wake up > > > On Fri, May 27, 2011 at 9:24 PM, himanshu kansal < > himanshukansal...@gmail.com> wrote: > >> a king has two sons eric and bob.he wants to divide hi

Re: [algogeeks] Test Cases

Don't really get the question On 10 May 2011 09:08, Akshata Sharma wrote: > write test cases for the division '/' operator.. > > -- > 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

Re: [algogeeks] Re: Sartaj Sahni ebook

Haha I was just joking around. No harm done. On 24 April 2011 11:37, D.N.Vishwakarma@IITR wrote: > @KK I have shared a link of sartaj sahni ebook wth you > > On Sun, Apr 24, 2011 at 4:06 PM, KK wrote: > >> @ Carl Barton: >> I also know that site... i wan

Re: [algogeeks] Sartaj Sahni ebook

No problem. http://www.amazon.co.uk/Data-Structures-Algorithms-Applications-Java/dp/0071169008/ref=sr_1_3?ie=UTF8&qid=1303586345&sr=8-3 On 23 April 2011 18:41, KK wrote: > Please give link to: > Data Structures,Algorithms and Applications by Sartaj Sahni... > or directly mail to me. > > -- > Yo

Re: [algogeeks] [brain teaser ] Math Prime number puzzle 15april

What do you mean by 'Whether it is true'? On 15 April 2011 09:41, Lavesh Rawat wrote: > * Puzzle * > * > * > *If 'a' is a prime number, then prove, that a*a+26 is NOT a prime number > (whether it is true).* > > *Update Your Answers at* : Click > Here

Re: [algogeeks] Re: Sort array with two subparts sorted

Very interesting link! As we only need to perform one merge we should be able to modify it to run in O(n) time? In a similar style as a strand sort? On 12 April 2011 22:55, hary rathor wrote: > > http://thomas.baudel.name/Visualisation/VisuTri/inplacestablesort.html > > > take a glance on this

Re: [algogeeks] Re: Sort array with two subparts sorted

quick sort is worst case O(n^2) On 12 April 2011 18:17, Akash Agrawal wrote: > since we are bubbling up, it's again is a O(n^2). > > Is there anything possible like O(n) in constant space. I tried on swapping > values but mees it somewhere... here are intermediate steps in my approach. > > > 1,

Re: [algogeeks] Re: Sort array with two subparts sorted

That's linear space, not constant space. Vaibhav's seems good for constant space solution On 12 April 2011 13:17, sravanreddy001 wrote: > Yes.. merge sort. > > O(n) to find the starting of 2nd sub-array. > and O(n) for the merge process (similar to last step in merge sort) > > O(n) > > On Apr 12

Re: [algogeeks] [brain teaser] 12april

Greater than, > On 12 April 2011 10:25, Lavesh Rawat wrote: > Mathematical Puzzle > > What mathematical symbol can be placed between 5 and 9, to get a number > greater than 5 and smaller than 9? > > *Update Your Answers at* : Click > Here

Re: [algogeeks] website feedback

Either way, it's a pretty boring idea. On 9 April 2011 16:06, hary rathor wrote: > is it not some kind of fishing page ? > > -- > 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

Re: [algogeeks] website feedback

So it will post to other people that I would love to do something? 2011/4/8 Seçkin Can Şahin > I developed a website/facebookapp. I would appreciate it if you could give > feedback about it. > > http://apps.facebook.com/wouldloveto/ > > -- > You received this message because you are subscribed t

Re: [algogeeks] [brain teaser ] 7april

As the fire burns it will spread to the east but burn out in the west, so he can move to the west of the island? On 7 April 2011 08:57, your name last name wrote: > > * Survive Fire in Island Puzzle * >> > > Answer: The Man can escape the fire if he goes to the west corner of the > island... as

Re: [algogeeks] Re: 28march

The question is to find the minimum number of races, so there is only one answer On 7 April 2011 06:40, Manish Pathak wrote: > There are two answers > > 11 and 7 > > > On Thu, Mar 31, 2011 at 12:23 PM, Abhishek Sharma > wrote: > >> @sourabh: could u please elaborate how u came to that conclus

Re: [algogeeks] i am new

Yes On 6 April 2011 11:36, a_SillyGuy wrote: > hi , > i've recently joined this group in a mood to master the algorithms. > Will someone tell ,weather i will be benifitted by this group or not. > ??? > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm

Re: [algogeeks] Re:

Haha On 3 April 2011 15:28, Arpit Sood wrote: > assignment problem ? haha > > > On Sun, Apr 3, 2011 at 7:16 PM, Dr. Deepak Garg wrote: > >> Beta, puchna hi tha, to mujhse puchte! >> Anyways, you will get the solution in tomorrow's lecture @1pm. >> I have gone through your profile. See me in my c

Re: [algogeeks] minimizes the average completion-time

Correct me but isn't this just a process scheduling problem and your solution is a shortest processing time schedule? It's a well research problem and there's plenty of papers on this if you google. On 1 April 2011 13:14, snehal jain wrote: > Suppose you are given a collection of n tasks that n

Re: [algogeeks] Are U a Student Must Read this Frwd This Please If u Like We R student like You TOO

Your link doesn't work and all the links on the top bar appear to lead to do nothing. Doesn't give a brilliant impression. On 30 March 2011 09:22, ArPiT BhAtNaGaR wrote: > NIT JAIPUR PRESENTS YOU > > KAMPUSATTACK.COM > > > Biggest Social Platform For Students by Student

Re: [algogeeks] [brain teaser ] 29march

Agreed, 122 On 29 March 2011 14:19, Kunal Yadav wrote: > 122 > > > 1, 2, 5, 14, 41, x Whats x ?? -- > Regards > Kunal Yadav > (http://algoritmus.in/) > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post

Re: [algogeeks] Re: How to check whether a language isTuring Complete?

ctions then h is defined by a > > composition iff h (x1,..., xn) = g (f1 (x1, .., xn), f2 (x1, ... , xn > ),..., > > fn (x1,..., xn)) > > > > The notion of computability is established by Churh-Turing thesis. I > believe > > our general computabi

Re: [algogeeks] Re: How to check whether a language isTuring Complete?

To elaborate why; if your language suffers from the halting problem then it's pretty safe to say it's turing complete and infinite loops would allow you to achieve that. On 27 March 2011 19:03, Carl Barton wrote: > If you're not concerned about being that formal then

Re: [algogeeks] Re: How to check whether a language isTuring Complete?

a practical > way of checking it > > On Mar 26, 7:40 pm, Carl Barton wrote: > > If it can simulate a universal turing machine then it is turing complete > > > > On 26 March 2011 22:34, Karthik Jayaprakash >wrote: > > > > > > > > > >

Re: [algogeeks] How to check whether a language isTuring Complete?

If it can simulate a universal turing machine then it is turing complete On 26 March 2011 22:34, Karthik Jayaprakash wrote: > Hi, > Is there a way to check that if a language is Turing complete? > > Thanks. > > -- > You received this message because you are subscribed to the Google Groups >

Re: [algogeeks] Merge K Sorted Array In to Single Array

k sorted array can be merged in linear time I believe. If we have K arrays FIRST, SECOND, ., Up to K and we keep k counters (i, j, , up to k), one for each list Simply check if FIRST[i] < SECOND[j], ., Up to K Put the smallest in the merged list and increment the counter of the list i

Re: [algogeeks] Thinktionary -- The social dictionary!

So, what is this? 2011/3/24 Seçkin Can Şahin > Hi guys, > I developed this website. Might be interesting for you! > > http://www.thinktionary.net > > Have fun! > Seckin John > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to

Re: [algogeeks] friend's finder

Are their any requirements on performance? On 22 March 2011 13:05, snehal jain wrote: > If you want to search for a friend on Facebook, what are the possible > strategies that you could use. You are a programmer and can also > access Facebook’s Social Graph API. Make your own assumptions. How >

Re: [algogeeks] How to print numbers from 1 to 100 without loop , without recursion , without #define statements , without goto statement

:D On 16 March 2011 18:35, gmagog...@gmail.com wrote: > printf("1 2 3 4 5 6 7 8 9 10 11 12 13..."); > > no loop, no recursion, no define, no goto. HAHA : ) > > > > On Wed, Mar 16, 2011 at 12:30 PM, Carl Barton > wrote: > >> @kumar You

Re: [algogeeks] How to print numbers from 1 to 100 without loop , without recursion , without #define statements , without goto statement

@kumar Your example is still recursion On 16 March 2011 16:46, kumar anurag wrote: > ok guys... > > > On Wed, Mar 16, 2011 at 9:54 PM, himanshu kansal < > himanshukansal...@gmail.com> wrote: > >> >> class arr >> {static int i; >> public: >> arr() >> { >> cout<> } >> }; >> int arr::i=1; >> >> int

Re: [algogeeks] Brainfuck compiler

t;> u can compile using gcc >> >> >> On Tue, Mar 15, 2011 at 9:12 PM, Carl Barton >> wrote: >> >>> Just out of interest. What are you planning to write in brainfuck? >>> >>> >>> On 15 March 2011 14:58, Natansh Verma wrote: >

Re: [algogeeks] Brainfuck compiler

Just out of interest. What are you planning to write in brainfuck? On 15 March 2011 14:58, Natansh Verma wrote: > I don't know about Windows 7, but there is an interpreter online, in case > you want one. > > http://brainfuck.tk/ > > > On Tue, Mar 15, 2011 at 5:15 PM, cegprakash wrote: > >> do a

Re: [algogeeks] Re: Serialization in BT

If it's in array representation the simplest way is just serialise the array? Linked i'd agree with snehal On 9 January 2011 11:54, juver++ wrote: > And this: > http://www.cs.usfca.edu/~galles/cs245/lecture/lecture9.pdf > > -- > You

Re: [algogeeks] Re: 1s and 0s

com/2010/12/sort-array-containing-1s-and-0s.html > > > On Wed, Dec 22, 2010 at 6:47 AM, Carl Barton > wrote: > >> Could be modelled as a deterministic finite statemachine to be checked in >> linear time. >> >> >> >> On 22 December 2010 07:47, snehal

Re: [algogeeks] Re: 1s and 0s

Could be modelled as a deterministic finite statemachine to be checked in linear time. On 22 December 2010 07:47, snehal jain wrote: > @above > nice approach :) > > > On Wed, Dec 22, 2010 at 1:06 PM, juver++ wrote: > >> Use bits manipulation tricks. >> 1. There is a way to remove a group of co