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

[Dan]

Depends on what language you are using???

Fortran has this capability built directly into it's standard Index() 
routine ( ie.  it does what you might call a 'backwards' search).   I 
imagine other languages have a similar capability.  If not,  and the 
strings are not huge memory hogs...  or if you are ok with overwriting your 
original string, s1 in the process:

Invert both strings.ie   rearrange them such that the last letter of 
each string becomes the first, etc., etc.

Then use your languages normal INDEXED type of search.

Otherwise,  you'll just have to do an Indexed search repeatedly to find the 
last occurrence...  or...  write your own special Index function.  I'm not 
sure what the fastest search algorithm is for that.  I seem to remember 
reading up on it a long time ago.  It's not a brute force method if I 
recall correctly.

Dan   :-)

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

[algogeeks] Re: strictly sorting by adding or subtracting a range of numbers

[Dan]

I just stumbled upon this one (I know, a little late).  At least this 
way...  it's too late to be helpful if it was a Homework assignent.  :-)

This is one of those problems that, at first, appears difficult,  but , 
upon closer inspection, turns out to have a very straight forward 
(elegant?) solution.

Take any two adjacent values from the list...  call them  a  &   b

In the worst case scenario,  the value of   a  is higher than the value of 
b... a > b

Therefore,   we need an  X  value that solves the inequality   a - X  < 
  b + X

Rearrange this  equation just slightly to another equivalent equation...   
a - b  <  2X

This indicates that a slightly different (but, still equivalent) problem 
can be solved to arrive at a correct solution.

Only allow values from 0 to 2X,  [0,2X]  to be added to the original values 
in the array (ie. no subtractions).  This simplifies things greatly and 
allows for a clear algorithm solution that can be easily performed in a 
single pass through the array.  Essentially, you find a value of 2X that 
works... then divide that in half, and convert the resulting float type 
value to a whole integer value to get the final  X value that solves the 
'original' problem statement.
 
The fortran code below has been tested and appears to work just fine.
The real algorithm of note is the function routine:*FUNCTION 
TransformArray( v ).*
Note that the important code is only 7 simple lines long and should
be easy to recode in most any language.
It runs extremely fast,  even for array sizes of 1.
There's also 'fluff' code here, written to test multiple test sets to check 
the value of X arrived and to time everything. at is the desired answer.

Does anyone know of any Practical applications for this algorithm??  I'm 
guessing it's just an interesting problem.

Dan:-)

Module Transform

  Contains






*   Function TransformArray( v )   Result(x)   
!---   ! Find a minium X 
value to transform the array, v(:)   ! Transformed array values can be 
negative.  It is a trivial task to   ! alter this to guarantee no negative 
values in the transformed array.   
!---*
   Integer, intent(in)  :: v(:)
   Integer  :: x
   Integer  :: i, b
   x = 0
   b = v(1)
   Do i = 2, Size(v)
  b = Max( b+1,   v(i) )
  x = Max(  x , b-v(i) )
   End Do
   x = Ceiling( x/2.0 )  ! smallest integer greater/equal to the 
value.
*   End Function TransformArray*


   Subroutine Validate_X( v, x )
   !-
   ! Given a value of x, see if the array can be successfully transformed
   ! This is merely code to see if the X value arrived at is correct.
   !-
   Integer, intent(in)  :: v(:)
   Integer, intent(in)  :: x
   Integer, allocatable :: vt(:), xt(:)
   Integer  :: i, n

   n = Size(v)
   Allocate( vt(n), xt(n) )

   vt(1) = v(1) - x
   xt(1) = -x

   Do i = 2, n
  vt(i) = Max( vt(i-1)+1, v(i)-x )
  xt(i) = vt(i)-v(i)
   End Do

   write(*,'(a,2i6)')  '  v = ', v
   write(*,'(a,2i6)')  ' xt = ', xt
   write(*,'(a,2i6)')  ' vt = ', vt

   If(   Any( abs(xt) > x )   ) Then
  write(*,'(a)' )  ' A higher x value was required during the 
transformation.'
  write(*,'(a,i0,a)')  ' X = ', x,  '  does not work.'
   End If

   If(  Any( vt(1:n-1) >= vt(2:n) )   ) &
   write(*,'(a)')  ' ERROR: Transformed array is not in "Strictly 
Ascending" order!'

   End Subroutine Validate_X

End Module Transform



Program Main
!--
Use Transform
Implicit None
Integer, parameter   :: nmax=1
Integer  :: n, x
Integer, allocatable :: v(:)
Real,allocatable :: r(:)
Integer  :: it1, it2

Allocate( v(nmax), r(nmax) )

call timer(it1)
write(*,*)
write(*,*) 'Test Case #1:  array size = 5,  Easy to check'
n = 5
v(1:n) = (/5,4,3,2,8/)
Call Solve_for_X()
write(*,*) '--'

write(*,*)
write(*,*) 'Test Case #2  array size = 8,  Easy to check'
n = 8
v(1:n) = (/8,12,7,15,10,20,12,16/)
Call Solve_for_X()
write(*,*) ''

write(*,*)
write(*,*) 'Test Case #3:  array size = 1  w/ random array values up to 
999'
n = 1
Call Random_Seed()
Call Random_Number( r(1:n) )
v(1:n) = 1 + Int(999*r(1:n))
Call Solve_for_X()
write(*,*) ''

call timer(it2)
write(*,*) 'Total time = ', Real(it2-it1)/100.0

Contains

   Subroutine Solve_for_X()
   !
   x = Trans

[algogeeks] Re: Pointers Usage

[Dan]

On Tuesday, January 1, 2013 12:05:31 PM UTC-8, shady wrote:
>
> Why do we use pointers at all considering space as a factor other than 
> allocating memory dynamically does it have any other use ?
>
> to store an integer
> (int *) = 8 bytes, and while making it point to an integer location would 
> cost another 4 bytes, total = 12 bytes ... compared to directly taking 
> (int) = 4 bytes
>

Well..  you don't necessarily need them for speed or for dynamic management 
of memory or for most things.   However, it depends on what language you 
are using.  Keep in mind that the term 'pointer' is used in slightly 
different ways depending on the language you are using.

There are algorithms where pointers may be quite useful and there are 
algorithms where they make the code much more complicated and provide no 
real benefit.  One example where they 'might' be useful would be in the 
solution of a set of linear equations where the coefficient matrix which 
represents the values in the equations is sparse (ie. lots of zeros).  You 
could use a very simple solution scheme where you store all of your 
coefficients in a very simple rectangular matrix.  In this case, the use of 
pointers will get you nowhere. If your equations aren't too big, the use of 
pointers here will probably make your algorithm slower.   However,  for 
large equations,  your memory usage may be off the charts (say 1 million 
equations with 1 million coefficients per equation).   Now,  since the 
majority of your coefficients are going to be zeros...  you can save a LOT 
of memory by not having to allocate memory for each coefficient.   Your 
solution algorithm will be more complicated now.   However, by using 
pointers to point at the non-zero coefficients,  you'll save a lot of 
memory and you'll also cut down on the actual math your algorithm has to 
perform.  Pointers aren't necessarily needed here either, though, they 
often are used in this situation.  So...  in this case,  the pointers make 
your problem solvable.  Though,  you still have to deal with a more 
complicated algorithm,  it's worth it simply because a simpler algorithm 
just isn't tractable.

As another example  think of Linked List.  These can be built without 
pointers also.   However,  they tend to be simpler with pointers.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[algogeeks] Re: find point lies in side circle

[Dan]

On Jan 5, 4:17 am, dabbcomputers  wrote:
> you are given with N points on graph. and a point A on graph and range
> R you have to find the points that lies within the radius of R from
> point A. with complexity less than O(N).

Why does it have to be done with less complexity than O(N) ?
O(N) certainly doesn't mean it will run faster.

You "appear" to know more about the problem than you have stated???
You're not going to get good answers to your question unless you give
more information on your problem and what your goals are.  Finding an
O(N) algorithm doesn't mean much in the real world unless it results
in a faster running and/or more memory efficient algorithm.

Based on the info you've given so far  you need to check every
single point.  "O(N) or not" is irrelevant.   Is there some order to
your points that will allow you to trivially discard them from needing
to be checked?   Does your graph structure tell you anything about the
location of your points in 2D or 3D space (other than, that they may
be interconnected )?   Do you have more than a hundred thousand
points?  Do you need to perform this checking operation often (in a
loop) or only once?  If you don't have that many points...  the
simplest and arguably the best algorithm is the one that has the
simplest and easiest to understand coding by an average programmer.

These are just my thoughts for whatever they're worth,
Dan  :-)

-- 
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] Re: NULL pointer

[Dan]

Just FYI,

You need to (and "should" always) be specific.  Many languages have
pointers.  Many do not.  Of those that do...  pointers don't work the
same way in each of them.  Even the concept of what a pointer is can
vary a bit.So...  always state which specific programming language
you are talking about in your questions & comments.

Dan  :-)


On Nov 14, 1:52 pm, UTKARSH SRIVASTAV  wrote:
> is subtraction of two NULL pointers defined ?
>
> --
> *UTKARSH SRIVASTAV
> CSE-3
> B-Tech 3rd Year
> @MNNIT 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.

[algogeeks] Re: Intersection of arrays

[Dan]

Hashing all of the K arrays seems like a bit much.   How about this?

You have  K  seperate arrays to start with,  each array having N
elements (is that correct?).

1)  Sort the first array.

2)  Step through the 2nd array, 1 element at a time  say
Array(2).element(i)
 Check to see if the value of  Array(2).element(i) is in the first
sorted array.
 If it is,  add this numeric value to your list of  "intersection
elements".

 As you pass through all elements of the 2nd array,  the values
found which
 are intersecting need to be saved  ( maybe in the 1st arrays
space to save
  memory).   Ideally, these should be saved in sorted order as
they are found.

 ( how you store the sorted array will affect speed of this check
of course.
   I'd keep it simple on the 1st round, then optimize the code
once everything
   appears to be working well, ie with buckets or pointers or
whatever.  How
   you determine if an element in array 2 intersects with an
element of array
   1 will depend on how you store your sorted array.  You might do
a linear
   search or a binary search or a bucket search of some sort ).

3)  Now...  step through the 3rd array,  1 element at a time,  looking
to see if each
value is in the  just created  list  of   "intersection elements"

4)  Do the save thing now with each of the remaining original K
arrays.

Dan:-)



On Oct 24, 10:17 pm, kumar raja  wrote:
>  Find intersection of K unsorted array of N elements each. Intersection
> consists of elements that appear in all the K arrays.
>
> what data structure is useful here??
>
> --
> Regards
> Kumar Raja
> M.Tech(SIT)
> IIT Kharagpur,
> 10it60...@iitkgp.ac.in

-- 
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] Re: Inplace Array Convertion

[Dan]

I have a hard copy of the book (years back,  I implemented a fortran
version of the algorithm described in the book).  I don't know if you
can find an online version or not.  I'm sure there is stuff there.
Have you done a simple Google search for "in place reorder
array"  ??   It's not a difficult algorithm.  And Sedgewicks's books
are well known.  Searches for his name may also yield results.

Just FYI:  If your rearrangement doesn't have to be in-place...  you
will achieve more speed by other methods.  I did testing with
rearrangement of some very large data sets.  The in-place method was
noticeably slower.  It also required you to write your own routine to
do the reordering.  Using basic fortran, I could do the same thing in
just one or two lines of very simple code.  The only advantage to the
in-place algorithm is that it uses less memory.   This should only be
important if you are dealing with some very large arrays.

Dan   :-)


On Oct 14, 9:44 pm, Ankur Garg  wrote:
> @Dan ..can you post the algo here or link to the book??
> @Anika ...yes please post the code here..but please explain a bit about
> underlying algo ...(algo is more important than actual code )
>
>
>
>
>
>
>
> On Sat, Oct 15, 2011 at 1:54 AM, Dan  wrote:
> > On Oct 13, 7:52 pm, "shiva@Algo"  wrote:
> > > Convert an array "a1 a2 a3...an b1 b2 b3...bn c1 c2 c3...cn" to "a1b1c1
> > > a2b2c2...anbncn", inplace
>
> > See the algorithm for memory efficient rearrangement of array elements
> > in one of the books by Robert Sedgewick such as Algorithms in C++ or
> > Algorithms in Pascal, etc.
>
> > Dan
>
> > --
> > 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] Re: Inplace Array Convertion

[Dan]

On Oct 13, 7:52 pm, "shiva@Algo"  wrote:
> Convert an array "a1 a2 a3...an b1 b2 b3...bn c1 c2 c3...cn" to "a1b1c1
> a2b2c2...anbncn", inplace


See the algorithm for memory efficient rearrangement of array elements
in one of the books by Robert Sedgewick such as Algorithms in C++ or
Algorithms in Pascal, etc.

Dan

-- 
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] Re: content extraction

[Dan]

Pick a language to work in.
Open the file in whatever way your language of choice allows.
Read the data.
And...  you are done.

A better answer will probably require a better question.

Dan   ;-)


On Oct 13, 10:44 am, karthikeya s  wrote:
> Does anyone have an idea about how to extract content from a file
> irrespective of file format???

-- 
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] Re: Sorting Array

[Dan]

Your question is good for a classroom style discussion/debate.
However,  in the real world, there is no simple answer.

There are lots of sorting algorithms.  Each one has it's pros & cons
and no single sorting algorithm is "best", especially when not much is
known about the data to be sorted.  In your case  about all that
we really know is that there are no negative numbers involved.  I
don't think that helps very much (any?).   Then...  you need to
consider the programming language and computer system used for the
implementation.  Yes.  They do matter.  Sometimes, they matter a
LOT.Don't assume that an O(x) algorithm is better than an O(y)
algorithm just because x is less than y.

Dan   :-)



On Jun 26, 12:14 am, ross  wrote:
> Given a sequence of numbers in the range of 1-N^2, what is the most
> efficient way to sort the numbers (better than NlgN)..
> Can counting sort be used here? Is an O(N) solution possible..

-- 
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] Re: NEED ALGO IN TIME 0.00

[Dan]

I found the problem statement on the web page link to be a bit
"weak".   Nothing in the problem statement says that you must do
anything other than read in two lines of integers and multiply them in
pairs and sum the results  ( ie.  Dot Product ).

People seem to think that you should sort the data first  ( an
assumption that is NOT in the problem statement ).   Does that mean
that you get the problem wrong if you don't sort the data first?

Also...  it looks as if you have to write the code in one of the
listed languages.  Is that true?
You then submit your "text" code and it is compiled somewhere else?
What compiler(s) is/are used and with what settings?  This can affect
both speed and memory (by large amounts).
Also...  exactly what does  1.6M  for  memory mean?

For the moment,  let's assume that you ARE supposed to sort the data
first.
Then...  at best,  all this test really does is check to see if you
can read and sort data quickly.  Multiplying pairs of numbers is
trivial and I doubt many individuals are writing much code to speed up
this simple Dot Product calculation.   So...  unless you write your
own integer sorting algorithm that you are very proud of,  what's the
point of this test (other than it might be worthwhile as a homework
assignment to new coders).

Have I missed something?

Dan   :-)


On Jun 24, 9:53 am, prathimzn  wrote:
> http://www.spoj.pl/problems/FASHION/
>
> i summit this question and my time is 0.02 as i used sorting and then
> multiply corresponding index value and sum them to get ans.
>
> but best time is 0.00 and 1.6M in C.
> can anyone tell me what is the best algo to solve this problem in 0.00 i.e.
> best algo
>
> *
>
> - - - - -
> WITH REGARDS,
> PRAMENDRA RATHI
> *
> **
> *B.TECH 2ND YEAR*
> *COMPUTER SCIENCE AND ENGINEERING*
> *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.

[algogeeks] Re: MS Question

[Dan]

I don't think you need a temp string (though, this may be a language
dependent issue).  Just use the string "as given" and keep track of
the character positions within the string.  The length of the original
string is irrelevant as long as your system can handle it.

Dan  :-)


On Jun 23, 2:44 pm, hary rathor  wrote:
> 1 :take directly word by word direct from input stream
> 2: just reverse word and put them into out stream
>
> Note : out stream can send data either on console or file
>
> this is require temp string  sizeof (> length of largest word)  that
> you calculate
>
> On 6/24/11, Ashish Goel  wrote:
>
>
>
>
>
>
>
>
>
> > given string "     abc    def    i   "
> > output string "     cba    fed    i   "
>
> > program is simple, write code and test this function
>
> > what if the given string is a book of 500 pages.
>
> > Best Regards
> > Ashish Goel
> > "Think positive and find fuel in failure"
> > +919985813081
> > +919966006652
>
> > --
> > 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.
>
> --
> Harish Pranami
> Master Of Computer Application ,
> Deptt of computer Science,
> north campus , university of delhi,
> New Delhi   pin no - 110007

-- 
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] Re: a doubt..

[Dan]

On Jun 13, 11:43 am, snehi jain  wrote:
> hi,
> we try to implement many programs using Recursion
> and its said that this is better than iterative procedure.
>
> if i am right then
> i cant understand why is it so?
>  can anybody explain ...
> and are there situations when iterative procedure is better than recursion.
>
> Snehi

Don't believe everything that you hear or read.   ;-)

If your instructor tells you simply that,   "recursion is better than
iteration",  you may want to go find a better (or more experienced)
instructor.

If your instructor tells you simply that,   "iteration is better than
recursion",  you may want to go find a better (or more experienced)
instructor.

You often see small "factorial" algorithms used as a demonstration of
recursion.   Does that mean that recursion is the way to go to do
factorials?

I'd consider the following four points before going with recursion or
iteration:

  Code readability and complexity ( or simplicity )
  Execution time
  Resource management  ( memory usage, etc )
  The language you're using and it's strengths/weaknesses

QuickSort is usually demonstrated using recursion.  But...  non-
recursive QuickSort is blazingly fast and isn't as likely to plow
through your resources.   I've seen a LOT of quicksort algorithms on
the net.  But...  I don't recall seeing one yet that I would consider
in a production code that had to sort large data sets.   I'm not
saying that one doesn't exist.  But...  I've not yet run across it.

Just my opinion,
Dan   :-)




-- 
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] Re: Find min after rotating an array

[Dan]

It depends "highly" on the language used doesn't it?

Based on the problem as stated
I'd assume no prior knowledge of the rotation amount or direction.
Unless the array is known/assumed to be very large,  the simplest
solution is likely the best.  Anything else may not qualify under the
"elegant" requirement.

Here's a simple Fortran solution:

given:
an integer array  a(n) with n elements in it
an integer scalar variable,  smallest_a,  to store the result in

:::  sorting, rotating, etc., etc. :::

Finding the minimum value is just a one-liner:

  smallest_a = MINVAL( a, dim=1 )

Dan  :-)

-- 
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] Re: C Output

[Dan]

Take a look at this article on the "The Perils of Floating Point"  by
Bruce Bush.

   http://www.lahey.com/float.htm

The discussion uses fortran code samples.   Though you clearly aren't
using fortran in your code, the article should still be an easy read
for you and it is applicable regardless of your language of choice.
In it, a few very simple techniques are discussed on ways to handle
comparisons of floating point numbers.   If you are going to do any
numerical programming,  you really NEED to know (or should want to
know) the information discussed in the article.

Dan   :-)

-- 
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] Re: Array Question

[Dan]

Look up the "Subset Sum" problem.  I think you may find that you can
put together a hybrid algorithm based on the classic method of
performing subset sum calculations.   I did something similar a few
years back.  It worked out pretty good as I recall.

Dan:-)

-- 
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] Re: Minimum positive-sum subarray

[Dan]

On Jan 21, 1:05 am, snehal jain  wrote:
> In this variation of the Maximum-Sum Subarray Problem, you are given a
> one-dimensional array A[1 : n] of positive or negative numbers, and
> you are asked to find a subarray A[i : j] such that the sum of its
> elements is (1) strictly greater than zero, and (2) minimum. In other
> words, you want to find a subarray of smallest positive sum. Give an
> O(nlog^2n) Divide and Conquer algorithm and a O(nlogn) Dynamic
> Programming Algorithm.

There are three considerations here:

1)  Insufficient clarity in the problem statement.
2)  Most people don't want to do others homework/school problems for
them.
3)  At very least...  you need to show that you are attempting to
answer the problem yourself at least a little bit.

-- 
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] Re: Symmetric matrix

[Dan]

You haven't provided enough information for anyone to give you any
kind of reasonable answer.

What language will you use to store & manipulate the matrix?
WHY do you wish to store the matrix?
How BIG is the matrix that you anticipate storing?
Do you need to store just one of them or several?
What will you do with the matrix once it is stored?
What type of algorithm do you intend to apply to the matrix data?
Can you overwrite the matrix while you manipulate it?
Do you need the same data over and over again?
How much memory is available to you to use?

Of course  if none of the above matters,  I'd say that you should
just store it in a 2D array of some type.   Of course, not all
languages have 2D array capability.   So... even this may be a bad
answer.

Side Note:  This sounds a bit like a Homework problem???  You know,
the kind that a teacher can't reasonably expect you to answer.

Dan   :-)

-- 
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] Re: subsorted array

[Dan]

On Dec 18, 9:57 am, snehal jain  wrote:
> Given an unsorted array arr[0..n-1] of size n, find the minimum length
> subarray arr[s..e] such that sorting this subarray makes the whole
> array sorted.


Sounds like a simple homework problem to me.:-)

-- 
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 options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Algorithm intensive Please solve

[Dan]

distance between two points,  a & b  =  SQRT[   (xa-xb)^2 + (ya-
yb)^2)  ]

Define  d = the above distance squared  =  (xa-xb)^2 + (ya-yb)^2)

d =   xa^2 - 2*xa*xb + xb^2   +   ya^2 - 2*ya*yb + yb^2

d =   xa^2 - 2*xa*xb + xb^2   +   ya^2 - 2*ya*yb + yb^2

d =  ( xa^2 + xb^2 + ya^2 + yb^2 )  -  2*( xa*xb + ya*yb )

d =   first-term  -   second-term

The first-term is always positive and will always occur for all  (x,y)
pairs  ( paired off as point a & point b ).

Thus,  we want the part of the second-term in parenthesis to be as
positively large as possible !!!

Thus,  for all pairs of points   a(x,y)   &   b(x,y),   we want to
choose the  a-b pairs that cause the sum of all pairs to be as large
as possible.

ie.If we can sum all  pairs,   a(x,y) &  b(x,y)  and   Maximize
the value of: xa*xb + ya*yb  ,   we will have an answer!!!


So...  given a bunch of points  (xi,yi),  how do we pair them up such
that  for each pair of points,  a(x,y) & b(x,y),  we get a maximum
value of   xa*xb + ya*yb  ???

If you solve this algorithm  I think you have a solution.   Is it
easier this way?   I'm not really sure.

Dan   :-)

-- 
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 options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: mutual exclusion algorithm problem

[Dan Ulman]

Nat (Padmanabhan Natarajan) wrote:
> is the flag := true equvilanet to Test & Set instruction? That is, can we
> assume that setting/unsetting the flag is an atomic operation?

since it is a single command, I assume that, yes, it is atomic.
Thanks !

>
> On 6/14/06, Dan Ulman <[EMAIL PROTECTED]> wrote:
> >
> >
> > Hi ! Can you please help me with the following ?
> >
> > Let A be an arbitrary deadlock-free mutual exclusion algorithm in which
> > the
> > number of steps in the exit code of A depends on the activity of the
> > other
> > processes (e.g., it has a loop with a wait statement).
> >
> > In the following, A is modifed, so that the new algorithm satisfies the
> > requirement
> > that the exit code be of constant number of steps.
> > The modified algorithm uses one additional shared bit, called flag, is
> > used.
> >
> > This is the modified mutual exclusion algorithm:
> >
> > 1 entry code of original A;
> > 2 while flag do skip od;
> > 3 flag := true;
> > 4 exit code of original A; /* Whose step complexity may depend on other
> > processes */
> > 5 critical section;
> > 6 flag := false;
> >
> > Does the modifed algorithm satisfy deadlock-freedom and/or mutual
> > exclusion (for any A)? Prove your answers.
> >
> > thanks !!
> > Dan.
> >
> >
> > >
> >
>
> --=_Part_9201_28782189.1150285992293
> Content-Type: text/html; charset=ISO-8859-1
> X-Google-AttachSize: 1385
>
> is the flag := true equvilanet to Test & Set instruction? That is, can we 
> assume that setting/unsetting the flag is an atomic 
> operation?On 6/14/06,  class="gmail_sendername">Dan Ulman
>  <mailto:[EMAIL PROTECTED]">[EMAIL PROTECTED]> 
> wrote:Hi ! 
> Can you please help me with the following ?
> Let A be an arbitrary deadlock-free mutual exclusion algorithm in 
> whichthenumber of steps in the exit code of A depends on the activity 
> of theotherprocesses (e.g., it has a loop with a wait statement).
> In the following, A is modifed, so that the new algorithm satisfies 
> therequirementthat the exit code be of constant number of 
> steps.The modified algorithm uses one additional shared bit, called flag, 
> is
> used.This is the modified mutual exclusion algorithm:1 
> entry code of original A;2 while flag do skip od;3 flag := true;4 
> exit code of original A; /* Whose step complexity may depend on other
>  processes */5 critical section;6 flag := false;Does the 
> modifed algorithm satisfy deadlock-freedom and/or mutualexclusion (for 
> any A)? Prove your answers.thanks !!Dan.
> --=_Part_9201_28782189.1150285992293--


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] mutual exclusion algorithm problem

[Dan Ulman]

Hi ! Can you please help me with the following ?

Let A be an arbitrary deadlock-free mutual exclusion algorithm in which
the
number of steps in the exit code of A depends on the activity of the
other
processes (e.g., it has a loop with a wait statement).

In the following, A is modifed, so that the new algorithm satisfies the
requirement
that the exit code be of constant number of steps.
The modified algorithm uses one additional shared bit, called flag, is
used.

This is the modified mutual exclusion algorithm:

1 entry code of original A;
2 while flag do skip od;
3 flag := true;
4 exit code of original A; /* Whose step complexity may depend on other
 processes */
5 critical section;
6 flag := false;

Does the modifed algorithm satisfy deadlock-freedom and/or mutual
exclusion (for any A)? Prove your answers.

thanks !!
Dan.


--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---